Articles of algoritmo

Progetto Eulero Domanda 14 (Problema di Collatz)

La seguente sequenza iterativa è definita per l’insieme di numeri interi positivi: n -> n / 2 (n è pari) n -> 3n + 1 (n è dispari) Usando la regola sopra e iniziando con 13, generiamo la seguente sequenza: 13 40 20 10 5 16 8 4 2 1 Si può vedere che questa […]

Come trovare tutti i sottoinsiemi possibili di un determinato array?

Voglio estrarre tutti i possibili sottoinsiemi di una matrice in C # o C ++ e quindi calcolare la sum di tutti i rispettivi elementi degli array di sottoinsiemi per verificare quanti di essi sono uguali a un dato numero. Quello che sto cercando è l’algoritmo. Capisco la logica qui, ma non sono stato in […]

Calcolo del percorso più breve tra due punti

Ho lavorato nelle ultime settimane su un gioco HTML5 multiplayer, usando nodejs e websockets . Sono rimasto bloccato in questo problema per un po ‘. Immagina di avere questa mappa del tilesheet implementata con un array ( come mostrato sotto ). 1 o tessere marroni – c’è un ostacolo nel modo in cui il giocatore […]

Il setaccio di Atkin

Ho cercato di imparare gli algoritmi per generare numeri primi e mi sono imbattuto in Sieve of Atkin su Wikipedia. Capisco quasi tutte le parti dell’algoritmo, tranne alcune. Ecco le domande: Come sono formate le tre equazioni quadratiche sotto? 4x ^ 2 + y ^ 2, 3x ^ 2 + y ^ 2 e 3x […]

Soluzione rapida a sum sottoinsieme

Considera questo modo di risolvere il problema della sum del sottoinsieme: def subset_summing_to_zero (activities): subsets = {0: []} for (activity, cost) in activities.iteritems(): old_subsets = subsets subsets = {} for (prev_sum, subset) in old_subsets.iteritems(): subsets[prev_sum] = subset new_sum = prev_sum + cost new_subset = subset + [activity] if 0 == new_sum: new_subset.sort() return new_subset else: […]

Java: genera il set di potenza di una determinata lista

Sto provando a generare una raccolta di tutte le 2 ^ N – 1 combinazioni possibili di un determinato Elenco di lunghezza N. La raccolta mapperà il numero di elementi in una combinazione in un elenco ordinato di combinazioni contenenti combinazioni della lunghezza specifica. Ad esempio, per la lista: [A, B, C, D] Voglio generare […]

Trovare tutte le permutazioni uniche di una stringa senza generare duplicati

La ricerca di tutte le permutazioni di una stringa avviene tramite un noto algoritmo Steinhaus-Johnson-Trotter. Ma se la stringa contiene i caratteri ripetuti come AABB, allora le possibili combinazioni uniche saranno 4! / (2! * 2!) = 6 Un modo per ottenere ciò è che possiamo memorizzarlo in un array o giù di lì e […]

Buona sostituzione di GetHashCode () per gli oggetti List of Foo che rispettano l’ordine

EnumerableObject : IEnumerable avvolge una List Se EnumerableObject a.SequenceEquals( EnumerableObject b) , allora sono uguali. Pertanto, è necessario implementare un GetHashCode . Il problema è che XORing ogni elemento nell’elenco restituirà lo stesso codice hash per qualsiasi elenco con tutti e solo gli stessi elementi, indipendentemente dall’ordine. Questo va bene in termini di funzionamento, ma […]

Come eliminare in una struttura dati heap?

Capisco come eliminare il nodo radice da un heap massimo ma è la procedura per eliminare un nodo dal centro per rimuovere e sostituire la radice più volte fino a quando il nodo desiderato viene eliminato? O (log n) è la complessità ottimale per questa procedura? Questo influenza la grande complessità O dal momento che […]

Algoritmo di Bresenham in Javascript

Ho bisogno di un algoritmo veloce per calcolare le coordinate di una linea tra due punti. Ho cercato di trovare una buona implementazione JavaScript di Bresenham, ma ci sono troppe pubblicazioni abbastanza confuse. In wikipedia – qui la forma più veloce e semplice (nessuna divisione e calcolo degli errori per entrambe le direzioni) è presentata […]