- تاریخ عضویت
- 22 ژانویه 2006
- نوشتهها
- 60
- لایکها
- 0
به نقل از Arash_j13 :تمرین شما رو سعی می کنم بنویسم یه راه به نظرم رسیده
یه تمرین هم من می گم از کتاب C++ How to program فصل آرایه ها
چه جوری می شه توی یه صفحه شطرنج با یک اسب طی 64 حرکت تمام خونه ها صفحه رو طی کرد
یه راهنمایی هم داره توی کتاب اون رو هم می گم
باید سعی کنید به خونه هایی برید که احتمال رفتن به اونجا کمتره جدول احتمال خونه ها این شکلی هست
کد:2,3,4,4,4,4,3,2 3,4,6,6,6,6,4,3 4,6,8,8,8,8,6,4 4,6,8,8,8,8,6,4 4,6,8,8,8,8,6,4 4,6,8,8,8,8,6,4 3,4,6,6,6,6,4,3 2,3,4,4,4,4,3,2
این روش رو یه جور واضحتر قبلا شنیده بودم که باید به خونه ای رفت که از اون خونه به کمترین خونه های ممکن بشه رفت.
حل مسئله:
(اصل برنامه 20 خطه بقیش کارای گرافیکیه و ... است).
کد:
#include<stdio.h>
#include<conio.h>
#define Cbakg 1
#define Cbakgtxt 2
#define Cbakgshattxt 4
#define Cbakgshatsiah 0
#define Cbakgshatsefid 7
void shat3(int x,int y,int nx,int ny,int tnx,int tny,int cse,int csi)
{
int i,j,k,l,m=0;
gotoxy(x,y);
for(i=0;i<tny;i++)
for(j=0;j<ny;j++){
m++;
for(k=0;k<tnx;k++){
if((i+k)%2==0)
textbackground(cse);
else
textbackground(csi);
for(l=0;l<nx;l++)
cprintf(" ");
}
gotoxy(x,y+m);
}
}
void main()
{
int sh[12][12]={0};
int h[8][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},
{-1,-2},{1,-2},{2,-1}};
int k=0,x,y,step=1,xNew,yNew,num,minNum=9,minK;
int l,i,j;
char ch;
textbackground(Cbakg);
textcolor(Cbakgtxt);
clrscr();
/////////////
//initialize
for(i=0;i<12;i++){
sh[i][0]=sh[i][1]=sh[i][10]=sh[i][11]=-1;
sh[0][i]=sh[1][i]=sh[10][i]=sh[11][i]=-1;
}
cprintf("inter x,y ");
scanf("%d%d",&x,&y);
x=(x-1)%8+1;
y=(y-1)%8+1;
clrscr();
cprintf("inter x,y x=%d y=%d",x,y);
x++;
y++;
sh[x][y]=step;
/////////////////
//begin calculate
for(step=2;step<=64;step++){
minNum=9;
for(k=0;k<8;k++){
xNew= x + h[k][0];
yNew= y + h[k][1];
if( sh[xNew][yNew] == 0){
sh[xNew][yNew] = step;
num=0;
for(l=0;l<8;l++)
if(sh[ xNew + h[l][0] ][ yNew + h[l][1] ]==0) num++;
if(num<minNum){
minNum=num;
minK=k;
}
sh[xNew][yNew] = 0;
}
}
x= x + h[minK][0];
y= y + h[minK][1];
sh[x][y]=step;
}
//end calculate
///////////////
///////////////
//output
textcolor(Cbakgshattxt);
shat3(10,1,8,3,8,8,Cbakgshatsiah,Cbakgshatsefid);
for(i=0;i<8;i++)
for(j=0;j<8;j++){
if((i+j)%2==0)
textbackground(Cbakgshatsiah);
else
textbackground(Cbakgshatsefid);
gotoxy(j*8+13,i*3+2);
cprintf("%2d",sh[i+2][j+2]);
}
textcolor(Cbakgtxt);
textbackground(Cbakg);
gotoxy(20,25);
cprintf("if you want run step by step press y ");
ch=getch();
if(ch=='y'||ch=='Y'){
clrscr();
shat3(10,1,8,3,8,8,Cbakgshatsiah,Cbakgshatsefid);
textcolor(Cbakgshattxt);
for(i=1;i<65;i++){
for(j=0;j<8;j++)
for(l=0;l<8;l++)
if(sh[j+2][l+2]==i){
if((l+j)%2==0)
textbackground(Cbakgshatsiah);
else
textbackground(Cbakgshatsefid);
gotoxy(l*8+13,j*3+2);
cprintf("%2d",i);
gotoxy(80,25);
}
ch=getch();
if(ch=='q'||ch=='Q')break;
}
}
}
آرایه sh درسته که 12*12 هست ولی در واقع خود صفحه شطرنج هستش که به این صورت مقدار دهی اولیه کردم:
کد:
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,-1,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
آرایه h هم که نحوه حرکت اسب رو شبیه سازی می کنه. هر کدوم از هشت جفت عددهای آرایه h یک حرکت اسب هست. و چون اسب از هر خونه حداکثر به هشت خانه بعدی می تونه بره پس آرایه h هشت جفت عدد داره.
این روش فقط چند حالت از میلیونها جواب رو میده. این سئوال رو قبلا در حالت کلیش رو مجبور بودم حل کنم یعنی تمام حالتهایی که اسب می تونه همه خونه ها رو در 64 حرکت بره .
اینطوری خیلی سخت تر میشه این هم بعنوان یک سئوال بهش فکر کنید . من قبلا حل کردم (کلا تغییرش دادم تا جواب این سئوال رو بدم) البته برنامه با این روش راه حل های زیادی رو پیدا می کنه ولی نمی تونه همه راه حل ها رو پیدا کنه باید 64^8 حالت رو چک کنه که در حدود همون برنامه قبلی در میاد (یعنی یکسال). توی سه یا چهار ساعت 3000 تا جواب رو بدست میاره (بستگی به نقطه شروع داره) برای همین کل جواب ها باید بیشتر از چند میلیون باشه.
حالا همین خودش دوباره سئوال باشه. یعنی برنامه ای که بتونه تمام راه حل ها رو بدست بیاره.
روش جالبی داره ولی سخت تره.