递归与分治
一、斐波那契(Fibonacci)数列的递归实现
他讲的一个故事：
如果说兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。假设所有兔子都不会死去，能够一直干下去，那么一年以后可以繁殖多少对兔子呢？
用数学函数来定义：
1.使用迭代来实现打印出前40位斐波那契数列数
#include <stdio.h>
int main()
{
int i;
int a[40];
a[0] = 0;
a[1] = 1;
printf("%d %d ", a[0], a[1]);
for( i=2; i < 40; i++ )
{
a[i] = a[i-1] + a[i-2];
printf("%d ", a[i]);
}
return 0;
}
2.使用递归来实现打印出前40位斐波那契数列数
递归事实上就是函数自己调用自己，代码实现：
int Fib(int i)
{
if( i < 2 )
return i == 0 ? 0 : 1;
return Fib(i-1) + Fib(i-2);
}
代码实现：
#include <stdio.h>
int Fib(int i)
{
if( i < 2 )
{
return i == 0 ? 0 : 1;
}
return Fib(i-1) + Fib(i-2);
}
int main()
{
int i;
for( i=0; i < 40; i++ )
{
printf("%d ", Fib(i));
}
return 0;
}
二、递归定义
在高级语言中，函数自己调用和调用其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。
注意：每个递归定义必须至少有一个条件，当满足这个条件时递归不再进行，即函数不再调用自身而是返回值。
之前的Fbi函数结束条件是：i < 2
对比两种实现斐波那契的代码，迭代和递归的区别是：
迭代使用的是循环结构，
递归使用的是选择结构。
- 使用递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。
- 但大量的递归调用会建立函数的副本，会消耗大量的时间和内存，而迭代则不需要此种付出。
递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序。
举个例子，计算n的阶乘n!
则递归算法如下：
int factorial( n )
{
if( 0 == n ){
return 1;
}else{
return n * factorial( n - 1 );
}
}
假设n的值传入是5，那么：
三、实例分析
编写一个递归函数，实现将输入的任意长度的字符串反向输出的功能。例如输入字符串HCX,则输出字符串XCH。
分析：
要将一个字符串反向地输出，一般采用的方法是将该字符串存放到一个数组中，然后将数组元素反向的输出即可。这道题要求输入是任意长度，所以不用递归的话，实现起来会比较麻烦（当然也可以用动态申请内存）。
递归它需要有一个结束的条件，那么可以将“#”作为一个输入结束的条件。
void print()
{
char a;
scanf(“%c”, &a);
if( a !=‘#’) print();
if( a !=‘#’) printf(“%c”, a);
}
假设从屏幕上输入字符串：ABC#
四、分治思想
分而治之的思想古已有之，秦灭六国，统一天下正是采取各个击破、分而治之的原则。
分治思想在算法设计中也是非常常见的，当一个问题规模较大且不易求解的时候，就可以考虑将问题分成几个小的模块，逐一解决。
1.折半查找算法的递归实现
折半查找法是一种常用的查找方法，该方法通过不断缩小一半查找的范围，直到达到目的，所以效率比较高。
题目：有一个数组A[10]，里面存放了10个整数，顺序递归。A[10]={2,3,5,7,8,10,12,15,19,21} ,任意输入一个用数字n，用折半查找法找到n位于数组中的位置。如果n不属于数组A，显示错误提示。要求用递归的方法实现折半查找。
#include <stdio.h>
int bin_search(int key[],int low, int high,int k)
{
int mid;
if(low>high)
return -1;
else{
mid = (low+high) / 2;
if(key[mid]==k)
return mid;
if(k>key[mid])
return bin_search(key,mid+1,high,k); /*在序列的后半部分查找*/
else
return bin_search(key,low,mid-1,k); /*在序列的前半部分查找*/
}
}
int main()
{
int n , i , addr;
int A[10] = {2,3,5,7,8,10,12,15,19,21};
printf("The contents of the Array A[10] are\n");
for(i=0;i<10;i++)
printf("%d ",A[i]); /*显示数组A中的内容*/
printf("\nPlease input a interger for search\n");
scanf("%d",&n); /*输入待查找的元素*/
addr = bin_search(A,0,9,n);
if(-1 != addr) /*查找成功*/
printf("%d is at the %dth unit is array A\n ",n,addr);
else printf("There is no %d in array A\n",n); /*查找失败*/
getchar();
return 0;
}
五、汉诺塔问题
在世界中心贝拿勒斯的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。
思路：
这其实也是一个经典的递归问题。
我们可以做这样的考虑：
- 先将前63个盘子移动到Y上，确保大盘在小盘下。
- 再将最底下的第64个盘子移动到Z上。
- 最后将Y上的63个盘子移动到Z上。
由于每次只能移动一个圆盘，所以在移动的过程中显然要借助另外一根针才行。
也就是说第1步将1~63个盘子借助Z移到Y上，第3步将Y针上的63个盘子借助X移到Z针上。
那么我们把所有新的思路聚集为以下两个问题：
问题一：将X上的63个盘子借助Z移到Y上；
问题二：将Y上的63个盘子借助X移到Z上。
解决上述两个问题依然用相同的方法：
问题一的圆盘移动步骤为：
- 先将前62个盘子移动到Z上，确保大盘在小盘下。
- 再将最底下的第63个盘子移动到Y上。
- 最后将Z上的62个盘子移动到Y上。
问题二的圆盘移动步骤为：
- 先将前62个盘子移动到X上，确保大盘在小盘下。
- 再将最底下的第63个盘子移动到Z上。
- 最后将X上的62个盘子移动到Y上。
代码实现：
#include <stdio.h>
// 将 n 个盘子从 x 借助 y 移动到 z
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); // 将 第 n 个盘子从 x 移到 z 上
move(n-1, y, x, z); // 将 n-1 个盘子从 y 借助 x 移到 z 上
}
}
int main()
{
int n;
printf("请输入汉诺塔的层数: ");
scanf("%d", &n);
printf("移动的步骤如下: \n");
move(n, 'X', 'Y', 'Z');
return 0;
}
六、八皇后问题
八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题；此处使用递归解决。
该问题是十九世纪著名的数学家高斯1850年提出：
在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
正确的结果应该是92种
以下是其中一种解法：
代码实现：
#include <stdio.h>
int count = 0;
int notDanger( int row, int j, int (*chess)[8] )
{
int i, k, flag1=0, flag2=0, flag3=0, flag4=0, flag5=0;
// 判断列方向
for( 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 )
{
flag2 = 1;
break;
}
}
// 判断右下方
for( i=row, k=j; i<8 && k<8; i++, k++ )
{
if( *(*(chess+i)+k) != 0 )
{
flag3 = 1;
break;
}
}
// 判断右上方
for( i=row, k=j; i>=0 && k<8; i--, k++ )
{
if( *(*(chess+i)+k) != 0 )
{
flag4 = 1;
break;
}
}
// 判断左下方
for( i=row, k=j; i<8 && k>=0; i++, k-- )
{
if( *(*(chess+i)+k) != 0 )
{
flag5 = 1;
break;
}
}
if( flag1 || flag2 || flag3 || flag4 || flag5 )
{
return 0;
}
else
{
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( 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++ )
{
*(*(chess2+row)+i) = 0;
}
*(*(chess2+row)+j) = 1;
EightQueen( row+1, n, chess2 );
}
}
}
}
int main()
{
int chess[8][8], i, j;
for( i=0; i < 8; i++ )
{
for( j=0; j < 8; j++ )
{
chess[i][j] = 0;
}
}
EightQueen( 0, 8, chess );
printf("总共有 %d 种解决方法!\n\n", count);
return 0;
}
