Backtracking Magisches Quadrat Laufzeit Problem

Danke für die schnelle Antwort DirkB.

Ich wäre erstmal glücklich wenn es für n=4 funktioniert.

Ja ich kenne schleifen allerdings sollen wir nur Rekursion benutzen, soll eine Art Übung sein.

Was genau meinst du mit Stack überlaufen? Und wie genau kann ich das verhindern. (Sry wenn ich doofe Fragen stelle)

Was genau meinst du mit mein Makro index ist ziemlich übel? (Sry wenn ich wieder doof frage möchte es nur verstehen und verbessern)

Ja das des mit den globalen Variablen schlecht ist ist mir bewusst. Das werd ich wohl gleich mal versuchen zu ändern. Wollte ich am ende eigentlich machen, war wohl nicht schlau...

Lokale Variablen (dazu gehören auch die Paramter einer Funktion) werden auf dem Stack (http://de.wikipedia.org/wiki/Kellerspeicher) angelegt.

Dieser Speicher ist begrenzt.
Da bei einem rekursiven Aufruf die Variablen jedesmal neu angelegt werden, ist irgendwann mal Schluss.
(Im Debugmodus werden dort noch ein paar mehr Informationen abgelegt)

Du kannst irgendwo in den Projekteigenschaften die Stackgröße ändern.

Du hast beim Aufruf von deinem index-Makro ja schon Klammern gesetzt. (wegen Punkt- vor Strich-Rechnung)
Die gehören aber nicht in den Aufruf sondern in die Definition.
Und das n gehört da auch mit rein:

#define index(zeile, spalte, n) ((n)*(zeile) + (spalte))

Dann ist das Makro universell, auch wenn die Größe mal nicht n heißt.
Bei Makros kann man nicht zuviel Klammern machen.

Ok das mit der Definition hab ich verstanden und gleich geändert. Hätte ich mir die ganzen klammeren im Aufruf sparen können.

Werde die das dann gleich noch anpassen.

Ok das mim Stack hab ich auch einigermaßen nun verstanden. Die Stackgröße in den Projekteigenschaften zu ändern wäre ja eher nur nee mogel Packung.

Wenn ich nur Zeiger in den Funktionen benutzen würde könnte ich dann damit das Problem um gehen? Weil sonst wird mein Stack ja immer zwangsläufig irgendwann voll. Oder was könnte ich sonst noch dagegen tun?

Nochmal Danke für deine Antwort DirkB

knivil

Bei n=4 sollte die Rekursionstiefe eigentlich maximal nur 16 sein fuer jede Zahl im magischem Quadrat. Die Summe sollte nochmals 4 tief werden. Mit einer Rekursionstiefe von 20 sollte kein Stack Probleme haben.

Ooru schrieb:

void pruef(int zeile, int spalte, int i, int n){
    if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n && pruefw <2){
        /*printf("Zeile: %d , Spalte: %d ",zeile,spalte);*/
        if (zeile == 0 && spalte == 0){
            /*printf("feld00: %d i: %d \n\n",feld[index(zeile,spalte)],i);*/
            if(feld[index(zeile,spalte)] == i){
              pruefw++;
              /*printf("Gleich00, pruefw: %d\n\n",pruefw);*/
              pruef(zeile-1,spalte-1,i,n);
            }
            pruef(zeile-1,spalte-1,i,n);
        }

Ist das nötig, dass in Zeile 9 und 11 der gleiche Code steht?

Und warum rufst du die Funktion nochmal auf, wenn zeile und spalte schon 0 sind?
Beim Aufruf steht dann pruef(-1,-1,i,n);
Die Funktion kommt dann gleich zurück. Dann brauchst du sie auch gar nicht erst aufrufen.

So etwas wird auch noch im Rest des Programms sein.

DirkB schrieb:
void pruef(int zeile, int spalte, int i, int n){
    if (zeile >= 0 && spalte >= 0 && zeile < n && spalte < n && pruefw <2){
        /*printf("Zeile: %d , Spalte: %d ",zeile,spalte);*/
        if (zeile == 0 && spalte == 0){
            /*printf("feld00: %d i: %d \n\n",feld[index(zeile,spalte)],i);*/
            if(feld[index(zeile,spalte)] == i){
              pruefw++;
              /*printf("Gleich00, pruefw: %d\n\n",pruefw);*/
              pruef(zeile-1,spalte-1,i,n);
            }
            pruef(zeile-1,spalte-1,i,n);
        }
Ist das nötig, dass in Zeile 9 und 11 der gleiche Code steht?

Und warum rufst du die Funktion nochmal auf, wenn zeile und spalte schon 0 sind?
Beim Aufruf steht dann pruef(-1,-1,i,n);
Die Funktion kommt dann gleich zurück. Dann brauchst du sie auch gar nicht erst aufrufen.

So etwas wird auch noch im Rest des Programms sein.

Ja hast du absolut recht ist total unnötig. Hab es gerade getestet. Da hab ich mir wohl evtl viele Fehler erlaubt

Wenn du noch was siehst was dir auffällt poste es bitte. Ich kann nicht von dir verlangen das ganze Programm durch zu gehen aber schonmal vielen Dank dafür.

Hast mir schon einige Fehler aufgezeigt.

Bei n=4 sollte die Rekursionstiefe eigentlich maximal nur 16 sein fuer jede Zahl im magischem Quadrat. Die Summe sollte nochmals 4 tief werden. Mit einer Rekursionstiefe von 20 sollte kein Stack Probleme haben.

Hm ergibt sinn allerdings denke ich das die Rekursionstiefe durch die pruefw Funktion zu groß wird. Vermutlich liegt da mein Problem.

Danke dir.

Ooru schrieb:

Hm ergibt sinn allerdings denke ich das die Rekursionstiefe durch die pruefw Funktion zu groß wird. Vermutlich liegt da mein Problem.

Danke dir.

Die Aufrufe werden doch in eingabe gezählt.
Du rufst eingabe also schon 35452 mal auf. Das ist auch schon ein bisschen viel.

Die Zeilen/Spaltensumme ist doch bekannt (hängt von n ab)
Sobald die Summe einmal nicht stimmt kannst du den Versuch doch schon abbrechen.

Hm ich denk ich werds einfach nochmal komplett neu angehen.

Allerdings gibt es für n=4 worauf sich meine Angabe bezogen hat 16! Permutationen da sind 35.000 nicht gerade viel. Und ja ich breche aktuell ja ab sobald es nicht passt oder rufe viel mehr die funktion neu auf mit geänderten i wert.

Ok. Soweit bin ich da nicht durchgestiegen.
Aber bei 16! kommst du mit einem int nicht weit. Da gibt es bei 13! schon einen Überlauf.

Du kannst ja noch einen Paramter an die Funktion übergeben (Beispiel an deinem jetzigen Code, der ja nicht optimal ist):

eingabe(int zeile, int spalte, int i, int n, int tiefe){  // tiefe als neuen Parameter.
        printf("Versuch: %7d Tiefe %2d\n", j, tiefe);
        j++;

....
       eingabe(...., tiefe+1); // beim Aufruf nächste Ebene

Dann kannst du Rekursionstiefe verfolgen.