Summe von a+b+c=1000 -> Lösungen in Arrays speichern
-
volkard schrieb:
C_Newbe schrieb:
Die Aufgabe, die ich zu versuchen löse lautet:
Ein Pythagoras-Triplet ist eine Menge von drei natürlichen Zahlen, für die gilt:
a < b < c
a² + b² = c²Zum Beispiel: 3² + 4² = 9 + 16 = 25 = 5².
Finde nun ein Pythagoras-Triplet, das zudem a + b + c = 1000 erfüllt und gib das Produkt abc an.
Ok. Machs Stück für Stück bitte. Immer das notwendigste zuerst und sonst das leichteste.
> Finde nun ein Pythagoras-Triplet, das zudem a + b + c = 1000
Ok, a, b und c sind alle zwischen 1 und 1000. (Ich vermute, 0 war nicht eine natürliche Zahl in der Aufgabenstellung.)
Das machen wir mal...#include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { int a, b, c; for (a=1;a<1000;a++){ for(b=1;b<1000;b++){ for(c=1;c<1000;c++){ printf("%d %d %d\n",a,b,c); } } } return EXIT_SUCCESS; }
Klappt doch!
Laufzeit ungeheuer lange…Außerdem lese ich
> a < b < c
Alsoint main(int argc, char** argv) { int a, b, c; for (a=1;a<1000;a++){ for(b=a+1;b<1000;b++){ for(c=b+1;c<1000;c++){ printf("%d %d %d\n",a,b,c); } } } return EXIT_SUCCESS; }
Laufzeit schon fast abwartbar, vielleicht 10 Minuten.
Jetzt noch schnell
> a + b + c = 1000
einbauen…#include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { int a, b, c; for (a=1;a<1000;a++){ for(b=a+1;b<1000;b++){ for(c=b+1;c<1000;c++){ if(a+b+c==1000){ printf("%d %d %d\n",a,b,c); } } } } return EXIT_SUCCESS; }
Uups, Laufzeit von 0.5 Sekunden.
Und jetzt die Hauptbedingung
> a² + b² = c²
einbauen…#include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { int a, b, c; for (a=1;a<1000;a++){ for(b=a+1;b<1000;b++){ for(c=b+1;c<1000;c++){ if(a+b+c==1000){ if(a*a+b*b==c*c){ printf("%d %d %d\n",a,b,c); } } } } } return EXIT_SUCCESS; }
Fertig. Laufzeit 0.3 Sekunden.
Und dann noch einen Trick:
Haste a und b schon, dann kannste doch c ausrechnen! c=1000-a-b. Da bin ich sichi.#include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { int a, b, c; for (a=1;a<1000;a++){ for(b=a+1;b<1000;b++){ int c=1000-a-b; if(c>=1){ if(a+b+c==1000){ if(a*a+b*b==c*c){ printf("%d %d %d\n",a,b,c); } } } } } return EXIT_SUCCESS; }
Laufzeit 0.003 Sekunden.
Löse stets nur ein möglichst kleines Teilproblem und nähere Dich dem Ziel. Nach jedem Teilproblem muss die main() lauffähig sein und was anzeigen, nämlich ob das Teilproblem fein gelöst ist.
Ahhhh, danke Volker, aber ich darf das nicht sehen, ich muss das selbst lösen, sonst kommt der Aha Effekt nicht
Aber super, da kann ich dann die Lösung einsehen, wenn ich das Problem gelöst bekommen habe.
Ich konnte ein bisschen schon herauslesen, dass ich in Teilproblemen rangehen soll. Genau das war meine bewusste Intention :). Die Bedingung, dass die Variablen 1000 in der Summe ergeben müssen ist der Ausgangspunkt dafür, dass ich die Anzahl der Variablen überhaupt eingrenzen kann.
Ich male hier auch ernsthaft alles auf Papier auf und versuche die Probleme teilweise zu lösen, wie du sagst.
Was ist denn das Problem der VLA und gibt es anfängertaugliche Möglichkeiten diese zu umgehen?
EDIT:
okay habe mir die Lösung jetzt doch angesehen. Meine Herangehensweise wäre völlig anders gewesen. Ich hätte das in Teilfunktionen zerlegt, sodass jede etwas anderes macht. Du hast das eben sehr gut in die ausgehenden Zeilen integriert. Die Prüfung für die größer kleiner Verhältnisse hatte ich in einer Extra Funktion bereits angefangen.int solutionsA=varPos; varPos=0; //varPos ist bei mir der Zähler für die Arrays while (varpos != solutionsA){ if (a>b && a>c && pow(a,2) == pow(b,2) + pow(c,2)) if (b>c %% b>a && pow(b,2) == pow(a,2) + pow(c,2)) if (c>a %% c>b && pow(c,2) == pow(a,2) + pow(b,2))
EDIT EDIT:
Im letzten Code Post werden die a, b und c noch gegen die Arrays ausgetauscht. Ich re-edit wenn ich es geschrieben habe.
-
C_Newbe schrieb:
Ahhhh, danke Volker, aber ich darf das nicht sehen, ich muss das selbst lösen, sonst kommt der Aha Effekt nicht
Keine Bange, den Aha-Effekt kriegste auch, wenn Du mein Vorgehen sorgfältig anschaust und mit diesem Vorgehen weitere Euler-Probleme löst.
C_Newbe schrieb:
Ich male hier auch ernsthaft alles auf Papier auf
Genau!
Erst auf Papier lösen und dann proggern hilft bei Euler unglaublich viel.Habe neulich mit Azubis bis Euler25 gespielt und es war eine Freude.
Nimm kein Array! Kein VLA und kein SLA und kein DLA. Als Mensch auf Papier würdest Du doch auch nicht erst alle 1000*1000*1000=1000000000 Kombinationen aufschreiben und dafür 75 Kilotonnen Papier und 1.13 Millionen Kugelschreiberminen kaufen. Ich gehe davon aus, daß Du Dir die ca 200000€ dafür leisten kannst. Aber die ca 57 Jahre, erst das Array per Hand zu füllen, um dann doch bloß eine Zahl als Ergebnis zu haben. Das machste nicht, gell?
-
C_Newbe schrieb:
Ahhhh, danke Volker, aber ich darf das nicht sehen, ich muss das selbst lösen, sonst kommt der Aha Effekt nicht
Lies es dir unbedingt nochmal durch.
Da du keine Ahnung hast (nicht böse gemeint), wirst du nur sehr schwer auf diese Optimierungen kommen.
Darum von Profis lernen.pow
hört sich erstmal gut an, ist aber gar nicht nötig, da eine Integermultiplikation meist schneller ist.
Zudem rechnetpow
mit Fließkommazahlen, die für dein Problem auch nicht optimal sind.
-
volkard schrieb:
C_Newbe schrieb:
Ahhhh, danke Volker, aber ich darf das nicht sehen, ich muss das selbst lösen, sonst kommt der Aha Effekt nicht
Keine Bange, den Aha-Effekt kriegste auch, wenn Du mein Vorgehen sorgfältig anschaust und mit diesem Vorgehen weitere Euler-Probleme löst.
C_Newbe schrieb:
Ich male hier auch ernsthaft alles auf Papier auf
Genau!
Erst auf Papier lösen und dann proggern hilft bei Euler unglaublich viel.Habe neulich mit Azubis bis Euler25 gespielt und es war eine Freude.
Nimm kein Array! Kein VLA und kein SLA und kein DLA. Als Mensch auf Papier würdest Du doch auch nicht erst alle 1000*1000*1000=1000000000 Kombinationen aufschreiben und dafür 75 Kilotonnen Papier und 1.13 Millionen Kugelschreiberminen kaufen. Ich gehe davon aus, daß Du Dir die ca 200000€ dafür leisten kannst. Aber die ca 57 Jahre, erst das Array per Hand zu füllen, um dann doch bloß eine Zahl als Ergebnis zu haben. Das machste nicht, gell?
Haha! Du hast da absolut recht. Deine Variante ist die deutlich bessere, das habe ich schon beim Lesen der Antwort gesehen. Es werden alle Prüfungen im dafür vorgesehenen Schritt direkt durchgeführt. Ich würde im Prinzip einiges doppelt und dreifach prüfen.
Ich werde trotzdem noch versuchen meine Idee fortzuführen, einfach um zu sehen ob ich es mit meinem Ansatz hinbekommen hätte ein Ergebnis zu erhalten.
Was mich noch interessieren würde warum Arrays im Zusammenhang solcher "Euler" Probleme (muss ich dann erst noch recherchieren was das genau ist) ungünstig sind, oder was an den VLAs so problematisch ist.
Lies es dir unbedingt nochmal durch.
Da du keine Ahnung hast (nicht böse gemeint), wirst du nur sehr schwer auf diese Optimierungen kommen.
Darum von Profis lernen.pow hört sich erstmal gut an, ist aber gar nicht nötig, da eine Integermultiplikation meist schneller ist.
Zudem rechnet pow mit Fließkommazahlen, die für dein Problem auch nicht optimal sind.Ja genau, das habe ich auch gemacht, und danke für die schon sehr hilfreichen Hinweise. Ich versuche alles aufzusaugen.
-
C_Newbe schrieb:
Ich konnte ein bisschen schon herauslesen, dass ich in Teilproblemen rangehen soll.
Jupp. Und zwar darfst und sollst Du da in aller Brutalität vorgehen und wirklich nur im Schneckentempo allerkleinste Teilprobleme lösen. Eine Zeile ändern, compilieren, testen. Eine Zeile ändern, compilieren, testen. Eine Zeile ändern, compilieren, testen…
C_Newbe schrieb:
Genau das war meine bewusste Intention :). Die Bedingung, dass die Variablen 1000 in der Summe ergeben müssen ist der Ausgangspunkt dafür, dass ich die Anzahl der Variablen überhaupt eingrenzen kann.
Jo. Erst damit war es möglich, die drei Schleifen zu bauen. Wobei auch die nicht auf einen Schlag passieren müssen. Man kann gerne auch zuerst nur mal die a-Schleife bauen und testen und dann erst die b-Schleife reinfummeln und testen. Und dann die c-Schleife.
Das kostet ja quasi keine Programmierzeitzeit, die zusätzlichen Tests zu machen. Aber wehe, beim Schreiben der drei Zeilen auf einmal wäre was schiefgegangen… Fehlersuche, Debugger, Rätselraten, Forumposten, Abwarten, und alles nur für zum Beispiel ein ungeschicktes Semikolen an der falschen Stelle, was man übersieht.C_Newbe schrieb:
okay habe mir die Lösung jetzt doch angesehen. Meine Herangehensweise wäre völlig anders gewesen. Ich hätte das in Teilfunktionen zerlegt, sodass jede etwas anderes macht. Du hast das eben sehr gut in die ausgehenden Zeilen integriert. Die Prüfung für die größer kleiner Verhältnisse hatte ich in einer Extra Funktion bereits angefangen.
Ja, guter Punkt. Manche Probleme werden gerne sorum gelöst und manche Probleme werden gerne andersrum gelöst.
Löse einfach alle Probleme, bei denen Du nicht sicher bist in beiden Richtungen. So für den Aha-Effekt.C_Newbe schrieb:
Ich re-edit wenn ich es geschrieben habe.
Mach das nicht. Der Server verkraftet ein paar mehr Postings auch. Ich und vermutlich noch ein paar mehr Leser gehen immer auf die Forumsseite "Neue Beiträge seit dem letzten Besuch anzeigen" und würden Deine Änderung niemals sehen.
-
Ich merke auch gerade, dass ich dann die ganze Arrays neu durchkämmen müsste um die dann in einem neuen Array zu speichern. Das ist alles sehr aufwendig und mir passieren auch Syntaxfehler, die ein Vorankommen gerade grauenhaft machen.
Ich werde euch zur Liebe das nicht posten, was ich da gerade zusammengecoded habe. Die Hinweise waren aber schon Mal sehr hilfreich. Ich werde mich später nochmal ran setzen und mit dem Gedanken alles innerhalb der for-Schleifen zu lösen probieren und mich später anderen Aufgaben widmen.
Zu aller Letzt noch, warum sind die VLAs verpönt bzw. was ist problematisch an denen? Das soll meine letzte Lektion im Zusammenhang mit dieser Aufgabe sein.
-
C_Newbe schrieb:
Ich merke auch gerade, dass ich dann die ganze Arrays neu durchkämmen müsste um die dann in einem neuen Array zu speichern. Das ist alles sehr aufwendig und mir passieren auch Syntaxfehler, die ein Vorankommen gerade grauenhaft machen.
Kein Problem, auch das übernehme ich gerne. Inklusive der Fehler.
Ein Array auf dem Stack ist üblicherweise maximal 1 Megabyte groß oder maximal 4 Megabyte groß. Hier brauchen wir viel viel mehr. Deswegen muss es auf dem Heap sein. Das mache ich mit malloc()/free().
Zur Übung mache ich mal die einigermaßen sinnvollen Tripel mit a<b<c und a+b+c==1000 in die Arrays rein und werte danach erst die Tripel aus.
#include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { int* solA=malloc(1000000000*sizeof(int)); int* solB=malloc(1000000000*sizeof(int)); int* solC=malloc(1000000000*sizeof(int)); int varPos=0; int a, b, c, i; for (a=1;a<1000;a++){ for(b=a+1;b<1000;b++){ for(c=b+1;c<1000;c++){ if(a+b+c==1000){ solA[varPos]=a; solB[varPos]=b; solC[varPos]=c; varPos++; } } } } for(i=0;i<varPos;i++){ if(solA[i]*solA[i]+solB[i]+solB[i]==solC[i]*solC[i]){ printf("%d %d %d\n",solA[i],solB[i],solC[i]); } } free(solA); free(solB); free(solC); return EXIT_SUCCESS; }
C_Newbe schrieb:
Ich werde euch zur Liebe das nicht posten, was ich da gerade zusammengecoded habe.
Das ist nett. Aber ich hab's verkackt!!!
Die total simple Umsetzung des Programms in ein ein wenig umständlicheres ist nicht geglückt. Es zeigt das Ergebnis nicht an. Ich kann draufstarren wie ich will. Alle Zeilen stimmen. Kacke. Debuggen ist ätzend. Und ich wüßte auch nicht, wie ich so ein Programm debuggen sollte, alle 1000000000 Kombinationen anschauen und aufmerksam bemerken, wenn was falsch wird.
-
Zeile 24:
if(solA[i]*solA[i]+solB[i]*solB[i]==solC[i]*solC[i]){ // ^
-
Also ich weiß mittlerweile wo der Hund begraben liegt und mit dem Ansatz, den ich verfolgt habe bekomme ich kein Ergebnis zu Stande. Ich poste trotzdem noch mal abschließend das, was ich unter dem Strich als selbst entwickelten Gedanken entworfen hatte.
Funktioniert aber nicht (alleine der Anfang erzeugt immer noch diesen Fehler) _
#include <stdio.h> #include <stdlib.h> #include <math.h> /* * */ int main(int argc, char** argv) { int a, b, c; int varPos = 1000; int solA[varPos], solB[varPos], solC[varPos]; varPos = 0; for (a=0;a<1000;a++){ for(b=0;b<1000;b++){ for(c=0;c<1000;c++){ if (a+b+c==1000){ solA[varPos] = a; solB[varPos] = b; solC[varPos] = c; varPos++; } } } } int solutionsA=varPos; varPos=0; while (varPos != solutionsA){ if (solA[varPos]>solB[varPos] && solA[varPos]>solC[varPos] && //a is biggest pow(solA[varPos],2) == pow(solB[varPos],2) + pow(solC[varPos],2)){ printf ("%d,&d,%d\n", solA[varPos], solB[varPos], solC[varPos]); } else if (solB[varPos]>solC[varPos] %% solB[varPos]>solA[varPos] && //b is biggest pow(solB[varPos],2) == pow(solA[varPos],2) + pow(solC[varPos],2)){ printf ("%d,&d,%d\n", solA[varPos], solB[varPos], solC[varPos]); } else if (solC[varPos]>solA[varPos] %% solC[varPos]>solB[varPos] && pow(solC[varPos],2) == pow(solA[varPos],2) + pow(solB[varPos],2)){ } varPos++; } return (EXIT_SUCCESS); }
-
C_Newbe schrieb:
Also ich weiß mittlerweile wo der Hund begraben liegt und mit dem Ansatz, den ich verfolgt habe bekomme ich kein Ergebnis zu Stande. Ich poste trotzdem noch mal abschließend das, was ich unter dem Strich als selbst entwickelten Gedanken entworfen hatte.
Funktioniert aber nicht (alleine der Anfang erzeugt immer noch diesen Fehler) _
Ist dir klar, das 1000 Werte im Array nicht reichen?
Alleine für a = 0 bekommst du 999 Einträge zusammen.C überprüft auch nicht, ob die Arraygrenzen eingehalten werden.
Das musst du selber machen.
-
DirkB schrieb:
C_Newbe schrieb:
Also ich weiß mittlerweile wo der Hund begraben liegt und mit dem Ansatz, den ich verfolgt habe bekomme ich kein Ergebnis zu Stande. Ich poste trotzdem noch mal abschließend das, was ich unter dem Strich als selbst entwickelten Gedanken entworfen hatte.
Funktioniert aber nicht (alleine der Anfang erzeugt immer noch diesen Fehler) _
Ist dir klar, das 1000 Werte im Array nicht reichen?
Alleine für a = 0 bekommst du 999 Einträge zusammen.C überprüft auch nicht, ob die Arraygrenzen eingehalten werden.
Das musst du selber machen.Aber ist es nicht so, dass a höchstens 1000 Werte annehmen kann, und dass b höchstens 1000 Werte annehmen kann, und dass c höchstens 1000 Werte annehmen kann?
-
Hast du den geposteten Code überhaupt mal versucht zu kompilieren? Bei mir kommt da:
c_newbe.c:31:63: warning: data argument not used by format string [-Wformat-extra-args] printf ("%d,&d,%d\n", solA[varPos], solB[varPos], solC[varPos]); ~~~~~~~~~~~~ ^ c_newbe.c:33:45: error: expected expression else if (solB[varPos]>solC[varPos] %% solB[varPos]>solA[varPos] && //b is biggest ^ c_newbe.c:35:63: warning: data argument not used by format string [-Wformat-extra-args] printf ("%d,&d,%d\n", solA[varPos], solB[varPos], solC[varPos]); ~~~~~~~~~~~~ ^ c_newbe.c:37:45: error: expected expression else if (solC[varPos]>solA[varPos] %% solC[varPos]>solB[varPos] && ^
Also: dein printf-String ist falsch und was soll das %% bedeuten?
Zur anderen Frage mit maximal 1000:
hast du mal darüber nachgedacht, dass ein Wert auch mehrfach vorkommen kann? Zum Beispiel 44*44+117*117 = 125*125 und auch 44*44+483*483=485*485. Hier kommt die 44 also doppelt vor.
-
wob schrieb:
Hast du den geposteten Code überhaupt mal versucht zu kompilieren? Bei mir kommt da:
c_newbe.c:31:63: warning: data argument not used by format string [-Wformat-extra-args] printf ("%d,&d,%d\n", solA[varPos], solB[varPos], solC[varPos]); ~~~~~~~~~~~~ ^ c_newbe.c:33:45: error: expected expression else if (solB[varPos]>solC[varPos] %% solB[varPos]>solA[varPos] && //b is biggest ^ c_newbe.c:35:63: warning: data argument not used by format string [-Wformat-extra-args] printf ("%d,&d,%d\n", solA[varPos], solB[varPos], solC[varPos]); ~~~~~~~~~~~~ ^ c_newbe.c:37:45: error: expected expression else if (solC[varPos]>solA[varPos] %% solC[varPos]>solB[varPos] && ^
Also: dein printf-String ist falsch und was soll das %% bedeuten?
Zur anderen Frage mit maximal 1000:
hast du mal darüber nachgedacht, dass ein Wert auch mehrfach vorkommen kann? Zum Beispiel 44*44+117*117 = 125*125 und auch 44*44+483*483=485*485. Hier kommt die 44 also doppelt vor.Super Danke für die Hinweise, ja jetzt habe ich die Fehler entdecken können, das doppelte %% soll eigentlich ein && sein, das habe ich gestern einfach nicht mehr entdecken können. Ich habe eine halbe Ewigkeit auf diese Zeilen geguckt um den Fehler zu finden. War wohl schon etwas spät.
Dass a, b und c einen Wert mehrmals annehmen können, daran hatte ich nicht gedacht und ich muss zugegeben nochmal in Ruhe darüber nachdenken um das zu verstehen. Ich werde mir das mal anschauen. Alles super wertvolle Hinweise für mich, danke sehr!
Korrektur der while Schleife
while (varPos != solutionsA){ if (solA[varPos]>solB[varPos] && solA[varPos]>solC[varPos] && //a is biggest pow(solA[varPos],2) == pow(solB[varPos],2) + pow(solC[varPos],2)){ printf ("%d,%d,%d\n", solA[varPos], solB[varPos], solC[varPos]); } else if (solB[varPos]>solC[varPos] && solB[varPos]>solA[varPos] && //b is biggest pow(solB[varPos],2) == pow(solA[varPos],2) + pow(solC[varPos],2)){ printf ("%d,%d,%d\n", solA[varPos], solB[varPos], solC[varPos]); } else if (solC[varPos]>solA[varPos] && solC[varPos]>solB[varPos] && pow(solC[varPos],2) == pow(solA[varPos],2) + pow(solB[varPos],2)){ printf ("%d,%d,%d\n", solA[varPos], solB[varPos], solC[varPos]); } varPos++; }
-
wob schrieb:
Zur anderen Frage mit maximal 1000:
hast du mal darüber nachgedacht, dass ein Wert auch mehrfach vorkommen kann? Zum Beispiel 44*44+117*117 = 125*125 und auch 44*44+483*483=485*485. Hier kommt die 44 also doppelt vor.Es ist ja noch schlimmer, da ja für die Einträge im Array nur die (normale) Summe genommen wird.
Das kommt dann schon bei a = 0 glatt 999 mal vor (1+999;2+998;....998+2;999+1)
-
DirkB schrieb:
wob schrieb:
Zur anderen Frage mit maximal 1000:
hast du mal darüber nachgedacht, dass ein Wert auch mehrfach vorkommen kann? Zum Beispiel 44*44+117*117 = 125*125 und auch 44*44+483*483=485*485. Hier kommt die 44 also doppelt vor.Es ist ja noch schlimmer, da ja für die Einträge im Array nur die (normale) Summe genommen wird.
Das kommt dann schon bei a = 0 glatt 999 mal vor (1+999;2+998;....998+2;999+1)Okay ich habe es verstanden also brauche ich thereotisch gesehen in meinem Code 1000^3 verschiedene Array Positionen, um meine Lösungen alle zu speichern. Ja das ist total ineffizient.
Naja gut, ich konnte wenigstens meine Idee zu Ende schreiben, und jetzt ist sie syntaktisch auch in Ordnung. Nur der Logikfehler mit den Arrays fällt mir gerade auf die Füße, aber ich habe schon Mal was gutes gelernt. Danke für den Input!
-
Mit Arrays wird das schwierig, da du dafür knapp 12 GByte brauchst.
Beishort
stattint
wären es noch 6 GByte.Um 20:01:09 10.05.2016
volkard schrieb:
Ein Array auf dem Stack ist üblicherweise maximal 1 Megabyte groß oder maximal 4 Megabyte groß. Hier brauchen wir viel viel mehr. Deswegen muss es auf dem Heap sein. Das mache ich mit malloc()/free().
-
Da muss ich wohl für mein tolles Programm Arbeitsspeicher aufrüsten
Kleiner Spaß am Rande, ich versuche Volkers Ansatz selbst nachzuentwickeln. Danach widme ich mich neuen Aufgaben. Danke für den ganzen tollen Input