递归与分治思想

    递归与分治思想往往是相伴而生的，在各种算法中使用很频繁。分治算法的思想是，解决一些规模较大的问题，常常将问题进行分解，将大规模的问题，分割成规模较小的同类问题，然后将这些小的子问题逐个解决，最终也就将整个大的问题解决了。

    计算n的阶乘。因为n的阶乘为n*(n-1)的阶乘，而零的阶乘为1。因此我们可以使用递归的算法进行求解，代码如下：

#include <stdio.h>

/*计算n的阶乘*/
int factorial(int n)
{
  if (n == 0)
  {
    return 1;
  }
  else
  {
    return n * factorial(n-1);
  }
}

int main(int argc, char* argv[])
{
  int i,result;
  printf("please input a number:");
  scanf("%d",&i);
  result = factorial(i);
  printf("result: %d! = %d\n",i,result);

  return 0;
}

计算整数的划分数。将一个正整数n表示程一系列的正整数之和，此问题的解决，也需要使用分治的算法进行解决，代码如下：

#include <stdio.h>

/*计算输入的正整数n的划分数*/
int P(int n, int m)
{
  if (m == 1 || n == 1) return 1;
  if(m > n) return P(n, n);
  if(m == n) return 1 + P(n, m - 1);
  return P(n, m - 1) + P(n - m, m);
}

int main(int argc, char* argv[])
{
  int n,s;
  printf("please input a integer for getting the number of division\n");
  scanf("%d",&n);
  s = P(n, n);
  printf("the number of division of %d is %d\n",n,s);

  return 0;
}

    分治算法的经典案例也就是递归的折半查找算法，此算法的前提是，数组中的元素排列顺序要不递增，要不递减。然后才可以使用此算法，代码如下：

#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 argc, char* argv[])
{
  int n,i,addr;
  int A[11] = {1,2,3,4,5,6,7,8,9,10,11};
  printf("the contents of the array A[11] are\n");
  for(i=0;i<11;i++)
  {
    printf("%d ",A[i]);
  }
  printf("\nplease input a integer for search\n");
  scanf("%d",&n);
  addr = bin_search(A, 0, 11, n);
  if (-1 != addr)
  {
    printf("%d is at the %dth unit is arry A\n", n,addr);
  }
  else
  {
    printf("there is no %d in array A\n", n);
  }

  return 0;
}

折半查找算法的执行结果如下：

peng@ubuntu:~/src/test/c/suanfa/miaoqu$ ./3.7

the contents of the array A[11] are

1 2 3 4 5 6 7 8 9 10 11

please input a integer for search

3

3 is at the 2th unit is arry A