سلام بر عزیزان دل
والا از هونجایی که از همه پوشیده نیست از شما برنامه نویس ها هم پوشیده نباشه همون قدر که از سخت افزار سر در نمیاریم همون اندازه به توان 2 از نرم افزار سر در نمیاریم :دی
به عنوان پروژه اخر ترم برای درس ساختمان داده قراره حرکت اسب رو در شطرنج شبیه سازی کنیم.
البته نه این بخوام دوستان برام بنویسند اصلا این قصد رو ندارم فقط خواستم اگر خدا خواست و نوشتم کسایی که نیاز داشته باشن بتونن استفاده ببرن
و عزیزانی هم که سرور ما هستن بیان گیر بدن(همون نقد باکلاس ها) تا این کار رو بهتر انجام بشه.
-------------------
مسئله: اسب را از هر خانه ی صفحه ی شطرنج طوری حرکت دهید که به صورت متوالی تمام 64 خانه ی شطرنج را با یک بار و فقط با یک بار عبور از هر خانه ی شطرنج طی کند.
این مسئله از کتاب "ساختمان داده ها در c++" نویستده: ا.هورویتس س.سهنی د.مه تا ، ترجمه: مهندس حسین ابراهیم زاده ی قلزم در صفحه 119 یا در بعضی ئیرایش ها در صفحه 117 گفته شده هست
خوب بریم سر اصل مطلب
والا نرفتم ببینم به چند روش حل میشه کرد، روشی که فک می کنم ساده تر باشه استفاده از یک ارایه دو بعدی باشه.
والا ائل از همه نحوه حرکت اسب هستش.
بعدش هم مسئله اصلی اینه که چطور یه اسب لامثب رو بدون این که توی خونه ی تکراری بره داخل 64 خونه بچرخونیمش.
چیزی که کتاب گفته اینه که نباید فقط از یه نقطه خاص شروع کرد از اینور خودم هم خوشم نمیاد مهدود باشه و دوست دارم خونه مورد نظر رو کار بر انتخواب کنه و در این صورت پدر خودم در میاد
البته این هم بگم که بعد از هر حرکت باید یه خروجی نمایش داده بشه تا حرکت اسب رو نشون بده.
فردا میشینم کارایی که انجام دادم رو تست می کنم و توی تاپیک قرار می دم .
بعد از دو روز برگشتم
راستیتش من یه کد توی اینترنت پیدا کردم که دقیقا مثل کتاب حل کرده بود و متغیر هاش هم همونا بودن که می تونید ببینید:
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
int min,npos,l,m,counter,
board[9][9]={{0},{0}} ,nexti[9]={0},
exits[11][2] ,nextj[9]={0}, //main
ktmov1[9]={0,-2,-1,1,2,2,1,-1,-2}, // variables
ktmov2[9]={0,1,2,2,1,-1,-2,-2,-1};
int i,j,t,p,q,r,temp; //temporary required elements
void move(int min)
{ //This function
i = nexti[min]; //move horse place
j = nextj[min]; //if needed
board[i][j] = m;
board[i][j] = m;
}
void prompt(){
cout<<'\n'<<setw(22)<<"The chessboard is: "<<'\n'<<'\n';
for(p=1 ; p<=8 ; p++) {
for(q=1 ; q<=8 ; q++)
cout<<setw(4)<< board[p][q] ;
cout<< endl;
} // end_first for
} //end_prompt
void main(){
clrscr();
cout<<'\n'<<"This program shoes horse jumpings in all chessboard squars";
cout<<'\n'<<"by ordering them with numbers in similar chessboard. ";
cout<<'\n'<<"__________________________________________________ ________";
cout<<'\n'<<"Enter Number Of Row And Column You Want To Start From ? ";
cout<<'\n'<<" ( 0<row<9 and 0<column<9 ) >> ";
cin>>i>>j;
board[i][j] = 1;
for(m=2 ; m<=64 ; m++) //main loop
{
for(p=0 ; p<=10 ;p++) //giving
for(q=0 ; q<=1 ;q++) //zero to
exits[p][q]=0; //variables
for(p=0 ; p<=8 ;p++) //and arrays
nexti[r]=nextj[r]=0; //needed
l=1 ;npos=0;
for (r=1 ; r<=8 ; r++) //This loop
{ //find rows and columns of
p =i + ktmov1[r]; //places the horse
q =j + ktmov2[r]; //can go and save
if( p<=8 && p>0 //rows in 'nexti' array and
&& q<=8 && q>0 //column in 'nextj' array
&& board [p][q]==0)
{
nexti[l] = p;
nextj[l] = q;
++l;
++npos; //number of positions
} // end_if
} //end_for
if(npos == 0){ //This condition check
prompt(); //the next place .
return; }
if(npos == 1) { // This condition check
min = 1; // if there is only one
move(min); // place to go, move horse
continue; } // to it.
t=0;
for( l=1 ; l<=npos ; l++) // This loop find and
{ // save numbers of exits
counter=0; // from every next place
for( r=1 ; r<=8 ; r++)
{
p=nexti[l] + ktmov1[r];
q=nextj[l] + ktmov2[r];
if( p<=8 && p>0 // checking next
&& q<=8 && q>0 // move is in board
&& board [p][q]==0) // and is empty
++counter;} // or not
exits[t][0]=l;
exits[t][1]=counter;
t++;
} //end for l
t=0;
min=exits[t][0];
temp=exits[t][1];
t++;
while(exits[t][0]!=0){ // finding minimum exit
if(temp>exits[t][1]){ // in next place
temp=exits[t][1];
min=exits[t][0];} // end_if
++t;
} //end_while
move(min);
}
prompt(); //showing board
getch();
cin.get();
}
اما کدی که خودم نوشتم جان خودم اخرشه :دی:love:
چون تا تحویل استاد ندادم نمی تونم روی سایت بزارم فعلا قسمتیش رو می زارم(بدون تابع main )
بعد از این که به استاد تحویل دادم کاملش رو می زارم.
-------------
من از اول تاپیک گفتم با کد نویسی میونه خوبی ندارم بعدا نگید خیلی کشکی بود :دی(ولی خداییش با اون برنامه ای که بالا هستش قابل رقابته :whistle:)
#include<stdio.h>
#include<conio.h>
int p=2;
void printchess ( int a[][8],int r)
{
for(int i=0;i<r;i++)
{
for(int j=0;j<8;j++)
if(a[i][j]>9)
printf("%d ",a[i][j]);
else
printf("%d ",a[i][j]);
printf("\n");
}
printf("\n");
}
void error(int *m)
{
printf("az 1 ta 8 vared konid\n");
scanf("%d",&*m);
}
int min(int B[8])
{
int m=B[0];
for(int i=1;i<8;i++)
if(B[i]<m)
m=B[i];
return m;
}
void next(int B[8],int A[][8],int d,int a,int b)
{
for(int i=0;i<8;i++)
if(d==B[i])
{
if(i==0)
{
A[a-2][b+1]=p;
p++;
break;
}
if(i==1)
{
A[a-1][b+2]=p;
p++;
break;
}
if(i==2)
{
A[a+1][b+2]=p;
p++;
break;
}
if(i==3)
{
A[a+2][b+1]=p;
p++;
break;
}
if(i==4)
{
A[a+2][b-1]=p;
p++;
break;
}
if(i==5)
{
A[a+1][b-2]=p;
p++;
break;
}
if(i==6)
{
A[a-1][b-2]=p;
p++;
break;
}
if(i==7)
{
A[a-2][b-1]=p;
p++;
break;
}
}
}
int move2(int D[][8],int a,int b)
{
int c=0;
if((a-2)>-1&&(b+1)<8&&D[a-2][b+1]==0)
c++;
if((a-1)>-1&&(b+2)<8&&D[a-1][b+2]==0)
c++;
if((a+1)<8&&(b+2)<8&&D[a+1][b+2]==0)
c++;
if((a+2)<8&&(b+1)<8&&D[a+2][b+1]==0)
c++;
if((a+2)<8&&(b-1)>-1&&D[a+2][b-1]==0)
c++;
if((a+1)<8&&(b-2)>-1&&D[a+1][b-2]==0)
c++;
if((a-1)>-1&&(b-2)>-1&&D[a-1][b-2]==0)
c++;
if((a-2)>-1&&(b-1)>-1&&D[a-2][b-1]==0)
c++;
return c;
}
void move (int A[][8],int a,int b)
{
int c=0,
g[8];
for(int i=0;i<8;i++)
g[i]=10;
if((a-2)>-1 && (b+1)<8 && A[a-2][b+1]==0)//{
g[0] = move2(A,a-2,b+1);
if((a-1)>-1 && (b+2)<8 && A[a-1][b+2]==0)
g[1]=move2(A,a-1,b+2);
if((a+1)<8 && (b+2)<8 && A[a+1][b+2]==0)
g[2]=move2(A,a+1,b+2);
if((a+2)<8 && (b+1)<8 && A[a+2][b+1]==0)
g[3]=move2(A,a+2,b+1);
if((a+2)<8 && (b-1)>-1 && A[a+2][b-1]==0)
g[4]=move2(A,a+2,b-1);
if((a+1)<8 && (b-2>-1) && A[a+1][b-2]==0)
g[5]=move2(A,a+1,b-2);
if((a-1)>-1 && (b-2)>-1 && A[a-1][b-2]==0)
g[6]=move2(A,a-1,b-2);
if((a-2)>-1 && (b-1)>-1 && A[a-2][b-1]==0)
g[7]=move2(A,a-2,b-1);
c=min(g);
if(c>0)
next(g,A,c,a,b);
}