Projekt Euler # 8: Gibt es einen effizienteren Algorithmus als Brute-Force-Berechnung?

Question

Frage

Gibt es einen besseren Weg, um die Lösung des Projekts Euler Problem 8 zu finden, die Find the greatest product of five consecutive digits in the 1000-digit number, als die Brute-Force-Methode.

Ich berechnete alle möglichen Produkte und wählte den größten - Brute-Force-Algorithmus.

Gibt es einen effizienteren Algorithmus? Oder ist die Brute-Force-Methode der einzige Weg?

Side Noten

• Dies ist keine Hausaufgaben Frage.
• ich frage nicht für das Ergebnis Problem 8.

Answer 1

Da die Frage aufeinanderfolgenden Ziffern fragt nach 'Brute-Force' bedeutet O (n) in diesem Fall n das Wesen Anzahl der Ziffern (1000). Solange es keine Art von Muster in der Zahl gibt, benötigen Sie n Schritte für das Scannen nur die Nummer, so ist dies die schnellste Lösung.

Sie können das Produkt der letzten 4 Ziffern zwischenspeichern oder ähnliche Tricks, aber Sie werden definitiv nicht besser als O (n).

Answer 2

Sie können ein Schiebefenster der Größe 5 verwenden und dieses in O(d) lösen, wobei d die Anzahl der Ziffern in der Eingabezahl ist.

Sie repräsentieren das Fenster nach Index der Startnummer im Fenster und der Wert des Fensters i ist das Produkt der Elemente mit Index [i, i + 4]. Jetzt schieben Sie das Fenster in jeder Iteration nach rechts, so dass das Element ganz links abgelegt wird und ein neues Element rechts hinzugefügt wird. Der neue Wert des Fensters ist old_value/left_most_ele * new_right_ele. Machen Sie dies für jeden Index i im Bereich [0,d-5] und finden Sie den maximalen Fensterwert.

Beachten Sie, dass die Brute-Force-Methode mit geschachtelten Schleifen, bei denen die innere Schleife fünf Mal ausgeführt wird, auch eine O(d) Lösung ist. Aber die obige Methode ist etwas besser, da wir nicht fünf Multiplikationen in jedem Schritt machen, sondern stattdessen eine Multiplikation und eine Division.

Answer 3

Ja und nein. Sie müssen sich jede Sequenz von fünf aufeinanderfolgenden Ziffern ansehen, aber Sie müssen nicht jede einzelne dieser Sequenzen jedes Mal durch die Schleife multiplizieren. Es gibt Verknüpfungen, die Sie verwenden können, um die Verarbeitung zu beschleunigen. Zum Beispiel, wenn die nächste Ziffer eine 0 ist, können Sie weiterspringen. Wenn die nächste Ziffer kleiner ist als die letzte, die Sie aus der Sequenz gelöscht haben, wissen Sie, dass das Ergebnis der Multiplikation mit den anderen vier Ziffern kleiner ist. Überspringen Sie also die Multiplikation und gehen Sie zur nächsten Ziffer. Tricks wie diese machen keinen großen Unterschied, wenn Sie nur 1000 Ziffern haben, aber später werden die Probleme gleich sein, nur bei größeren Eingaben.

Answer 4

Eine Optimierung besteht darin, das Produkt der ersten fünf Ziffern zu berechnen und in jeder Iteration mit der nächsten Ziffer zu multiplizieren und durch das vorherige (bewegte Fenster) zu dividieren.

Eine weitere Optimierung besteht darin, alle Ziffern um 0 sofort zu verwerfen.