Project Euler Problem 92: Erklärung eines Lösungsweges gesucht
-
Hallo,
ich hab Problem 92 bei Project Euler gelöst. Im internen Forum des Problems hab ich eine Lösung gefunden, die wohl sehr schnell sein soll. Das Problem dabei ist nur, dass ich sie nicht komplett verstehe.
Ich poste mal die Erklärung des Users ceebo53 (2. Seite im internen Forum) - Spoilergefahr für alle, die das Problem noch nicht gelöst haben:
ceebo53 schrieb:
There's actually no need to store huge lists or to have to cycle through each number from 1 to 10^7.
After a single iteration of the "sum squares of digits" step the number is guaranteed to be less than or equal to 9^2*7 = 567.
Now for each number n <= 567 that ends its cycle with 89 the question becomes: "How many numbers below 10^7 have the sum of the squares of their digits equal to n?"
Let the number of ways of writing n as the sum of k squares be f(n,k). Then f can be computed by the recurrence relation:
f(n,k) = f(n-0^2,k-1) + f(n-1^2,k-1) + f(n-2^2,k-1) + .... + f(n-9^2,k-1)
Base cases:
f(n,k) = 0 if n<0
f(n,0) = 0 if n>0
f(0,0) = 1Den ersten Teil in dem erklärt wird, dass es nur 567 verschiedene Kombinationen gibt, hab ich verstanden. Aber ich bekomme einfach nicht raus wie man anhand dieser Zahlen darauf schließen kann wie viele Kombinationen es genau gibt. Kann mir das jemand erklären?
Viele Grüße
Antoras
-
Also der nächste Schritt ist die Überlegung, dass wenn man die Summe n aus k Quadraten mit f(n,k) Möglichkeiten zusammensetzen kann, dann muss dieses f{n,k} gleich dem Term sein der da steht, was die Summe der Möglichkeiten ist, (n-Quadratzahl) mit k-1 Quadratzahlen darzustellen.
Und wie das danach mit dem Lösen dieser Differenzengleichung weitergeht weiß ich auch nicht, Lineare Algebra 2 ist zu lange her und ich habe das nie wieder im Leben gebraucht. Ich würde daher mal auf Wikipedia verweisen, habe aber keine Lust das selber noch mal alles zu lernen.
-
Hey,
vielen Dank für deine Antwort.
SeppJ schrieb:
Also der nächste Schritt ist die Überlegung, dass wenn man die Summe n aus k Quadraten mit f(n,k) Möglichkeiten zusammensetzen kann, dann muss dieses f{n,k} gleich dem Term sein der da steht, was die Summe der Möglichkeiten ist, (n-Quadratzahl) mit k-1 Quadratzahlen darzustellen.
Mit was für Startparametern soll der Term denn aufgerufen werden? n dürfte eine Zahl von 2-567 sein, aber was ist k? Die Anzahl der Ziffern von n?
Und vor allem was für einen Wert gibt f(n,k) denn zurück. In der Erklärung steht nur was von 1 und 0, aber da fehlt doch noch was?
Ich hab ein Blog gefunden, in dem die gleiche Methode nochmal beschrieben wird (ziemlich am Ende des Artikels). Ich hab es aber noch immer nicht verstanden. Der dabeistehende Code ist leider F#, was ich nur halb entschlüsselt bekomme.SeppJ schrieb:
Und wie das danach mit dem Lösen dieser Differenzengleichung weitergeht weiß ich auch nicht, Lineare Algebra 2 ist zu lange her und ich habe das nie wieder im Leben gebraucht. Ich würde daher mal auf Wikipedia verweisen, habe aber keine Lust das selber noch mal alles zu lernen.
In dem Blog sieht das nur so aus wie wenn das rekursiv aufgelöst wird. Das kann man aber immer noch optimieren wenn es mal läuft.
-
Antoras schrieb:
Mit was für Startparametern soll der Term denn aufgerufen werden? n dürfte eine Zahl von 2-567 sein, aber was ist k?
7. Und die 1 würde ich drinlassen, sonst erwischt du die Zehnerpotenzen nicht. (edit: Ach, es sind ja nur die gesucht, die auf eine 89 enden. Dann kannste die 1 weglassen, da die 1 logischerweise mit 1 endet)
Und vor allem was für einen Wert gibt f(n,k) denn zurück. In der Erklärung steht nur was von 1 und 0, aber da fehlt doch noch was?
Nein, 1 ist nur einer der bekannten Werte, mit denen man seine Rekursion abbrechen kann. Es wird die Gesamtzahl an Zahlen mit 7 oder weniger Ziffern zurückgegeben die äquivalent zu n sind in dem Sinne des ersten Teils des Beweises.
In dem Blog sieht das nur so aus wie wenn das rekursiv aufgelöst wird. Das kann man aber immer noch optimieren wenn es mal läuft.
Ach, einfach numerisch. Ja, dann ist die Technik und der Tipp der dazu gegeben wurde einleuchtend. Ich dachte da sollte irgendeine clevere Formel bewiesen werden, was mich verwirrt hat, da ich mich an nichts diesbezüglich aus der (formellen) Mathematik erinnern kann, dass den Begriff "base class" benutzt hätte. Aber mit einem Computer ist es natürlich simpel, alle 567 Zahlen durchzuprobieren.
edit2: Und natürlich hätte eine Bruteforce Lösung innerhalb von Sekunden (höchstens!) alle 7-Stelligen Zahlen durchprobiert, ohne dass man sich stundenlang Gedanken hätte machen müssen :p .
-
SeppJ schrieb:
Nein, 1 ist nur einer der bekannten Werte, mit denen man seine Rekursion abbrechen kann. Es wird die Gesamtzahl an Zahlen mit 7 oder weniger Ziffern zurückgegeben die äquivalent zu n sind in dem Sinne des ersten Teils des Beweises.
Ich kapier es noch immer nicht.
In welcher Reihenfolge werden die Additionen in f(n,k) den aufgerufen? Wird die komplette Gleichung mitf(n-0^2,k-1) + f(n-1^2,k-1) + f(n-2^2,k-1) + .... + f(n-9^2,k-1) f(n-0^2,k-2) + f(n-1^2,k-2) + f(n-2^2,k-2) + .... + f(n-9^2,k-2) f(n-0^2,k-3) + f(n-1^2,k-3) + f(n-2^2,k-3) + .... + f(n-9^2,k-3) ... f(n-0^2,k-1) + f(n-1^2,0) + f(n-2^2,0) + .... + f(n-9^2,0)aufgerufen? Also, dass k so lange runter gezählt wird bis es 0 ist?
SeppJ schrieb:
edit2: Und natürlich hätte eine Bruteforce Lösung innerhalb von Sekunden (höchstens!) alle 7-Stelligen Zahlen durchprobiert, ohne dass man sich stundenlang Gedanken hätte machen müssen :p .
Ich weiß, meine jetzige Lösung braucht nicht mal eine Sekunde, aber ist Brute-force. Die Lösung interessiert mich an sich nicht, ich bin am Lösungsweg interessiert und Brute-force ist inakzeptabel.
-
Aus deinem Code-Block werde ich nicht schlau, weshalb ich dir nicht sagen kann, ob du es richtig verstanden hast.
n ist eine Zahl zwischen 2 und 567, das hast du schon richtig erkannt. k ist die Anzahl der Ziffern. f(n-x^2,k-1) bedeuet: Die aktuelle Ziffer, die ich mir gerade anschaue, ist x. Da ich als gesamte Summe n herausbekommen möchte, müssen sich die anderen k-1 Ziffern zusammen zu n-x^2 aufsummieren. Wenn man alle möglichen x durchgeht und aufsummiert, hat man alle Möglichkeiten durchprobiert und f(n, k) bestimmt.
Nun zu den Startwerten:
f(n, k) = 0, wenn n < 0. Diese Bedingung musst du reinnehmen für den Fall, dass x^2 > n ist bei einem deiner rekursiven Aufrufe. Denn es gibt keine Möglichkeit, auf die Gesamtsumme n zu kommen, wenn du mit den bisherigen Ziffern bereits mehr als n erreicht hast.
f(n, 0) = 0, wenn n > 0. Du bist alle dir zur Verfügung stehenden Ziffern durchgegangen, aber die Summe ist noch nicht n. Also wieder nicht das, was du haben willst.
f(0, 0) = 1. In diesem Fall summieren sich die k Ziffern zu n. Das ist genau der Fall, den du haben willst. Der Stack Trace repräsentiert genau eine Möglichkeit für die Ziffern 1,...,k, die Summe n zu erreichen. Deshalb ist der Zahlenwert 1.
-
In welcher Reihenfolge werden die Additionen in f(n,k) den aufgerufen?
In Code ausgedrückt:
int f(int n, int k) { if (n < 0) return 0; if (k == 0 && n == 0) return 1; if (k == 0) return 0; return f(n - 0*0, k-1) + f(n - 1*1, k-1) + f(n - 2*2, k-1) + f(n - 3*3, k-1) + f(n - 4*4, k-1) + f(n - 5*5, k-1) + f(n - 6*6, k-1) + f(n - 7*7, k-1) + f(n - 8*8, k-1) + f(n - 9*9, k-1); } #include<iostream> using namespace std; int main() { for (int n = 2; n <= 567; ++n) cout << "Die Anzahl siebenstelliger Zahlen deren Ziffernquadrate die Summe " << n << " ergeben ist " << f(n,7) << endl; }Ich weiß, meine jetzige Lösung braucht nicht mal eine Sekunde, aber ist Brute-force. Die Lösung interessiert mich an sich nicht, ich bin am Lösungsweg interessiert und Brute-force ist inakzeptabel.
Du wirst überrascht sein, wenn du siehst, wie lange die rekursive Lösung braucht
. Brute-Force ist nicht unbedingt schlecht.
-
SeppJ schrieb:
Du wirst überrascht sein, wenn du siehst, wie lange die rekursive Lösung braucht
. Brute-Force ist nicht unbedingt schlecht.Die rekursive Lösung schreit aber förmlich danach, optimiert zu werden
-
Am gewinnbringendsten dürfte es wohl sein, ein 257x10-Array zu erstellen und iterativ für k = 0,...,9 mit der Rekursionsformel zu füllen. Dabei kann man sich sogar die Hälfte der Einträge sparen. Ich hab hier aber leidert keinen Compiler, sodass ich es nicht ausprobieren kann.
-
Michael E. schrieb:
n ist eine Zahl zwischen 2 und 567, das hast du schon richtig erkannt. k ist die Anzahl der Ziffern. f(n-x^2,k-1) bedeuet: Die aktuelle Ziffer, die ich mir gerade anschaue, ist x. Da ich als gesamte Summe n herausbekommen möchte, müssen sich die anderen k-1 Ziffern zusammen zu n-x^2 aufsummieren. Wenn man alle möglichen x durchgeht und aufsummiert, hat man alle Möglichkeiten durchprobiert und f(n, k) bestimmt.
Ok, ich glaub ich hab es jetzt verstanden. Es werden einfach alle möglichen Kombinationsmöglichkeiten durchprobiert. Wenn eine Kombination n ergibt. dann wird eine 1 zurückgegeben sonst 0.
Aber ineffizient ist diese Lösung wirklich, d.h. ja, dass bei jeder Zahl immer wieder alle Kombinationen durchgegangen werden, oder?SeppJ schrieb:
Du wirst überrascht sein, wenn du siehst, wie lange die rekursive Lösung braucht
. Brute-Force ist nicht unbedingt schlecht.Wenn ich den Code jetzt richtig verstanden habe, dann ist er ja auch Brute-force, nur eben über einen anderen Lösungsweg.
Michael E. logged out schrieb:
Am gewinnbringendsten dürfte es wohl sein, ein 257x10-Array zu erstellen und iterativ für k = 0,...,9 mit der Rekursionsformel zu füllen. Dabei kann man sich sogar die Hälfte der Einträge sparen. Ich hab hier aber leidert keinen Compiler, sodass ich es nicht ausprobieren kann.
Das mit dem Array wurde in dem Blog mit dem F#-Code glaube ich auch so gemacht.
Aber das hab ich auch wieder nicht verstanden.
Wie soll das Array genau gefüllt werden?
-
Antoras schrieb:
Das mit dem Array wurde in dem Blog mit dem F#-Code glaube ich auch so gemacht.
Aber das hab ich auch wieder nicht verstanden.
Wie soll das Array genau gefüllt werden?Ich hab die Aufgabe vor Jahren auch mal gemacht. Das war meine Lösung (braucht auf meinem i3-330M ca. 335ms, Brute Force dauert glaub ich ca. 1,5s):
vector<int> table; table.reserve(600); table.push_back(-1); for(int i = 1; i < 568; ++i) { int foo = i; while(foo != 1 && foo != 89) { int bar = 0; while(foo > 0) { bar += (foo % 10) * (foo % 10); foo /= 10; } foo = bar; } if(foo == 89) table.push_back(1); else table.push_back(0); } int sum = 0; for(int i = 1; i < 10000000; ++i) { int foo = i; int bar = 0; while(foo > 0) { bar += (foo % 10) * (foo % 10); foo /= 10; } sum += table[bar]; } return sum;Ich versuch aber gerade, den Rekursionansatz schneller zu machen.
-
Nachdem ich gesehen habe, wie schnell die letzte Lösung im projecteuler-Thread (von Peteris, Seite 5) bei mir (3ms) ist, habe ich ehrlich gesagt die Lust verloren, einen minderwertigen Ansatz zu optimieren
-
Stimmt, da hätte ich auch keine Lust mehr drauf. Ich hab den Post leider übersehen, sonst hätte ich mich ihm gleich zugewandt. Hast du zufällig herausgefunden wie der Code funktioniert?
Der erste Teil, in dem die Zahlen berechnet werden, die in 1 oder 89 enden ist klar, aber ich verstehe nicht wie man anhand der Quadratzahlen von 1-9 darauf schließen kann wie oft die Zahlen vorkommen.
-
Antoras schrieb:
Stimmt, da hätte ich auch keine Lust mehr drauf. Ich hab den Post leider übersehen, sonst hätte ich mich ihm gleich zugewandt. Hast du zufällig herausgefunden wie der Code funktioniert?
Der erste Teil, in dem die Zahlen berechnet werden, die in 1 oder 89 enden ist klar, aber ich verstehe nicht wie man anhand der Quadratzahlen von 1-9 darauf schließen kann wie oft die Zahlen vorkommen.
Die Idee ist wieder dieselbe wie bei der Rekursion, nach der du gefragt hast. Allerdings macht Peteris das Ganze iterativ und rückwärts. Im Set stehen alle Zahlen von 0 bis 257, die nach den ersten k Stellen auftreten können. Im Vektor stehen die dazugehörigen Häufigkeiten.
-
Super, ich hab es verstanden! Vielen Dank an alle, die mir geholfen haben.
Hab diesen C/C++ Mischcode in Scala nachprogrammiert und ihn so weit optimiert bekommen, dass er anstatt 3ms nur noch 0.5ms benötigt.
Ich hab leider keinen Weg gefunden das ständige Umkopieren des Sets und das Neuanlegen des Arrays zu verhindern. Fällt da noch jemandem was ein wie man das in den Griff bekommen könnte? Andererseits ist jetzt auch schon genug optimiert. Nur schade, dass ich meinen Code bei Project Euler nicht mehr posten kann.
-
Antoras schrieb:
Ich hab leider keinen Weg gefunden das ständige Umkopieren des Sets und das Neuanlegen des Arrays zu verhindern.
Das wirst du IMHO auch nicht verhindern können.
Fällt da noch jemandem was ein wie man das in den Griff bekommen könnte?
Bedenke, dass die meisten keinen Zugriff auf den Code haben
Andererseits ist jetzt auch schon genug optimiert. Nur schade, dass ich meinen Code bei Project Euler nicht mehr posten kann.
Du kannst ihn ja hier posten. Dann seh ich mal, wie schön Scala ist.
-
Michael E. schrieb:
Antoras schrieb:
Ich hab leider keinen Weg gefunden das ständige Umkopieren des Sets und das Neuanlegen des Arrays zu verhindern.
Das wirst du IMHO auch nicht verhindern können.
Hätte ja sein können, dass es einen speziellen Programmiertrick gibt mit dem man das in Griff bekommen könnte. Aber der läuft jetzt ja und das wichtigste: Ich hab ihn verstanden.
Michael E. schrieb:
Du kannst ihn ja hier posten. Dann seh ich mal, wie schön Scala ist.
Ich glaube nicht, dass der Code besonders geeignet ist um die Schönheit von Scala zu demonstrieren, aber urteile selbst:
object P92 extends App { bench (warmup = true) { 1000.times { solution1 } } def solution1 = { val end = 9*9*7 val squares = (0 to 9) map toSquare val set = mutable.BitSet() ++ squares var count = new Array[Int](9*9+1) for (s <- set) count(s) = 1 for (i <- (2 to 7)) { val newCount = new Array[Int](count.size+9*9) for (s <- set.clone; d <- squares) { newCount(s+d) += count(s) set += s+d } count = newCount } val chainEend = 0 +: ((1 to end) map findEnd) val occurrences = set.iterator map (s => chainEend(s)*count(s)) occurrences.sum } def findEnd: Int => Int = { case 89 => 1 case 1 => 0 case n => n |> next |> findEnd } def toSquare(n: Int) = n*n def next(n: Int): Int = { def loop(n: Int, res: Int): Int = if (n == 0) res else loop(n/10, res + toSquare(n%10)) loop(n, 0) } /* * More idiomatic, but slower */ // def next(n: Int) = n.toString map (_-'0' |> toSquare) sum }
