03/09/2006 01:32:26 SlimShady

קראתי איזו תוכנית שכתבו ב-C, שבעצם מביאה את כל האפשרויות, להצבת שמונה מלכות בלוח שחמט, בלי שיוכלו לאכול אחת את השנייה (לוח אם שמונה עמודות ושורות, ואסור שיהיו שתי מלכות באותה עמודה,שורה או אלכסון)
הנה התוכנית:
קוד:
#include <conio.h>

char sum=0;

void swap(char *a, char *b)
{
char temp=*a;
*a=*b;
*b=temp;
}


char check(char a[])
{
char i,j;
for(i=0;i<7;++i)
for(j=i+1;j<8;++j)
if((a-i==a[j]-j) || (a+i==a[j]+j))
return 0;

return 1;
}

void show(char a[])
{
char i,j;

clrscr();
for(i=0;i<8;i++)
{
gotoxy(1,2*i+1);
for(j=0;j<8;j++)
cprintf("+---");
}

for(i=0;i<8;i++)
{
gotoxy(1,2*i+2);
for(j=0;j<8;j++)
cprintf("| ");
}

for(i=0;i<8;i++)
for(j=0;j<8;j++)
if(a[j]==i)
{
gotoxy(2+i*4,j*2+2);
cprintf("X");
}

gotoxy(1,20);
cprintf("Pres any key (ctr+break to quit).");
getch();
}


void solve(char a[],int n)
{
char i;

if(n==7)
{
if(check(a))
{
show(a);
sum++;
}
}

else
{
solve(a,n+1);
for(i=n+1;i<8;i++)
{
swap(a+n,a+i);
solve(a,n+1);
swap(a+n,a+i);
}
}
}


void main()
{
char a[8]={0,1,2,3,4,5,6,7};

show(a);
solve(a,0);
gotoxy(5,22);
cprintf("Total solutions: %d", sum);
getch();
}


הבנתי את כל הפונקציות פה, חוץ מהפונקציה SOLVE. מה בעצם היא עושה? איך בעצם היא מגיעה לפתרון?
פשוט התחלתי ללמוד רקורסיות, וזה היה בסדר בהתחלה, אבל פה זה ממש תסבוכת שלמה שלא הבנתי כלום, איך לעזאזל אפשר לחשב את כל הדרך שהרוקרסיות האלה עושות...

[ההודעה נערכה על-ידי SlimShady ב-03/09/2006 01:33:14]

[ההודעה נערכה על-ידי SlimShady ב-03/09/2006 11:55:09][ההודעה נערכה על-ידי tal ב-05/09/2006 20:20:05]