经典的递归程序设计中的2到题目

1、八皇后问题

国际象棋棋盘走法，用递归实现所有的可能性；

棋盘：

(1)、代码如下：

#include<stdio.h>typedefunsignedcharboolean;#defineTRUE1#defineFALSE0#defineEIGHT8voidshowChess(int(*chess)[EIGHT]);//显示棋盘booleanisSafe(int(*chess)[EIGHT],introw,intcol);//判断这个位置是否安全voideightQueen(int(*chess)[EIGHT],introw);//八皇后的递归程序voideightQueen(int(*chess)[EIGHT],introw){intcolIndex;if(row>=EIGHT){showChess(chess);}else{for(colIndex=0;colIndex<EIGHT;colIndex++){if(isSafe(chess,row,colIndex)==TRUE){chess[row][colIndex]=1;eightQueen(chess,row+1);chess[row][colIndex]=0;}}}}booleanisSafe(int(*chess)[EIGHT],introw,intcol){introwIndex;intcolIndex;for(rowIndex=row-1;rowIndex>=0;rowIndex--){if(chess[rowIndex][col]==1){returnFALSE;}}for(rowIndex=row-1,colIndex=col-1;rowIndex>=0&&colIndex>=0;rowIndex--,colIndex--){if(chess[rowIndex][colIndex]==1){returnFALSE;}}for(rowIndex=row-1,colIndex=col+1;rowIndex>=0&&colIndex<EIGHT;rowIndex--,colIndex++){if(chess[rowIndex][colIndex]==1){returnFALSE;}}returnTRUE;}voidshowChess(int(*chess)[EIGHT]){inti;intj;intstaticcount;printf("解：%d\n",++count);for(i=0;i<EIGHT;i++){for(j=0;j<EIGHT;j++){printf("%4d",chess[i][j]);}printf("\n");}}voidmain(void){intchess[EIGHT][EIGHT]={0};eightQueen(chess,0);}

(2)、运行结果：


因为4个方向，每一个方向都有23种解法!!!


2、全排列问题

从n个数据中挑选m个数据，每个数据只能取一次，输出其全部组合的可能性；

(1)、代码如下：

#include<stdio.h>#include<string.h>voidfullArray(char*sourceStr,intsourceLen,int*used,inti,char*resStr,intcount);voidfullArray(char*sourceStr,intsourceLen,int*used,inti,char*resStr,intcount){intindex;if(i>=count){printf("%s\n",resStr);}else{for(index=0;index<sourceLen;index++){if(used[index]==0){resStr[i]=sourceStr[index];used[index]=1;fullArray(sourceStr,sourceLen,used,i+1,resStr,count);used[index]=0;}}}}voidmain(void){charsourceStr[80];intused[80]={0};charresStr[80]={0};intcount;printf("请输入字符串:");gets(sourceStr);printf("请问要几个进行全排列?");scanf("%d",&count);fullArray(sourceStr,strlen(sourceStr),used,0,resStr,count);}

(2)、运行结果：