kleines Rätsel mit Schleifen lösen.
-
volkard schrieb:
Manchmal bringt das Beschleunigungen von 3000Jahre->0.1Sekunde.
Ich habs mal überschlagen.
Mit 16! Möglichkeiten durchtesten wäre mein PC maximal 29 Stunden beschäftigt (habe großzügig aufgerundet).Von daher heißts geduldig sein
-
Aus der Aufgabenstellung kann man die 16! praktisch sofort auf 4! * 12! runterbrechen. Ein paar Stunden spart das auch.
-
Ich hab mal das Machen der Permutationen ohne weitere Prüfungen gebaut.
#include <iostream> using namespace std; int main() { bool belegt[17]={0}; for (int a=1;a<=16;++a) { if (belegt[a]) continue; belegt[a]=true; for (int b=1;b<=16;++b) { if (belegt[b]) continue; belegt[b]=true; for (int c=1;c<=16;++c) { if (belegt[c]) continue; belegt[c]=true; for (int d=1;d<=16;++d) { if (belegt[d]) continue; belegt[d]=true; for (int e=1;e<=16;++e) { if (belegt[e]) continue; belegt[e]=true; for (int f=1;f<=16;++f) { if (belegt[f]) continue; belegt[f]=true; for (int g=1;g<=16;++g) { if (belegt[g]) continue; belegt[g]=true; for (int h=1;h<=16;++h) { if (belegt[h]) continue; belegt[h]=true; for (int i=1;i<=16;++i) { if (belegt[i]) continue; belegt[i]=true; for (int j=1;j<=16;++j) { if (belegt[j]) continue; belegt[j]=true; for (int k=1;k<=16;++k) { if (belegt[k]) continue; belegt[k]=true; for (int l=1;l<=16;++l) { if (belegt[l]) continue; belegt[l]=true; for (int m=1;m<=16;++m) { if (belegt[m]) continue; belegt[m]=true; for (int n=1;n<=16;++n) { if (belegt[n]) continue; belegt[n]=true; for (int o=1;o<=16;++o) { if (belegt[o]) continue; belegt[o]=true; cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<' '<<f<<' '<<g<<' '<<h<<' '<<i<<' '<<j<<' '<<k<<' '<<l<<' '<<m<<' '<<n<<' '<<o<<'\n'; belegt[o]=false; } belegt[n]=false; } belegt[m]=false; } belegt[l]=false; } belegt[k]=false; } belegt[j]=false; } belegt[i]=false; } belegt[h]=false; } belegt[g]=false; } belegt[f]=false; } belegt[e]=false; } belegt[d]=false; } belegt[c]=false; } belegt[b]=false; } belegt[a]=false; } return 0; }
-
Die Bedingungen lassen sich jetzt Zwanglos reinfummeln. Einfach immer hinschreiben, sobald alle Variablen leben, die diese Bedingung braucht.
... for (int g=1;g<=16;++g) { if (belegt[g]) continue; belegt[g]=true; for (int h=1;h<=16;++h) { if (belegt[h]) continue; //Schließlich gilt: n mal o = c + d, i + j = k + l und e mal f = g + h. if (e*f!=g+h) continue; //außerdem h > g, j > i, j > k und k > l. if (g>h) continue; belegt[h]=true; for (int i=1;i<=16;++i) { if (belegt[i]) continue; belegt[i]=true; for (int j=1;j<=16;++j) { ...Das ist übrigens genau Dein Ansatz
Mein erster Ansatz war den Computer wirklich stumpf bis 16 hoch 16 hochzählen zu lassen und sofern alles erfüllt ist eine Ausgabe zu machen, jedoch hat das Programm eine scheinbar ewige Zeit gebraucht so das diese Idee wohl eher unbrauchbar war.
Der einzige Unterschied ist, daß die ganzen if-continue nicht innendrin in der p-Schleife wohnen, wo alle Variablen bekannst sind. Sondern jedes if-continue wandert so weit nach oben, wie es eben geht. Das allein beschleumigt ausreichend. Nix mit Primzahlen.
KEIN weiteres Nachdenken über wie man das Problem "logisch" angehen könnte oder Rechenzeit reduzieren könnte.Laufzeit 0.1 Sekunden.
-
volkard schrieb:
KEIN weiteres Nachdenken über wie man das Problem "logisch" angehen könnte oder Rechenzeit reduzieren könnte.
Laufzeit 0.1 Sekunden.
.. das ist sehr gut. Mein Ansatz dauert knapp eine Minute. Ich find es interessant wie man so ein Backtracking mit Rekursion programmiert. Und dann hab ich mich gefragt, wie man die ganz unterrschiedlichen Bedingungen möglichst elegant in dem Programm unterbringt. Und das möglichst so, dass man das Problem im Code auch wiederfindet.
Dabei ist dann das herausgekommen:#include <iostream> #include <iomanip> #include <map> #include <vector> #include <cmath> #include <functional> #include <boost/bind.hpp> #include <boost/function.hpp> // -- der eigentliche Backtracking-Algorithmus template< typename L, typename H, typename Out, typename C > bool fuelleHaus( const L& zahlen, H& haus, Out cur, const C& pruefer ) { assert( !zahlen.empty() ); for( L::const_iterator i = zahlen.begin(); i!= zahlen.end(); ++i ) { *cur = *i; // versuchen wir mal das ... if( pruefer( haus, cur ) ) { // ok, das geht .. Out next( cur ); // lokale Kopie; wir brauchen 'out' noch if( zahlen.size() == 1 || ++next == haus.end() ) return true; // das war schon die letzte Zahl //.. nun zum nächsten Schritt; neue Liste ohne die aktuelle Zahl *i L neueZahlen( zahlen ); L::iterator j = neueZahlen.begin(); advance( j, distance( zahlen.begin(), i ) ); neueZahlen.erase( j ); if( fuelleHaus( neueZahlen, haus, next, pruefer ) ) return true; // beim Rest hat's geklappt -> also mit ok zurück } // hat nicht geklappt -> Backtrack // *out = 0; // nicht notwendig } return false; // keine Möglickeit gefunden } class Haus { public: typedef std::vector< int > C; Haus() : m_raeume( 16 ) {} typedef std::vector< int >::iterator iterator; typedef std::vector< int >::const_iterator const_iterator; const_iterator begin() const { return m_raeume.begin(); } iterator begin() { return m_raeume.begin(); } iterator end() { return m_raeume.end(); } bool isOk( const boost::function< bool( const Haus& ) >& pred ) const { return pred( *this ); } int at( char raum ) const { const std::size_t idx( raum - 'a' ); assert( idx < m_raeume.size() ); return m_raeume[ idx ]; } bool Die2ImErstenStock() const { return find( m_raeume.begin()+8, m_raeume.begin()+12, 2 ) != m_raeume.begin()+12; } friend std::ostream& operator<<( std::ostream& out, const Haus& h ) { int sp = 1; char c = 'a'; // Raum-Kennung for( C::const_iterator i = h.m_raeume.begin(); i != h.m_raeume.end(); ++i, ++sp, ++c ) { out << c << std::setw(2) << *i << " "; if( (sp % 4) == 0 ) out << '\n'; // naechstes Stockwerk } return out; } private: C m_raeume; }; bool is_square( int x ) { const int root = int( std::sqrt( double( x ) ) ); return root * root == x; } class Pruefer { public: typedef std::vector< boost::function< bool( const Haus& ) > > Checks; Pruefer() : m_catalog() { using boost::bind; // Bem.: der Index im Katalog gibt an, wo der aktuelle Iterator 'cur' stehen mus, damit // die Prüfung ausgeführt werden kann. // -- Die Quadratzahlen wohnen in den Ecken m_catalog[ 'a' ].push_back( bind( &is_square, bind( &Haus::at, _1, 'a' ) ) ); m_catalog[ 'd' ].push_back( bind( &is_square, bind( &Haus::at, _1, 'd' ) ) ); m_catalog[ 'm' ].push_back( bind( &is_square, bind( &Haus::at, _1, 'm' ) ) ); m_catalog[ 'p' ].push_back( bind( &is_square, bind( &Haus::at, _1, 'p' ) ) ); // -- die 2 im ersten Stock (i bis l) m_catalog[ 'l' ].push_back( bind( &Haus::Die2ImErstenStock, _1 ) ); // -- Im Erdgeschoß [m..p]werden die Zahlen von links nach rechts groesser m_catalog[ 'n' ].push_back( bind( &Haus::at, _1, 'm' ) < bind( &Haus::at, _1, 'n' ) ); m_catalog[ 'o' ].push_back( bind( &Haus::at, _1, 'n' ) < bind( &Haus::at, _1, 'o' ) ); m_catalog[ 'p' ].push_back( bind( &Haus::at, _1, 'o' ) < bind( &Haus::at, _1, 'p' ) ); // -- Es gilt a > e, das heißt, in a wohnt eine groessere Zahl als in e m_catalog[ 'e' ].push_back( bind( &Haus::at, _1, 'e' ) < bind( &Haus::at, _1, 'a' ) ); // -- außerdem h > g, j > i, j > k und k > l m_catalog[ 'h' ].push_back( bind( &Haus::at, _1, 'h' ) > bind( &Haus::at, _1, 'g' ) ); m_catalog[ 'j' ].push_back( bind( &Haus::at, _1, 'j' ) > bind( &Haus::at, _1, 'i' ) ); m_catalog[ 'k' ].push_back( bind( &Haus::at, _1, 'j' ) > bind( &Haus::at, _1, 'k' ) ); m_catalog[ 'l' ].push_back( bind( &Haus::at, _1, 'k' ) > bind( &Haus::at, _1, 'l' ) ); // -- Schließlich gilt: n mal o = c + d, i + j = k + l und e mal f = g + h. m_catalog[ 'o' ].push_back( bind( std::multiplies< int >(), bind( &Haus::at, _1, 'n' ), bind( &Haus::at, _1, 'o' ) ) == bind( std::plus< int >(), bind( &Haus::at, _1, 'c' ), bind( &Haus::at, _1, 'd' ) ) ); m_catalog[ 'l' ].push_back( bind( std::plus< int >(), bind( &Haus::at, _1, 'i' ), bind( &Haus::at, _1, 'j' ) ) == bind( std::plus< int >(), bind( &Haus::at, _1, 'k' ), bind( &Haus::at, _1, 'l' ) ) ); m_catalog[ 'h' ].push_back( bind( std::multiplies< int >(), bind( &Haus::at, _1, 'e' ), bind( &Haus::at, _1, 'f' ) ) == bind( std::plus< int >(), bind( &Haus::at, _1, 'g' ), bind( &Haus::at, _1, 'h' ) ) ); } template< typename Out > bool operator()( const Haus& haus, Out cur ) const { std::map< char, Checks >::const_iterator k = m_catalog.find( 'a' + char(distance( haus.begin(), Haus::const_iterator( cur ) ) ) ); if( k == m_catalog.end() ) return true; // keine Checks dann alles Ok const Checks& checks = k->second; return find_if( checks.begin(), checks.end(), !boost::bind( &Haus::isOk, haus, _1 ) ) == checks.end(); } private: std::map< char, Checks > m_catalog; }; int main() { using namespace std; Haus haus; Pruefer pruefer; vector< int > zahlen; for( int z = 1; z <= 16; ++z ) zahlen.push_back( z ); // die Zahlen 1-16 if( fuelleHaus( zahlen, haus, haus.begin(), pruefer ) ) cout << "Loesung gefunden:\n" << haus << endl; return 0; }Ich bin sicher, dass allein durch die Änderung der Reihenfolge wie die Räume belegt werden, sich noch mehr Performance rausholen lässt; aber Achtung die Prüfbedingungen sind von der Reihenfolge abhängig.
Gruß
Werner
-
volkard schrieb:
Laufzeit 0.1 Sekunden.
Scharlatan!
-
was heiß eigentlich: "die quadratzahlen wohnen in den ecken"?
ist nicht jede wohnung eine ecke?
-
wieso geht der erste stock von i-l
hat jeder stock also vier wohnungen? müsste der erste sock dann nicht von e-h gehen?
-
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?
