当一个问题规模比较大且不易求解的时候，就可以考虑将问题分成几个小的模块，逐一求解。
分治思想和递归算是有亲兄弟的关系，因为采用分治思想处理问题，其各个小模块通常具有与大问题相同的结构，这种特性也使递归技术有了用武之地。
折半查找算法的递归实现(二分查找)
折半查找法是一种查找方法，该方法通过不断缩小一半查找的范围，直到达到目的，所以效率比较高。
二分查找递归实现代码：
/**
* 递归实现二分查找
*/
int bin_search(int key[], int low, int high, int x){
int mid;
if (low > high)
return -1;
else{
mid = (low + high)/2;
if (key[mid] == x) return mid;
if (x > key[mid]) {
low = mid + 1;
return bin_search(key, low, high, x); // 在序列的后半部分查找
}else{
high = mid - 1;
return bin_search(key, low, high, x); //在序列的前半部分查找
}
}
}
测试：
int main(int argc, const char * argv[]) {
int str[11] = {1,1,2,3,5,8,13,21,34,55,89};
int n, addr;
printf("请输入待查找的关键字：");
scanf("%d", &n);
addr = bin_search(str, 0, 10, n);
if (addr != -1) {
printf("查找成功！\n关键字%d所在位置是：%d\n", n, addr);
}else{
printf("查找失败！\n");
}
return 0;
}
折半查找算法的递归实现
汉诺塔问题
汉诺塔问题起源
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
汉诺塔问题抽象成数学问题
假设三个分别命名为X、Y、Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1,2,3...的圆盘，现在要求将X轴上的n个圆盘移动至Z上，并按照同样顺序叠排，圆盘移动时必须循序一下规则：
- 每次只能移动一个圆盘；
- 圆盘可以插在X、Y、Z中的任意一个塔座上；
-
任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
用递归的思想来考虑汉诺塔问题
汉诺塔问题的实现步骤：
- 先将前n-1(63)个盘子移动到Y上，确保大盘在小盘下；
- 再将最底下的第n(64)个盘子移动到Z上；
- 最后将Y上的n-1(63)个盘子移动到Z上。
那么问题就化解为解决一下两个问题：
- 问题一：将X上的n-1(63)个盘子借助Z移动到Y上；
- 问题二：将Y上的n-1(63)个盘子借助X移动到Z上。
解决这两个步骤的思路相同：
问题一：
- 先将前n-2(62）个盘子移动到Z上，确保大盘在小盘下；
- 再将最底下的第n-1(63)个盘子移动到Y上；
- 最后将Z上的n-2(62)个盘子移动到Y上。
问题二： - 先将前n-2(62）个盘子移动到X上，确保大盘在小盘下；
- 再将最底下的第n-1(63)个盘子移动到Z上；
- 最后将Z上的n-2(62)个盘子移动到Y上。
得出相同的规律：这其实就是一个递归问题。
代码：
void hanoi(int n, char x, char y, char z){
if (n == 1) // 只有一层的情况
printf("%c --> %c\n", x, z);
else{
hanoi(n - 1, x, z, y); // 将 n-1 个盘子从 x 借助 z 移动到 y 上
printf("%c --> %c\n", x, z); // 将第 n 个盘子从 x 移动到 z 上
hanoi(n-1, y, x, z); // 将 n-1 个盘子从 y 借助 x 移动到 z 上
}
}
测试代码：
int main(int argc, const char * argv[]) {
int n;
printf("请输入汉诺塔的层数：");
scanf("%d", &n);
printf("移动的步骤如下：\n");
hanoi(n, 'X', 'Y', 'Z');
return 0;
}
汉诺塔递归算法
八皇后问题递归解法
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
用递归解决八皇后问题的代码
#include <stdio.h>
int count = 0;
/**
* 判断是否有危险
*/
int notdanger(int row,int j,int (*chess)[8]){
int i,k;
//判断列方向
for(i=0;i<8;i++){
if(*(*(chess+i)+j)==1) return 0; //这一列已存在皇后
}
//判断左上方
for(i=row,k=j;i>=0&&k>=0;i--,k--){
if(*(*(chess+i)+k)==1) return 0; //左上方已存在皇后
}
//判断右下方
for(i=row,k=j;i<8&&k<8;i++,k++){
if(*(*(chess+i)+k)==1) return 0; //右下方已存在皇后
}
//判断左下方
for(i=row,k=j;i<8&&k>=0;i++,k--){
if(*(*(chess+i)+k)==1) return 0; //左下方已存在皇后
}
//判断右上方
for(i=row,k=j;i>=0&&k<8;i--,k++){
if(*(*(chess+i)+k)==1) return 0; //右上方已存在皇后
}
return 1;
}
/**
* 参数row：起始行
* 参数n: 列数
* 参数(*chess)[8]：指向棋盘每一行的指针
*/
void eightqueen(int row,int n,int (*chess)[8]){
int chess2[8][8],i,j; // 临时棋盘
for(i=0;i<8;i++){
for(j=0;j<8;j++){
chess2[i][j] = chess[i][j]; // 临时棋盘赋值给棋盘
}
}
if(row == 8){
printf("第%d种：\n",count + 1);
for(i=0;i<8;i++){
for(j=0;j<8;j++){
printf("%d ",*(*(chess2+i)+j));
}
printf("\n");
}
count ++;
}else {
//判断这个位置是否有危险
//如果有危险，那继续往下
for(j=0;j<n;j++){
if(notdanger(row,j,chess)){ //判断是否危险
for(i=0;i<8;i++){ // 不危险
*(*(chess2+row)+i)=0;
}
*(*(chess2+row)+j)=1;
eightqueen(row+1,n,chess2);
}
}
}
}
int main(int argc, const char * argv[]) {
int chess[8][8]; // 8*8的棋盘
int i,j;
//初始化棋盘为0
for(i=0;i<8;i++){
for(j=0;j<8;j++){
chess[i][j]=0;
}
}
eightqueen(0,8,chess);//从第0行开始依次以行为单位遍历
printf("\n总共有 %d 种解决办法！\n\n",count);
return 0;
}
网友评论