C语言经典算法大全精选.docx

《C语言经典算法大全精选.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、7.AlgorithmGossip:骑士走棋盘说明骑士旅游（Knighttour）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提出已不可考，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完[所有的位置？解法骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，一个聪明的解法由J.C.Warnsdorff在1823年提出，简单的说，先将最难的位置走完，接下来的路就宽广了，骑士所要走的下一步，「为下一步再选择时，所能走的步数最少的一步。」，使用这个方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有

2、的）。#includeintboard[8][8]={0};intmain(void){intstartx,starty;inti,j;printf("输入起始点：");scanf("%d%d",&startx,&starty);if(travel(startx,starty)){printf("游历完成！");}else{printf("游历失败！");}for(i=0;i<8;i++){for(j=0;j<8;j++){printf("%2d",board[i][j]);}putchar('');}return0;}inttra

3、vel(intx,inty){//对应骑士可走的八个方向intktmove1[8]={-2,-1,1,2,2,1,-1,-2};intktmove2[8]={1,2,2,1,-1,-2,-2,-1};//测试下一步的出路intnexti[8]={0};intnextj[8]={0};//记录出路的个数intexists[8]={0};inti,j,k,m,l;inttmpi,tmpj;intcount,min,tmp;i=x;j=y;board[i][j]=1;for(m=2;m<=64;m++){for(l=0;l<8;l++)exists[l]=0;l=0;

4、//试探八个方向for(k=0;k<8;k++){tmpi=i+ktmove1[k];tmpj=j+ktmove2[k];//如果是边界了，不可走if(tmpi<0

5、

6、tmpj<0

7、

8、tmpi>7

9、

10、tmpj>7)continue;//如果这个方向可走，记录下来if(board[tmpi][tmpj]==0){nexti[l]=tmpi;nextj[l]=tmpj;//可走的方向加一个l++;}}count=l;//如果可走的方向为0个，返回if(count==0){return0;}elseif(count==1){//只有一个可走的方向//所以直接是最少出路

11、的方向min=0;}else{//找出下一个位置的出路数for(l=0;l

12、

13、tmpj<0

14、

15、tmpi>7

16、

17、tmpj>7){continue;}if(board[tmpi][tmpj]==0)exists[l]++;}}tmp=exists[0];min=0;//从可走的方向中寻找最少出路的方向for(l=1;l

18、ts[l];min=l;}}}//走最少出路的方向i=nexti[min];j=nextj[min];board[i][j]=m;}return1;}8.AlgorithmGossip:八皇后说明西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上，1970年与1971年，E.W.Dijkstra与N.Wirth曾经用这个问题来讲解程式设计之技巧。解法关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数？在八个皇后的问题中，不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个

19、方法称为分支修剪。#include#include#defineN8intcolumn[N+1];//同栏是否有皇后，1表示有intrup[2*N+1];//右上至左下是否有皇后intlup[2*N+1];//左上至右下是否有皇后intqueen[N+1]={0};intnum;//解答编号voidbacktrack(int);//递回求解intmain(void){inti;num=0;for(i=1;i<=N;i++)column[i]=1;for(i=1;i<=2*N;i++)rup[i]=lup[i]=1;backt

20、rack(1);retu