第三章递归与分治策略05

1、 问题问题1：求：求n个整数个整数1,2,3,.,n之和之和 问题问题2：猴子吃桃：猴子吃桃 海滩上有一堆桃子，五只猴子来分： 第一只猴子把这堆桃子平均分为五份，多了一个，这只猴子把多的一个扔入海中，拿走了一份 第二只猴子把剩下的桃子又平均分成五份，又多了一个，它同样把多的一个扔入海中，拿走了一份 第三、第四、第五只猴子都是这样做 问海滩上原来最少有多少个桃子？换一个思路，求倒数第n个猴子面前的桃子数 f(n) 将要求解的较大规模的问题分割成k个更小规模的子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问

2、题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

3、nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的设计思想是，将一个难以直接解决的大问题，分治法的

4、设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的分割成一些规模较小的相同问题相同问题，以便各个击破，以便各个击破，分而治之。分而治之。 凡治众如治寡，分数是也。凡治众如治寡，分数是也。-孙子兵法孙子兵法3.1 3.1 直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经

5、常同时应用在算法设计之中，并由此产生许多高效算法。下面来看几个实例。3.1 3.1 例例1 1 阶乘函数阶乘函数阶乘函数可递归地定义为：00)!1(1!nnnnn边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。3.1 3.1 例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程110)2() 1(11)(nnnnFnFnF第n个Fibonacci数可递归地计算如下：publ

6、ic static int fibonacci(int n) if (n 1n1时，时，perm(R)perm(R)由由(r(r1 1)perm(R)perm(R1 1) )，(r(r2 2)perm(R)perm(R2 2) )，(r(rn n)perm(R)perm(Rn n) )构成。构成。 排列问题递归算法的程序实现排列问题递归算法的程序实现 递归函数的输入是什么？ 递归函数的出口条件什么？ 执行体是什么？ 这是最关键的，即如何分治的 如何显示结果？何时显示结果如何显示结果？何时显示结果 若定义递归函数为 void fn(String str) 尝试编程实现。 为便于输出结果，我定义递

7、归函数为 void fn(String str，String output) void fn(String str, String output) if (str.Length=1) output += str; Console.WriteLine(0, output); return; for (int i=0; istr.Length; i+) String substr = str.Remove(i, 1); fn(substr, output+stri); 3.1 3.1 例例5 5 整数划分问题整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nj，其中n1n2nj1，j

8、1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。 如何来分析这个问题? 利用分治的思想, 整数n的整数规划问题,可以分解为一系列子问题，即求 f(n, k) 1=k=1; j-) /这里要判断 j 是否大于6-4 fn(6-4, j); f(6, 4) = 4 + f(2, 1) f(6, 4) = 4 + f(2, 2) 如果前面的理解不了，可以思考一下求11的整数规划3.1 3.1

9、例例6 Hanoi6 Hanoi塔问题塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n1时，需要

10、利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。3.1 3.1 例例6 Hanoi6 Hanoi塔问题塔问题 public static void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-

11、1, c, b, a); /借助b, c塔，将n个盘从a移到d塔, 从上至下，序号分别为1, 2,.,nvoid HanoEx(int n, String a, String b, String c,String d) if(n=1) Move(n, a, d); else if (n=2) Move(n - 1, a, c); Move(n, a, d); Move(n - 1, c, d); else HanoEx(n-2, a, c, d, b); Move(n-1, a, c); Move(n, a, d); Move(n - 1, c, d); HanoEx(n - 2, b, a,

12、 c, d); 优点：优点：结构清晰，可读性强，而且容易用数学归纳结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。试程序带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是耗费的计递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多算时间还是占用的存储空间都比非递归算法要多解决方法：解决方法： 在递归算法中消除递归调用，使其转化为非递归算法。在递归算法中消除递归调用，使其转化为非递归算法。1.1.采用一个用户定义的栈来模拟系统的递归调用工作栈。采用一个用户定义的栈来模拟

13、系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。了本来由编译器做的事情，优化效果不明显。2.2.用用递推递推来实现递归函数。来实现递归函数。3.3.通过通过CooperCooper变换、变换、反演变换能反演变换能将一些递归转化为尾递将一些递归转化为尾递归，从而迭代求出结果。归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用后两种方法在时空复杂度上均有较大改善，但其适用范围有限。范围有限。练习练习1. 输入一个自然数(90000), 分别用递归法和非递归法求其二机制表示；

14、 如何求二进制？ 8%2=0； 8/2=4 4%2=0； 4/2=2 2%2=0； 2/2=1 1%2=1 这样，8的二进制表示为： 1000void Bin(int n, String str)void Bin(int n, String str) if (n2) str = n.ToString() + str; Console.WriteLine(str); return; int m=n%2; Bin(n / 2, m.ToString()+str); 2. 分别用递归法和非递归法求Fibonacci数列的前1000位，并比较计算时间的差异；3.用递归算法完成如下问题： 有52张牌，使

15、它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下,正面朝下的翻成正面朝上；第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，以此类推，直到第一张要翻的牌超过52为止。 统计最后有几张牌正面朝上，以及它们的位置号。 如何用分治的思想来求解该问题？ 若把翻51次牌作为一个任务，利用分治可以逐次减少任务的总量 数据结构 可以定义一个布尔值的数组，翻到某一张牌，就是将该位置的布尔值取反bool poker52; for (int i = 1; i 51) return; for( int i=

16、n; i52; i+=i) pokeri=!pokeri; Turn(n+1);Void main() Turn(2); 4. 在88格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 八皇后分析求解过程八皇后分析求解过程 四皇后的枚举算法如何设计？ 八皇后的分治求解思想如何体现？ 如何记录已放置的皇后信息？ 如何判断某一空位是否与已放皇后冲突？ 如何编写递归程序？ 如何输出求解结果？实现过程实现过程 用一个88数组来表示棋盘，初始化时，每一个位置为0，表示没有放置皇后int, a = new int8, 8;for (int i

17、 = 0; i 8; i+) for (int j = 0; j 8; j+) ai, j = 0; 判断某一个空位 (x, y) 是否适合放置皇后 bool IsValid (int x, int y) for (int i = 0; i 8; i+) for (int j = 0; j 8; j+) if (ai, j = 1) if (x = i | y = j | x + y = i + j | x - y = i - j) return false; return true; 递归过程：从0行开始逐行递进，是一个搜索行空间逐步减少的过程：Queen(int n) /n为行值 if(n=8) 输出；return; void Queen(int n) 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可