Wie finden Sie alle möglichen Werte der vier Variablen, wenn die quadrierte Summe der N?
A^2+B^2+C^2+D^2 = N
Gegeben eine ganze Zahl N
, drucken Sie alle möglichen Kombinationen von ganzzahligen Werten von ABCD
die Lösung der Gleichung.
Ich vermute, wir können es besser als brute-force.
- Siehe diesem Artikel auf Wikipedia und verwandten Artikeln.
- Dies wird wahrscheinlich bewirken eine dynamische Programmierung Lösung oder Heuristik.
- Der Wikipedia-Artikel keine information, wie zum auflisten aller Lösungen für die vier-Quadrat-problem (es in Erster Linie Vorträge über den mathematischen Beweis der damit verbundenen Vermutung). Es tut Verweis auf einen Artikel von Rabin und Shallit, jedoch, dass der Artikel nur beschreibt das finden einer einzigen Lösung, nicht, wie das auflisten aller möglichen Lösungen. darüber hinaus, der Artikel ist nicht online, aber ist ein Kostenpflichtiger download.
- Deshalb ist es ein Kommentar - einfach für mehr Informationen auf die Eigenschaft der Summe von 4 Quadraten.
- FWIW, ich habe nachgedacht über diese eine, und ich bin jetzt überzeugt, dass dies geschehen kann in O(N) Zeit, wobei N die gewünschte Summe (sicherlich nicht schlechter als O(N*sqrt(N))). Ich bin mir immer noch nicht sicher, ob das ein guter Zeitpunkt ist, oder nicht...
- Welche Art von Arbeit fordert dies als eine interview-Frage?!?
- Seine ein google-interview-Frage.
- Follow-Up: ich stellte auf dem CS-forum, hier(cs.stackexchange.com/questions/2988/...). Es scheint, dass die theoretische schnellsten diese kann getan werden, ist O(N*Log(Log(N))), und die c# - Methode, die ich gepostet, es scheint sich zu erreichen, dies.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Die Wikipedia-Seite hat einige interessante hintergrund-Informationen, aber die Lagrange-vier-Quadrat-theorem (oder, mehr korrekt, Bachet ' s Theorem - Lagrange nur bewiesen es) nicht wirklich ins detail gehen, wie man sagte Quadrate.
Als ich sagte, in meinem Kommentar, die Lösung wird nicht trivial. Dieses Papier beschreibt die Lösbarkeit von vier-Quadrat-Summen. Das Papier behauptet, dass:
Weitere Informationen finden Sie unter Modulare Formen. Dies ist nicht einfach zu verstehen, es sei denn, Sie haben einige hintergrund in der Zahlentheorie. Wenn Sie könnten verallgemeinern Ramanujan 54 Formen, Sie haben vielleicht eine einfachere Zeit mit dieser. Mit dieser sagte, in der ersten Papier, das ich zitieren, es gibt einen kleinen Schnipsel, die diskutiert einen Algorithmus finden können jede Lösung (obwohl ich finde es ein bisschen schwer zu Folgen):
(Hervorhebung von mir.)
Wird der Algorithmus beschrieben als rekursive, aber es könnte leicht umgesetzt werden iterativ.
largest square below N
oderlargest square less than or equals N
? Wenn eslargest square below N
dann, wie gehen wir mit Quadratzahlen?Naive brute-force wäre so etwas wie:
Leider, so führt dies über eine Billion Schleifen, nicht übermäßig effizient.
Können Sie tatsächlich wesentlich besser, als dass durch Diskontierung der riesigen Zahl von Unmöglichkeiten auf jeder Ebene mit so etwas wie:
Es ist immer noch brute force, aber nicht ganz so Brutal, insofern es versteht, Wann man aufhören jede Ebene der Schleife, so früh wie möglich.
Auf meinem (relativ) bescheidenen box, das dauert unter einer Sekunde (a), um alle Lösungen für zahlen bis zu 50.000. Darüber hinaus, es beginnt mehr Zeit nehmen:
Für
n = ten million
es ging schon etwa eine Stunde und eine Hälfte, bevor ich es getötet.So, ich würde sagen, brute-force ist durchaus akzeptabel, bis auf einen Punkt. Darüber hinaus, mehr mathematische Lösungen benötigt werden würde.
Für noch mehr Effizienz, Sie konnte nur prüfen, diese Lösungen, wo
d >= c >= b >= a
. Das ist, da könnte man dann aufbauen, alle Lösungen, die von diesen Kombinationen in Permutationen (mit potentiell doppelte Entfernung, wo die Werte von zwei oder mehr dera
,b
,c
oderd
identisch sind).Zusätzlich, den Körper des
d
Schleife nicht überprüfen müssen, um jeden Wert vond
nur die Letzte mögliche.Immer die Ergebnisse für
1,000,000
in diesem Fall dauert weniger als zehn Sekunden, statt über sechs Minuten:Code folgt:
Und, laut einem Vorschlag von DSM, die
d
Schleife kann ganz verschwinden (da gibt es nur einen möglichen Wert vond
(Diskontierung negative zahlen) und es können berechnet werden), die bringt der eine million Fall bis zu zwei Sekunden für mich, und die zehn-Millionen-Fall zu einem viel mehr überschaubar 68 Sekunden.Diese version ist wie folgt:
(a): Alle timings sind fertig mit der inneren
printf
auskommentiert, so dass I/O nicht verzerren die zahlen.d
ist, die nicht benötigte (es gibt nur eined
die Arbeit, nachdem alle), und Sie können zu verhängen, ein, um über die Bedingungen (sprich Erhöhung), so dass Sie nur zu betrachten jede multiset mal lieber als jede permutation. [Sie müssen überprüfen, um zu sehen, welche Bedingungen sind gleich, die richtige Zahl zu addieren, natürlich.] Dies brachte die 10^6 Fall bis hinab zu 0,9 s für mich und die 10^7 Gehäuse nach unten, um die 28s.d
war das eine echte Verbesserung.Scheint es, als ob alle ganzen zahlen können durch eine solche Kombination:
usw.
Da habe ich einige der ersten arbeiten in meinem Kopf, ich dachte, es wäre nur der perfekte Quadrate, die hatte mehr als 1 mögliche Lösung. Jedoch nach der Liste heraus, es scheint mir, es ist nicht offensichtlich, um Sie. Ich dachte jedoch, dass ein Algorithmus, den ich denke, ist am besten geeignet für diese situation:
Das wichtigste ist, zu verwenden ein 4-Tupel (a, b, c, d). In jedem 4-Tupel, die eine Lösung a^2 + b^2 + c^2 + d^2 = n, setzen wir uns eine Einschränkung, die eine ist immer die größte der 4, b ist weiter, und so weiter und so Fort wie:
Beachten Sie auch, dass a^2 kann nicht kleiner als n/4, da sonst die Summe der Quadrate kleiner sein als n.
Dann der Algorithmus ist:
In diesem Punkt, den wir ausgewählt haben, eine bestimmte, und sind nun auf der Suche bei der überbrückung der Lücke von a^2 auf n, d.h. (n - a^2)
und so weiter und so Fort. Also ist der gesamte Algorithmus sieht dann etwa so aus:
Den Stufen 3b und 5b, die ich benutze (n - a^2)/3, (n - a^2 - b^2)/2. Wir teilen durch 3 oder 2, beziehungsweise, da die Anzahl der Werte in einem Tupel noch nicht 'behoben'.
Beispiel:
tun dies auf n = 12:
Dies sind nur zwei mögliche Tupel - hey presto!
nebffa hat eine großartige Antwort. ein Vorschlag:
max_c und max_d verbessert werden kann in der gleichen Weise.
Hier ist ein Versuch:
nun das problem ist zu finden, die 4 zahlen aus dem array Summe(a, b,c,d) = N;
Können wir eine Schleife aus nr-down-nr/2 und berechnen r = N - S[a];
die Frage ist nun, zu finden, 3 zahlen von S die Summe(b,c,d) = r = N -S[a];
hier ist der code:
Laufzeit ist
O(sqare_root(N)^3)
.Hier ist das test-Ergebnis die Ausführung von java auf meiner VM (Zeit in Millisekunden, das Ergebnis ist# total Anzahl der gültigen Kombination, Zeit-1 mit Ausdruck, Zeit2, ohne Ausdruck):