现在的位置: 首页 > 综合 > 正文

棋盘跳马问题

2013年10月06日 ⁄ 综合 ⁄ 共 1071字 ⁄ 字号 评论关闭

棋盘跳马问题

     暑假训练张老师讲的,递归问题。

     在一个5*5的棋盘上,马从某个格子出发,只能跳到能和现在所站位置成日子型的格子中,找到能跳完这25个格子的所有方式。    

     举例:

 

X1,y1

 

X1,y1

 

X1,y1

 

 

 

X1,y1

 

 

x,y

 

 

X1,y1

 

 

 

X1,y1

 

X1,y1

 

X1,y1

 

     这里不如就好好接受老师的思路,自己的太不顺了。

    

#include <stdio.h>
int a[9][9]={0};
void prt(){ 
	int i,j;
	for(i=2;i<=6;i++){
		for(j=2;j<=6;j++)
			printf("%3d",a[i][j]);
		printf("\n");
	}
	printf("\n\n");
}
void jump(int x,int y,int k){
	int i,x1,y1;
	for(i=1;i<=8;i++){ /*显而易见是对应的可以跳到的8个位置。*/
		switch(i){
		case 1:x1=x-1;y1=y+2;
			break;
		case 2:x1=x+1;y1=y+2;
			break;
		case 3:x1=x+2;y1=y+1;
			break;
		case 4:x1=x+2;y1=y-1;
			break;
		case 5:x1=x+1;y1=y-2;
			break;
		case 6:x1=x-1;y1=y-2;
			break;
		case 7:x1=x-2;y1=y-1;
			break;
		case 8:x1=x-2;y1=y+1;
			break;
		}
		if(a[x1][y1]==0){ 
			a[x1][y1]=k; /*其实这句话我觉得很不顺,可再也想不到更好的表达,*/
			if(k==25)    /*这样是为了打印的时候在期盼的对应格子打印出每一步跳的痕迹。*/
				prt();
			else 
				jump(x1,y1,k+1);
			a[x1][y1]=0;
		}
	}
}
void main(){
	int i,j;
	for(i=0;i<2;i++){ /*话说好佩服张老师这样开数组,开成一个9*9的数组,*/
		for(j=0;j<9;j++){ /*然后把最上下左右两行标记为不存在,这样就免去了判断是不是跳出界的麻烦。*/
			a[i][j]=-1;
			a[j][i]=-1;
		}
	}
	for(i=7;i<9;i++){
			for(j=0;j<9;j++){
				a[i][j]=-1;
				a[j][i]=-1;
			}
	}
	a[2][2]=1; /*自己写的时候还妄想能打印出所有情况,*/
	jump(2,2,2); /*只是以第一行第一列这一格为起点情况就这么多了。*/
}                /*老师还说可以自己加一个变量标记一下出现的情况的具体数目。*/

 

    

	

 

抱歉!评论已关闭.