Project Euler # 8: Esiste un algoritmo più efficiente del calcolo della forza bruta?

Question

Domanda

C'è un modo migliore per trovare la soluzione del problema Project Euler 8, che è Find the greatest product of five consecutive digits in the 1000-digit number, rispetto al metodo della forza bruta.

Ho calcolato tutti i possibili prodotti e selezionato il più grande algoritmo a forza bruta.

Esiste un algoritmo più efficiente? Oppure il metodo della forza bruta è l'unico modo. Note

laterale

• Questa non è una questione compiti a casa.
• non sto chiedendo per il risultato problema 8.

Answer 1

Poiché la domanda chiede cifre consecutive, 'forza bruta' significa O (n) in questo caso, n essendo la numero di cifre (1000). Finché non c'è una sorta di modello nel numero, è necessario n passaggi per la semplice scansione del numero, quindi questa è la soluzione più veloce.

È possibile memorizzare nella cache il prodotto delle ultime 4 cifre o eseguire trucchi simili, ma sicuramente non sarà migliore di O (n).

Answer 2

È possibile utilizzare una finestra scorrevole di dimensioni 5 e risolverlo in O(d), dove d è il numero di cifre nel numero di input.

Rappresenta la finestra per indice del numero iniziale nella finestra e il valore della finestra i è il prodotto di elementi con indice [i, i + 4]. Ora in ogni iterazione fai scorrere la finestra a destra, facendo cadere l'elemento più a sinistra e aggiungendo un nuovo elemento a destra e il nuovo valore della finestra è old_value/left_most_ele * new_right_ele. Continua a farlo per ogni indice i nel range [0,d-5] e trova il valore massimo della finestra.

Si noti che il metodo di forza bruta di avere cicli nidificati in cui il ciclo interno viene eseguito cinque volte è anche una soluzione O(d). Ma il metodo sopra è leggermente migliore in quanto non facciamo cinque moltiplicazioni in ogni passo, ma invece facciamo una moltiplicazione e una divisione.

Answer 3

Sì e no. Devi guardare ogni sequenza di cinque cifre consecutive, ma non devi moltiplicare ciascuna di queste sequenze ogni volta che passi attraverso il ciclo. Esistono scorciatoie da eseguire che velocizzano l'elaborazione. Ad esempio, se la cifra successiva è uno 0, puoi saltare avanti. Inoltre, se la cifra successiva è più piccola dell'ultima che hai lasciato dalla sequenza, sai che il risultato della moltiplicazione per le altre quattro cifre comuni sarà inferiore, quindi salta alla moltiplicazione e vai alla cifra successiva. Trucchi come questo non fanno molta differenza quando hai solo 1000 cifre, ma i problemi successivi saranno gli stessi, solo con input più grandi.

Answer 4

Un ottimizzazione consiste nel calcolare il prodotto delle prime cinque cifre e in ogni iterazione moltiplicare per cifra successiva e dividere per il precedente (finestra in movimento).

Un'altra ottimizzazione è quella di eliminare immediatamente tutte le cifre intorno a 0.