[C] Einstieg in rekursive Algorithmen

[Colin MacLaren]

Hey, ich versuche mich gerade am Rausschmeißer des ersten Semesters, der Rekursion ;)

Ziel ist das klassische Damenproblem. Wir haben ein Schachbrett mit 8x8 Feldern und versuchen darauf acht Damen so zu platzieren, dass keine die andere bedroht.

Die Idee war, iterativ in einer Zeile in jeder Spalte eine Dame zu platzieren, zu checken, ob bereits gesetzte Damen diese bedrohen und wenn dies nicht der Fall ist, eine Zeile nach unten zu gehen und dort mit der Rekursion fortzufahren. Die Abbruchbedingung ist eine gültig gesetzte Dame in der letzten Zeile, dann erfolgt die Ausgabe des Schachbretts und es geht wieder eine stufe tiefer.

Leider gibt mein Algorithmus genau gar nichts aus.

#include <stdio.h>
#include <stdlib.h>

//Testet, ob in der aktuellen Spalte oder auf den absteigenden Diagonalen eine andere Dame sitzt.
int DameOK(int feld[][8], int zeile, int spalte)
{
int i;

for ( i = 0 ; i < zeile; i++ )
if ( feld[i][spalte] )
return 0;
for (i = 1; zeile - i >= 0, spalte - i >= 0 ; i++ )
if ( feld[zeile-i][spalte-i] )
return 0;
for (i = 1; zeile - i >= 0, spalte + i <= 7 ; i++ )
if ( feld[zeile-i][spalte+i] )
return 0;

return 1;
}

//Darstellung des Schachbretts
void ausgabe(int feld[][8])
{
int i, j;

printf("+--+--+--+--+--+--+--+--+");
for (i = 0; i <= 7; i++)
{
printf("\n|");
for (j = 0; j <= 7; j++)
{
if ( feld[i][j] == 0)
printf(" |");
else
printf(" D|");
}
printf("\n+--+--+--+--+--+--+--+--+");
}
printf("\n\n");
}


int rekursion(int feld[][8], int zeile)
{
int i;

for ( i = 0 ; i <= 7 ; i++ )
{
if ( DameOK(feld, zeile, i) )
{
feld[zeile][i] = 1;
if ( zeile == 7 )
ausgabe(feld);
else
rekursion(feld, zeile + 1);
feld[zeile][i] = 0;
}
}
return 0;
}

void main()
{
int feld[8][8];
int i, j;

for (i = 0; i <= 7; i++)
for (j = 0; j <= 7; j++)
feld[i][j] = 0;

rekursion(feld, 0);

return;
}

[nalye]

Ich habe mal in meinem Archiv gewühlt und meine Variante gefunden. Kannst ja gerne mal vergleichen (Bin ein wenig raus aus C++)


#include <stdio.h>
#include <stdlib.h>

int x[8];

void print ()
{
int i,j;
printf ("+----------------+\n");
for (i=0; i<8; i++) {
printf ("|");
for (j=0; j<8; j++)
if (j==x[i]) printf ("<>");
else printf (" ");
printf ("|\n");
}
printf ("+----------------+\n\n");
}

int ist_frei (int ix, int iy)
{
int i;
for (i=0; i<iy; i++)
if ((x[i]==ix) || (abs(x[i]-ix)==abs(i-iy))) return 0;
return 1;
}

void try (int n)
{
int i;
if (n==8) print();
else
for (i=0; i<8; i++)
if (ist_frei(i,n)) {
x[n]=i;
try (n+1);
}
}

int main ()
{
try (0);
return 0;
}

[discordia]

Ist ja interessant

for (i = 1; zeile - i >= 0 && spalte - i >= 0 ; i++ )
if ( feld[zeile-i][spalte-i] )
return 0;
for (i = 1; zeile - i >= 0 && spalte + i <= 7 ; i++ )
if ( feld[zeile-i][spalte+i] )
return 0;

[Colin MacLaren]

Das war's schon. Danke.

Ich kann also in einer For-Schleife mehrere Inititialisierungen und mehrere Inkrementierungen mit Kommas trennen, bei den Tests auf die Abbruchbedingung aber nicht? Wieder was gelernt.

[Coda]

Das war's schon. Danke.

Ich kann also in einer For-Schleife mehrere Inititialisierungen und mehrere Inkrementierungen mit Kommas trennen, bei den Tests auf die Abbruchbedingung aber nicht? Wieder was gelernt.
Nein, du hast nichts gelernt, weil du eine völlig falsche Annahme hast, was das Komma angeht.

Der erste Teil eines for-Statements ist eine Deklaration, der zweite und dritte ein Ausdruck.

Das Komma hat in einer Deklaration aber eine total andere Bedeutung als in einem Ausdruck. In einer Deklaration trennt es mehrere deklarierte Variablen. Im Ausdruck aber ist es ein ,-Operator (https://en.wikipedia.org/wiki/Comma_operator), der einfach nur Hintereinanderausführung bedeutet, wobei der Rückgabewert der des rechten Teil-Ausdrücks ist.

Deine Abbruch-Bedingung wurde also nur zur Hälfte berücksichtigt, weil der Teil vor dem , überhaupt keinen Einfluss hat.

Nachtrag: In C ist der erste Teil des for auch ein Ausdruck. Sorry.

[Oid]

Solche for-Monster sollte man eh sein lassen, weil es den Code nicht gerade lesbarer macht :D

[ENKORE]

Solche for-Monster sollte man eh sein lassen, weil es den Code nicht gerade lesbarer macht :D
Da for aber einen Satz von Invarianten mitbringt, ermöglicht es dem Compiler bessere Optimierungen.

[del_4901]

Da for aber einen Satz von Invarianten mitbringt, ermöglicht es dem Compiler bessere Optimierungen.
Ist das nur nachgeplappert von einem 70 jaehrigen Uni-Prof., oder hast du das wirklich gemessen/verifiziert (assemblys verglichen)?