算法入门2:分治算法(上)

https://blog.csdn.net/jarvischu/article/details/14179335


上一篇中讲解了算法的基本概念,算法许许多多,按照算法基本思想,大致可分为如下几类:分治算法、贪心算法、动态规划、回溯法、分支限界、概率算法和随机算法等等。这一篇讲解分治算法。

分治算法

分治即分而治之。一个问题规模过大不容易直接解决,就可以划分成许多小问题,如果小问题不容易求解,那么可以再划分成规模更小的问题,直到规模小到很容易解决为止,解决这些小问题,再将小问题的解合并成大问题的解。这就是分治算法的基本思想。

 

至于小问题的规模到底划分多大,这是没有规定的,依实际情况而定。小问题的规模可以是相等的,也可以是不相等的。可以分成简单的2个小问题,当然也可以分成多个小问题。

 

分治算法常用的实现方法是递归。因为分治就是将大问题不断划分成小问题,递归的解决小问题,再合并小问题的解就可以得到问题的解。

 

递归

递归,就是在函数内部调用本函数自身。形式如下

void foo()

{

         //...

         foo();   //递归

         //...

}

 

下面举几个递归的典型例子。

 

阶乘

n! = n*(n-1)! 这就是一个递归

如果F(n)代表求解n!,那么F(n) = n * F(n-1)

  1. int f(int n)
  2. {
  3. if(n==1)
  4. {
  5. return 1;
  6. }
  7. return n*f(n-1);
  8. }

Fibonacci数列

其定义为

 

  1. int f(int n)
  2. {
  3. if(n==0 || n==1)
  4. return 1;
  5. return f(n-1)+f(n-2);
  6. }

汉诺塔问题

A,B,C三个塔座,将A上的N个盘子移动到C上,保证大的盘子不会放在小的盘子上。

  1. //直接将塔座from最上面的盘子移动到塔座to上
  2. void move(char from,char to)
  3. {
  4. cout<<"Move:"<<from<<" -->"<<to<<endl;
  5. }
  6. //n个盘子,从A移动到C,借助B
  7. void hanoi(int n,char A,char B,char C)
  8. {
  9. if(n>0)
  10. {
  11. hanoi(n-1,A,C,B); //首先将A中上面的n-1个盘子,从A移动到B,借助C
  12. move(A,C); //然后将A中最下面的盘子直接移动到C
  13. hanoi(n-1,B,A,C); //最后,将B上的n-1个盘子移动到C,借助A
  14. }
  15. }
  16. int main()
  17. {
  18. hanoi(3,'A','B','C');
  19. return 0;
  20. }

PS: 博主用MFC实现了一个汉诺塔的动画效果。如有兴趣可留邮箱索要源码。(代码中还存在bug,但基本功能可用)可以单步运行移动,也可以自动执行移动。


全排列问题

 

输出N个数的全排列的结果。

比如当N=3,三个数为1,2,3时 ,全排列为:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

 

N个数的全排列为Perm(N),也就是等于把N个数分别替换到第一位时的所有排列,即Perm(N) = 1_Perm(N-1) + 2_Perm(N-1)+…+N_Perm(N-1)

以上面的为例,Perm(N)就是1,2,3的全排列,1_Perm(N-1)就是 1,2,3 和 1,3,2

2_Perm(N-1)就是2,1,3和2,3,1。

同理可以对Perm(N-1)再递推到Perm(N-2)

 下面是代码,有详细的注释

  1. /************************************************************************
  2. * 名 称:Perm.cpp
  3. * 功 能:分治算法案例:使用递归解决全排列问题(对n个数进行全排列)
  4. * 作 者:JarvisChu
  5. * 时 间:2013-11-1
  6. ************************************************************************/
  7. #include <iostream>
  8. using namespace std;
  9. const int N=5; //常量,数组(序列)大小
  10. /*----------------------------------------------------------------------------------
  11. * 功 能: 交换两个数
  12. * 参 数: a,b为要交换的元素
  13. * 返 回:无
  14. ------------------------------------------------------------------------------------*/
  15. void swap(int& a,int& b)
  16. {
  17. int tmp = a;
  18. a=b;
  19. b=tmp;
  20. }
  21. /*----------------------------------------------------------------------------------
  22. * 功 能: 输出数组arr中,从arr[start]到arr[end]的全排列
  23. * 参 数: arr: 要全排列的数组
  24. start: 要全排列数组段的起始位置下标,数组arr中 0到start-1位置已经排好
  25. end: 要全排列的数组段的结束位置下标,arr[start]到arr[end]为待排数组段
  26. * 返 回:无
  27. ------------------------------------------------------------------------------------*/
  28. void Perm(int* arr,int start,int end)
  29. {
  30. if(start == end) //起点和终点位置重合,只剩最后一个元素了,说明arr已经全部排好了,此时输出结果
  31. {
  32. for(int i=0;i<N;++i)
  33. cout<<arr[i]<<" ";
  34. cout<<endl;
  35. }
  36. else //有数据要排列
  37. {
  38. for(int j=start;j<=end;++j)
  39. {
  40. swap(arr[start],arr[j]);//将j位置的数,放到start位置
  41. Perm(arr,start+1,end); //递归排序
  42. swap(arr[start],arr[j]);//交换回来
  43. }
  44. }
  45. }
  46. int main()
  47. {
  48. int data[N];
  49. for(int i=0;i<N;i++)
  50. {
  51. data[i] = i+1; //N个数,从1到N
  52. }
  53. Perm(data,0,N-1);
  54. return 0;
  55. }

代码的图解:

数组arr中 0到start-1位置已经排好, arr[start]到arr[end]为待排数组段。

初始时,start=0,end=N-1,说明要把arr[0]到arr[N-1]全排列输出

 

 如果start==end,说明待排的长度为0,要么是前面的已经全部排好了,要么就是数字长度为0,总之直接输出结果就好

 

否者,说明待排的长度不为0。要排列arr[start]到arr[end],方法就是分别把每个元素放到start位置,来一次交换

 

交换后如图


交换后,在对递归排列start-1 到end位置

递归结束后,还需要把start和j的位置再调换回来,以便后面start和j+1的位置进行调换。


下一篇继续讲解分治算法的其他几个案例。


转载本文请注明作者和出处

作者 :JarvisChu

出处:http://blog.csdn.net/jarvischu


原文链接:加载失败,请重新获取