数据结构--递归与分治

汉诺塔分析：

以三层进行分析，大于三层分析情况是一样的。

#include <stdio.h>void move(int n,char x,char y,char z)
{if(1 == n){printf("%c---------->%c\n",x,z);}else{move(n-1,x,z,y);//将第n-1个盘子从x借助z移动到y printf("%c---------->%c\n",x,z);move(n-1,y,x,z);//将n-1个盘子从y借助x移动到z上 }
}int main()
{int n;printf("Input n:");scanf("%d",&n);printf("移动的步骤\n");move(n,'x','y','z'); return 0;} 

 

 八皇后问题：

#include <stdio.h>int count = 0; int notDanger(int row ,int j,int (*chess)[8])
{int i,k;int flag1;//判断列方向 for(int i=0;i<8;i++){if(*(*(chess+i)+j) != 0){flag1 = 1;break;} }//判断左上方for(i = row, k =j;i>=0&&k>=0;i--,k--){if(*(*(chess+i)+k)!=0){flag1=1;break;}} //判断右下方for( i = row, k =j;i<8&&k<8;i++,k++){if(*(*(chess+i)+k)!=0){flag1=1;break;}} //判断右上方for( i = row, k =j;i>=0&&k<8;i--,k++){if(*(*(chess+i)+k)!=0){flag1=1;break;}} //判断左下方for( i = row, k =j;i<8&&k>=0;i++,k--){if(*(*(chess+i)+k)!=0){flag1=1;break;}} if(flag1==1){return 0;}else return 1;
}
// row:起始行  n:列数 chess[8]: 表示棋盘每一行指着 
void EightQueen(int row, int n, int (*chess)[8])
{int chess2[8][8];int i,j;for( i=0;i<8;i++){for( j=0;j<8;j++)chess2[i][j]=chess[i][j];}if(8 == row){printf("第 %d 种方法:\n",count+1);for(i=0;i<8;i++){for( j=0;j<8;j++)printf("%d  ",*(*(chess2+i)+j));printf("\n");}printf("\n");count++;}else{//判断这个位置是否有危险//如果没有危险，继续往下for(j=0;j<n;j++){if(notDanger(row,j,chess))//判断是否危险 (不危险） {for(i=0;i<8;i++){*(*(chess+row)+i) = 0;}*(*(chess2+row)+j) = 1;EightQueen(row+1,n,chess2);}} }
}int main()
{int chess[8][8];int i,j;for(i=0;i<8;i++){for(j=0;j<8;j++)chess[i][j]=0;}EightQueen(0,8,chess);printf("总共有 %d   种解决方法",count);return 0;
}