kleines Rätsel mit Schleifen lösen.
-
glaube da gibts wohl noch ne 4er-kelleretagenwohnung.
-
So tach nochmal. Ich hats damals nochmal probiert, jedoch auf anhieb trotzdem net hingekriegt, da diese Aufgabe bei uns eher als Zusatzaufgabe reinkam, für die, die meist was schneller fertig waren war mir die Aufgabe auch nicht so wichtig. Hab mich dann gestern aus Langeweile nochmal drangesetzt, so dass ich zumindest an eine Lösung komm, via 16 Schleifen und continue, einige größer und kleiner Sachen wollte noch nicht so ganz, wegen falscher Reihenfolge aber nun läufts und sieht wie folgt aus:
//------------------------------------------------------------------------------ #include <iostream.h> #include <conio.h> //------------------------------------------------------------------------------ void main() { int a, b, c ,d; int e, f, g, h; int i, j, k, l; int m, n, o, p; for (b = 3;b <=15 ;b++) { if (b == 4 || b == 9) continue; for (c = 3;c <=15 ;c++) { if (c == 4 || c == 9 || c == b) continue; for (f = 3;f <=15 ;f++) { if (f == 4 || f == 9 || f == b || f == c) continue; for (i = 2;i <=14 ;i++) { if (i == 4 || i == 9 || i == b || i == c || i == f) continue; for (l = 2;l <=13 ;l++) { if (l == 4 || l == 9 || l == b || l == c || l == f || l == i) continue; for (k = 3;k <=14 ;k++) { if (k == 4 || k == 9 || k <= l || k == b || k == c || k == f || k == i || k == l) continue; for (j = 6;j <=15 ;j++) { if (j == 9 || j <= k || j <= i || j == b || j == c || j == f || j == i || j == l) continue; for (e = 3;e <=15 ;e++) { if (e == 4 || e == 9 || e == b || e == c || e == f || e == i || e == l || e == k || e == j) continue; for (g = 3;g <=14 ;g++) { if (g == 4 || g == 9 || g == b || g == c || g == f || g == i || g == l || g == k || g == j || g == e) continue; for (h = 5;h <=15 ;h++) { if (h == 9 || h <= g || h == b || h == c || h == f || h == i || h == l || h == k || h == j || h == e) continue; for (a = 4;a <=16 ;a++) { if (a != 4 && a != 9 && a != 16 || a <= e) continue; for (d = 1;d <=16 ;d++) { if (d != 1 && d != 4 && d != 9 && d != 16 || d == a) continue; for (m = 1;m <=16 ;m++) { if (m != 1 && m != 4 && m != 9 && m != 16 || m == a || m == d) continue; for (n = 3;n <=14 ;n++) { if (n == 4 || n == 9 || n <= m || n == b || n == c || n == f || n == i || n == l || n == k || n == j || n == e || n == g || n == h) continue; for (o = 5;o <=15 ;o++) { if (o == 9 || o <= n || o == b || o == c || o == f || o == i || o == l || o == k || o == j || o == e || o == g || o == h || o == n) continue; for (p = 9;p <=16 ;p++) { if (p != 9 && p != 16 || p <= o || p == a || p == d || p == m) continue; if (a > e && h > g && j > i && j > k && k > l&& n * o == c + d && i + j == k + l && e * f == g + h) { cout << "A: " << a << endl; cout << "B: " << b << endl; cout << "C: " << c << endl; cout << "D: " << d << endl; cout << "E: " << e << endl; cout << "F: " << f << endl; cout << "G: " << g << endl; cout << "H: " << h << endl; cout << "I: " << i << endl; cout << "J: " << j << endl; cout << "K: " << k << endl; cout << "L: " << l << endl; cout << "M: " << m << endl; cout << "N: " << n << endl; cout << "O: " << o << endl; cout << "P: " << p << endl; cout << endl; } } } } } } } } } } } } } } } } } getch(); }Jedoch dauerts immernoch seine 30-40 Sekunden, was immernoch etwas lang ist. Gibts da noch Tips zum optimieren bzw. generelle Änderungen? Arrays hatten wir noch nicht und sollen daher auch nicht genutzt werden, sprich stumpf for, if, continue. Mein Lehrer meinte jedoch damals, dass man normalerweise unter 5 Sekunden sein Ergebnis haben sollte. Ich hab schon hier und da ein wenig rumgespielt und die Schleifen nur bis 15 oder 14 zählen lassen, da z.B die 16 als Quadratzahl fix in den Ecken ist und wenn ich dann was wie h > g hab ist ja klar das h maximal 15 sein könnte und g maximal 14, genauso andersrum beim hochzählen, dennoch brauchs eben doch noch was lang.
-
Hau mal die
if (a > e && h > g && j > i && j > k && k > l&& n * o == c + d && i + j == k + l && e * f == g + h)
soweit möglich weiter hoch und mach gegebenenfalls doppelcontinues.
ich machs mal mit
a > efor (a = 4;a <=16 ;a++) { if (a != 4 && a != 9 && a != 16 || a <= e) continue; if (a <= e) continue; for (d = 1;d <=16 ;d++) {edit: uups, haste ja schon oben. ich sehe deutlich ein "|| a <= e".
dann war's unten gar nicht mehr nötig.
-
Velicity schrieb:
...Gibts da noch Tips zum optimieren bzw. generelle Änderungen?...
Du bekommst die Lösung praktisch sofort ausgespuckt wenn du die Aufgabenstellung mehr einbeziehst.
Wie oben schon erwähnt lässt sich die 16! durch Beachten der Forderung mit den Quadratzahlen in den Ecken sofort auf 4! * 12! runterbrechen. Da in Zimmer a wegen der Bedingung a > e keine 1 sein kann, sogar auf noch weniger.
Außerdem folgt aus der Aufgabenstellung sofort, dass die 2 nur in die Zimmer i und l einziehen könnte, denn die 1 ist die einzige Zahl, die kleiner als 2 ist, sie befindet sich aber in einer der Ecken.
Folgender Ansatz funktioniert recht flott:
int main(){ int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p; // Fall 1, die 2 ist im Zimmer i i=2; for (a = 2; a < 5; ++a) // da in Zimmer a keine 1 sein kann beginnt es bei 2 { for(d = 1; d < 5; ++d) // Ecke d { if (d == a) continue; for (m = 1; m < 5; ++m) // Ecke m { if (m == a || m == d) continue; for (p = 1; p < 5; ++p) // Ecke p { if(p == a || p == d || p == m) continue; for (e = 3; e < 16; e++) { if (e > a*a || e==a*a || e==d*d || e==p*p || e==m*m) continue; // da die Schleifen für die Ecken a bis p von 1 bzw. 2 bis 4 Laufen muss // für den Vergleiche auf Gleichheit natürlich das Quadrat (1*1, 2*2, ...) genommen werden. // hier kommen die restlichen Schleifen mit den geforderten Bedingungen hin // Also z.B. : for (j = 3; j < 16; ++j) // ab 3 weil 1 in einer der Ecken liegen muss und 2 bereits vergeben ist { if (j < i || j == e || j==a*a || j==d*d || j==p*p || j==m*m ) continue; // ... } } } } } } // Fall 2, die 2 ist im Zimmer l l = 2 // hier dann nochmal alles wie oben, alledings wird i jetzt durchlaufen und l bleibt fest return 0; }Lauzeit: Nicht spürbar.
Mann könnte auf die Fallunterscheidung verzichten und die Bedingung "2 muss in den ersten Stock" innerhalb der Schleifen verarbeiten. Hab es zwar nicht ausprobiert, aber ich würde es auch noch recht flott einschätzen.
Der entscheidende Faktor ist die Reduzierung von 16! auf 4! * 12! also von 20.922.789.888.000 auf 11.496.038.400 zu betrachtende Fälle.
-
schlurf schrieb:
Der entscheidende Faktor ist die Reduzierung von 16! auf 4! * 12! also von 20.922.789.888.000 auf 11.496.038.400 zu betrachtende Fälle.
Also Umsortieren, daß die Schleifen a d m p außen sind.
schlurf schrieb:
Außerdem folgt aus der Aufgabenstellung sofort, dass die 2 nur in die Zimmer i und l einziehen könnte, denn die 1 ist die einzige Zahl, die kleiner als 2 ist, sie befindet sich aber in einer der Ecken.
Also Umsortieren, daß die Schleifen i l ganz außen sind. Code-Duplikation tut nicht not.
-
volkard schrieb:
Also Umsortieren, daß die Schleifen a d m p außen sind.
Yup. Wobei meiner Meinung nach auch die Schleifendurchläufe von 1 bis 16 auf 1 bis 4 reduziert weren müssten. Hab es aber so nicht getestet.
volkard schrieb:
Also Umsortieren, daß die Schleifen i l ganz außen sind. Code-Duplikation tut nicht not.
Yup. Wobei ich glaub, dass dieser Teil für die Laufzeit nicht unbedingt so entscheidend ist. Hab das aber ebenfalls nicht getestet.
Vielleicht macht sich der Threadstarter ja die Mühe und probiert ein paar Varianten aus. Also, einfach, wie du gesagt hast, umsortieren und testen wie die Laufzeit sich verhält. Vielleicht reicht das auch schon. Mal sehen.
-
schlurf schrieb:
Vielleicht macht sich der Threadstarter ja die Mühe und probiert ein paar Varianten aus. Also, einfach, wie du gesagt hast, umsortieren und testen wie die Laufzeit sich verhält. Vielleicht reicht das auch schon. Mal sehen.
Das wäre toll.
Dazu müßte er nur die Monsterif (j < i || j == e || j==a*a || j==d*d || j==p*p || j==m*m ) continue;mit dem großen Schwert in Stücke hauen
if (j < i ) continue; if (j == e ) continue; if (j==a*a ) continue; if (j==d*d ) continue; if (j==p*p ) continue; if (j==m*m ) continue;und die Variablen lokaler machen
for (int d = 1;d <=16 ;d++)und könnte dann frei Zeilen verschieben und wenn's der Compiler frißt, ist's auch inhaltlich ok. Verschieben mit dem Ziel, die stärksten Bedingungen so weit wie möglich nach oben zu kriegen.
-
" for( L::const_iterator i = zahlen.begin(); i!= zahlen.end(); ++i ) "
Mein Dev-C++ entdeckt bei dem oben genannten Code einen Fehler!
Da ich auch noch ein anfänger bin wollte ich fragen, was der Fehler ist,
und was das richtige Quellcode wäre!
Bitte um Antwort!
Gruß
-
masterx schrieb:
" for( L::const_iterator i = zahlen.begin(); i!= zahlen.end(); ++i ) "
Mein Dev-C++ entdeckt bei dem oben genannten Code einen Fehler!
Da ich auch noch ein anfänger bin wollte ich fragen, was der Fehler ist,
und was das richtige Quellcode wäre!Bitte um Antwort!
Gruß
Was ist der Fehler? Was willst du überhaupt machen? Was hat das mit diesem Thread zu tun?
Fragen über Fragen...
-
Und wechsle wenn möglich auf eine moderne Entwicklungsumgebung wie Code::Blocks oder Microsoft Visual C++. Dev-C++ ist veraltet und wird nicht mehr weiterentwickelt.
-
masterx schrieb:
" for( L::const_iterator i = zahlen.begin(); i!= zahlen.end(); ++i ) "
Mein Dev-C++ entdeckt bei dem oben genannten Code einen Fehler!
Da ich auch noch ein anfänger bin wollte ich fragen, was der Fehler ist,
und was das richtige Quellcode wäre!Bitte um Antwort!
Gruß
Und warum suchst du dir als Anfänger einen so komplexen Quellcode aus?
