递归和分治思想

Question

一、斐波那契数列

1 1 2 3 5 8 13 21 34 55 89 144 .....，我们可以用数学函数来定义：

     |0，当n = 0
F(n) = |1，当n = 1
     |F(n-1)+F(n-2)，当n>1

1.迭代实现斐波那契数列

#include<stdio.h>

int main(){

  int i,j,k;

  printf("请输入斐波那契数列的层数:");
  scanf("%d",&i);

  int arr[i+1];
  if(i<=0){
    printf("层数不能小于等于0\n");
    return 0;
  }

  arr[0] = 0;
  arr[1] = 1;

  if(i>1){
    for(j=2;j<=i;j++){
      arr[j] = arr[j-1]+arr[j-2];
    }
  }

  for(k=1;k<=i;k++){
    printf("%d ",arr[k]);
  }
  printf("\n");

  return 0;
}

2.递归实现斐波那契数列

#include<stdio.h>
int fib(int i){
  return i<2 ? i : fib(i-1)+fib(i-2);
}

int main(){
  int i,j;
  printf("请输入斐波那契数列的长度:");
  scanf("%d",&i);

  for(j=1;j<=i;j++){
    printf("%d ",fib(j));
  }
  printf("\n");
  return 0;
}

二、递归的定义

在高级语言中，函数调用自己和调用其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。

不过，写递归程序最怕的就是陷入永不结束的无穷递归中。切记，每个递归定义必须至少有一个条件，当满足这个条件时递归不再进行，即函数不再调用自身而是返回。

比如之前我们的fib函数的条件是i<2。

对比了两种实现斐波那契数列的代码，迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。

使用递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。

但大量的递归调用会建立函数的副本，会消耗大量的时间和内存，而迭代则不需要此种付出。

递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序。

void print(){
  char a;
  scanf("%c",&a);

  if(a!='#'){
    print();
  }else{
    printf("%c",a);
  }
}

三、分治思想

分治思想在算法设计中也是非常常见的，当一个问题规模较大且不易求解的时候，就可以考虑将问题分为几个小的模块，逐一解决。

分治思想和递归算是有亲兄弟关系了，因为采用分治思想处理问题，其各个小模块通常具有与大问题相同的结构，这种特性也使递归技术有了用武之地。

折半查找算法的递归实现

折半查找的基本思想是：减小查找序列的长度，分而治之的进行关键字的查找。

折半查找的实现过程是：先确定待查找记录的所在范围，然后逐渐缩小这个范围，直到找到该记录或查找失败（查无该记录）为止。

例如有序列 1 1 2 3 5 8 13 21 34 55 89 该序列包含11个元素，而且关键字也是单调递增，现要求查找关键字key为55的记录。

我们可以设置指针low和high分别指向关键字序列的上界和下界指针mid指向序列的中间为止，即 mid=(low+high)/2。

首先将mid所指向的元素与key进行比较，因为我们这里key = 55，大于8，这就说明待查找的关键字一定位于mid和high之间，于是我们执行low = mid+1;mid = (low+high)/2。

然后再将mid所指向的34与key进行比较，任然*mid<key，所以继续执行 low = mid +1;mid = (low+high)/2

接下来任然将mid所指向的元素与key进行比较，结果相等，查找成功，返回mid的指针值。

#include<stdio.h>
#include<stdlib.h>

int searchMid(int arr[],int i,int low,int height,int mid){
  if(low > height){
    return -1;
  }

  if(arr[mid] == i){
    return mid;
  }
  if(arr[mid] > i){
    height = mid - 1;
    mid = (low+height)/2;
    return searchMid(arr,i,low,height,mid);
  }
  if(arr[mid] < i){
    low = mid +1;
    mid = (low+height)/2;
    return searchMid(arr,i,low,height,mid);
  }

}

int main(){
  int arr[11] = {1,1,2,3,5,8,13,21,34,55,89};
  int low = 0;
  int height = sizeof(arr)/sizeof(arr[0])-1;
  int mid  = (low+height)/2;

  int i;
  printf("请输入需要查询的数字：");
  scanf("%d",&i);

  int loc = searchMid(arr,i,low,height,mid);

  printf("%d",loc);
  return 0;
}

四、汉诺塔

一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。

这其实也是一个经典的递归问题

我们可以这样考虑：

现将前63个盘子移动到Y上，确保大盘在小盘下；

再将最底下的第64个盘子移动到Z上；

最后将Y上的63个盘子移动到Z上。

在游戏中，我们发现由于每次只能移动一个圆盘，所以在移动的过程中显然要借助另外一根针才行。

也就是说第1步将1-63个盘子借助Z移到Y上，第3步将Y针上的63个盘子借助X移动到Z针上。那么我们把所有新的思路聚集为以下两个问题：

问题一：将X上的63个盘子借助Z移动到Y上

先将前62个盘子移动到Z上，确保大盘在小盘下；

再将最底下的63号盘子移动到Y上

最后将Z上的62个盘子移动到Y上。

问题二：将Y上的63个盘子借助X移动到Z上

先将前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);

  move(n,'X','Y','Z');
  return 0;
}

五、八皇后问题

在 8*8 格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。(92)

#include<stdio.h>

int count = 0;
//参数row表示起始行
//参数n表示列数
//参数(*chess)[8]表示指向棋盘每一行的指针
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;
  }
}


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(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");
    }
    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];//定义一个棋盘
  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种解决方法\n",count);

  return 0;
}