递归算法课件.ppt

《递归算法课件.ppt》由会员分享，可在线阅读，更多相关《递归算法课件.ppt（38页珍藏版）》请在三一办公上搜索。

1、第四章 递归算法,1,t课件,前面已经介绍了关于递归调用这样一种操作，而递归程序设计是C+语言程序设计中的一种重要的方法，它使许多复杂的问题变得简单，容易解决了。递归特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。,2,t课件,【例1】 给定n（n=1）,用递归的方法计算1+2+3+4+.+(n-1)+n。 【算法分析】 本题可以用递归方法求解，其原因在于它符合递归的三个条件： (1)本题是累加问题：当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同s(n)=s(n-1)+n; (2)给定n,所以是有限次的递归调用；

2、 (3)结束条件是当n=1，则s=1。 【参考程序】#includeusing namespace std;int fac(int); /递归函数int main()int t;cint; /输入t的值couts=fac(t)endl; /计算1到t的累加和，输出结果int fac(int n)if (n=1) return 1;return(fac(n-1)+n); /调用下一层递归,3,t课件,运行程序，当T=5时，输出结果：S=15，其递归调用执行过程是：（设T=3）,递归调用过程，实质上是不断调用过程或函数的过程，由于递归调用一次，所有子程序的变量（局部变量、变参等）、地址在计算机内部

3、都有用特殊的管理方法栈（先进后出）来管理，一旦递归调用结束，计算机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。,4,t课件,【例2】 设有N个数已经按从大到小的顺序排列，现在输入X，判断它是否在这N个数中，如果存在则输出：“YES” 否则输出“NO”。 【算法分析】 该问题属于数据的查找问题，数据查找有多种方法，通常方法是：顺序查找和二分查找，当N个数排好序时，用二分查找方法速度大大加快。二分查找算法： （1） 设有N个数，存放在A数组中，待查找数为X，用L指向数据的高端，用R指向数据的低端，MID指向中间： （2） 若X=AMID 输出 “YES”； （3）若XAMID则到

4、数据前半段查找：L不变，R=MID-1，计算新的MID值，并进行新的一段查找； （5）若LR都没有查找到，则输出“NO”。 该算法符合递归程序设计的基本规律，可以用递归方法设计。,5,t课件,【参考程序】 #include#includeusing namespace std;int a11;void search(int,int,int);int main() /主程序int k,x,L=1,R=10;coutak;cinx;search(x,L,R); system(pause); void search(int x,int top,int bot) /二分查找递归过程int mid; i

5、f (top=bot) mid=(top+bot)/2; /求中间数的位置,6,t课件,if (x=amid) coutYESendl; /找到就输出 else if (xamid) search(x,mid+1,bot); /判断在前半段还是后半段查找 else search(x,top,mid-1); else coutNOendl;,7,t课件,【例3】Hanoi汉诺塔问题 有N个圆盘，依半径大小（半径都不同），自下而上套在A柱上，每次只允许移动最上面一个盘子到另外的柱子上去（除A柱外，还有B柱和C柱，开始时这两个柱子上无盘子），但绝不允许发生柱子上出现大盘子在上，小盘子在下的情况，现要

6、求设计将A柱子上N个盘子搬移到C柱去的方法。 【算法分析】 本题是典型的递归程序设计题。 (1)当N=1 时，只有一个盘子，只需要移动一次:AC; (2)当N=2时，则需要移动三次： A-1 - B, A -2 - C, B -1- C. (3)如果N=3，则具体移动步骤为：,8,t课件,9,t课件,假设把第3步，第4步，第7步抽出来就相当于N=2的情况（把上面2片捆在一起，视为一片）：,10,t课件,所以可按“N=2”的移动步骤设计： 如果N=0，则退出，即结束程序;否则继续往下执行; 用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程mov(n-1, a,b,c); 将A柱上剩

7、下的一片直接移到C柱上; 用A柱作为协助过渡，将B柱上的（N-1）移到C柱上，调用过程mov (n-1,b,c,a)。【参考程序】 #includeusing namespace std;int k=0,n;void mov(int n,char a,char c,char b) /用b柱作为协助过渡，将a柱上的（n）移到c柱上if (n=0) return; /如果n=0，则退出，即结束程序mov(n-1,a,b,c ); /用c柱作为协助过渡，将a柱上的（n-1）片移到b柱上k+;cout cendl;mov(n-1,b,c,a ); /用a柱作为协助过渡，将b柱上的（n-1）移到c柱上,

8、11,t课件,int main() coutn;mov(n,a,c,b); ,12,t课件,程序定义了把n片从A柱移到C柱的过程mov (n,a,c,b)，这个过程把移动分为以下三步来进行： 先调用过程mov (n-1, a, b, c)，把(n-1)片从A柱移到B柱, C柱作为过渡柱; 直接执行 writeln(a, -, c)，把A柱上剩下的一片直接移到C柱上，; 调用mov (n-1,b,c,a)，把B柱上的(n-1)片从B移到C柱上，A柱是过渡柱。 对于B柱上的(n-1)片如何移到C柱，仍然调用上述的三步。只是把(n-1)当成了n，每调用一次，要移到目标柱上的片数N就减少了一片，直至减

9、少到n=0时就退出，不再调用。exit是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。 mov过程中出现了自己调用自己的情况，在Pascal中称为递归调用，这是Pascal语言的一个特色。对于没有递归调用功能的程序设计语言，则需要将递归过程重新设计为非递归过程的程序。,13,t课件,【例4】用递归的方法求斐波那契数列中的第N个数,【参考程序】#includeusing namespace std;int a11;int fib(int);int main() int m; cinm; coutfib(m)=fib(m); ,14,t课件,int fib(int n) if (n

10、=0) return 0; /满足边界条件，递归返回 if (n=1) return 1; /满足边界条件，递归返回 return (fib(n-1)+fib(n-2); /递归公式，进一步递归输入 15输出 fib(15)=610,15,t课件,【例5】集合的划分【问题描述】 设S是一个具有n个元素的集合，Sa1，a2，an，现将S划分成k个满足下列条件的子集合S1，S2，Sk ，且满足： 则称S1，S2，Sk是集合S的一个划分。它相当于把S集合中的n个元素a1 ，a2，an 放入k个（0kn30无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1 ，a2 ，an 放入k个无标号盒子中

11、去的划分数S(n，k)。【输入样例】setsub.in 23 7【输出样例】setsub.out 4382641999117305,16,t课件,【算法分析】 先举个例子，设S1，2，3，4，k3，不难得出S有6种不同的划分方案，即划分数S(4，3)=6，具体方案为：1，234 1，324 1，4232，314 2，413 3，412 考虑一般情况，对于任意的含有n个元素a1 ，a2，an的集合S，放入k个无标号的盒子中去，划分数为S(n，k)，我们很难凭直觉和经验计算划分数和枚举划分的所有方案，必须归纳出问题的本质。其实对于任一个元素an，则必然出现以下两种情况： 1、an是k个子集中的一个

12、，于是我们只要把a1，a2，an-1 划分为k1子集，便解决了本题，这种情况下的划分数共有S(n1，k1)个； 2、an不是k个子集中的一个，则an必与其它的元素构成一个子集。则问题相当于先把a1，a2，an-1 划分成k个子集，这种情况下划分数共有S(n1，k)个；然后再把元素an加入到k个子集中的任一个中去，共有k种加入方式，这样对于an的每一种加入方式，都可以使集合划分为k个子集，因此根据乘法原理，划分数共有k * S(n1，k)个。,17,t课件,综合上述两种情况，应用加法原理，得出n个元素的集合a1，a2，an划分为k个子集的划分数为以下递归公式：S(n，k)S(n1，k1) + k

13、 * S(n1，k) (nk，k0)。 下面，我们来确定S(n，k)的边界条件,首先不能把n个元素不放进任何一个集合中去，即k=0时，S(n，k)0；也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即kn时,S(n，k)0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是1，即k=1或k=n时，S(n,k)=1。 因此，我们可以得出划分数S(n，k)的递归关系式为： S(n，k)S(n1，k1) + k * S(n1，k) (nk，k0) S(n，k)0 (nk)或(k0) S(n，k)1 (k=1)或(kn),18,t课件,【参考程序】 #includeu

14、sing namespace std;int s(int n, int k) /数据还有可能越界，请用高精度计算 if (n n k; cout s(n,k); return 0;,19,t课件,【例6】数的计数(Noip2001)【问题描述】我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n1000），然后对此自然数按照如下方法进行处理：不作任何处理；在它的左边加上一个自然数，但该自然数不能超过原数的一半；加上数后，继续按此规则进行处理，直到不能再加自然数为止。输入：自然数n（n1000）输出：满足条件的数【输入样例】 6 满足条件的数为 6 (此部分不必输出)

15、16 26 126 36 136【输出样例】 6,20,t课件,【方法一】用递归，f(n)=1+f(1)+f(2)+f(div/2)，当n较大时会超时，时间应该为指数级。【参考程序】#includeusing namespace std;int ans;void dfs(int m) /统计m所扩展出的数据个数 int i; ans+; /每出现一个原数，累加器加1； for (i = 1; i n; dfs(n); cout ans; return 0;,21,t课件,【方法二】：用记忆化搜索，实际上是对方法一的改进。设hi表示自然数i满足题意三个条件的数的个数。如果用递归求解，会重复来求一

16、些子问题。例如在求h4时，需要再求h1和h2的值。现在我们用h数组记录在记忆求解过程中得出的所有子问题的解，当遇到重叠子问题时，直接使用前面记忆的结果。【参考程序】#includeusing namespace std;int h1001;void dfs(int m) int i; if (hm != -1) return; /说明前面已经求得hm的值，直接引用即可，不需要再递归 hm = 1; /将hm置为1，表示m本身为一种情况 for (i = 1; i n; for (int i = 1; i = n; i+) hi = -1; /h数组初始化为-1 dfs(n); /由顶到下记忆化

17、递归求解 cout hn; return 0;,22,t课件,【方法三】 用递推，用h(n)表示自然数n所能扩展的数据个数，则h(1)=1, h(2)=2, h(3)=2, h(4)=4, h(5)=4, h(6)=6, h(7)=6, h(8)=10, h(9)=10.分析以上数据，可得递推公式：h(i)=1+h(1)+h(2)+h(i/2)。此算法的时间度为O(n*n)。设hi-i按照规则扩展出的自然数个数(1in)。下表列出了hi值及其方案：,23,t课件,【参考程序】#includeusing namespace std;int h10001;int main() int n; cin

18、 n; for (int i = 1; i = n; i+) /按照递增顺序计算扩展出的自然数的个数 hi = 1; /扩展出的自然数包括i本身 for (int j = 1; j = i/2; j+) /i左边分别加上1自然数 按规则扩展出的自然数 hi += hj; cout hn; return 0;,24,t课件,【方法四】是对方法三的改进，我们定义数组s，s(x)=h(1)+h(2)+h(x),h(x)=s(x)-s(x-1)，此算法的时间复杂度可降到O(n)。【参考程序】#includeusing namespace std;int h1001,s1001;int main() i

19、nt n; cin n; for (int i = 1; i = n; i+) hi = 1 + si/2; si = si-1 + hi; /s是h的前缀累加和 cout hn; return 0;,25,t课件,【方法五】 还是用递推，只要作仔细分析，其实我们还可以得到以下的递推公式: (1)当i为奇数时，h(i)=h(i-1); (2)当i为偶数时,h(i)=h(i-1)+h(i/2).【参考程序】#includeusing namespace std;int h1001;int main() int n; cin n; h1 = 1; for (int i = 2; i = n; i+

20、) hi = hi-1; if (i % 2 = 0) hi = hi-1 + hi/2; cout hn; return 0;,26,t课件,【课堂练习】,1、输入一串以！结束的字符，按逆序输出。（用递归做）2、背包问题 问题：假设有n件质量分配为w1，w2，.，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+.+wik=T。若能，则背包问题有解，否则无解。(例如：有5件可选物品，质量分别为8千克、4千克、3千克、5千克、1千克。假设背包的最大转载质量是10千克。)3、阿克曼（Ackm

21、ann）函数A(x，y)中，x，y定义域是非负整数，函数值定义为：,写出计算Ack(m，n)的递归算法程序。,27,t课件,4、某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。 基本形式：D1=0;d2=1递归式：dn= (n-1)*( dn-1 + dn-2) 5、有52张牌，使它们全部正面朝上，从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；接着从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下,正面朝下的翻成正面朝上；接着第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，以此类推，直到第1张要翻的牌是第52张为止。统

22、计最后有几张牌正面朝上，以及它们的位置号。6、猴子吃桃问题猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉的一半，又多吃了一个。以后每天早上都吃掉了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘多少桃子。（答案：1534）,28,t课件,【上机练习】,1、斐波那切数列【问题描述】斐波那切数列0，1，1，2，3，5，8，13，21，34，55从第三项起，每一项都是紧挨着的前两项的和。写出计算斐波那切数列的任意一个数据项递归程序。【输入格式】输入所求的项数。【输出格式】 输出数据项的值。【输入样例】fbi.in 10【输出

23、样例】fbi.out 342、倒序数【问题描述】用递归算法写程序，输入一个非负整数，输出这个数的倒序数。【输入格式】输入一个非负整数。【输出格式】输出倒序结果。【输入样例】num.in 123【输出样例】num.out 321,29,t课件,3、十进制转换成八进制【问题描述】用递归算法，把任一给定的十进制正整数转换成八进制数输出。【输入格式】输入一个正整数，表示需要转换的十进制数。【输出格式】输出一个正整数，表示转换之后的八进制的数。【输入样例】change.in15【输出样例】change.out174、求N！的值【问题描述】 用递归算法，求N！的精确值(N以一般整数输入)。【输入样例】ni

24、.in 10【输出样例】ni.out 10!=3628800,30,t课件,5、求最大公约数【问题描述】 用递归方法求两个数m和n的最大公约数。(m0，n0) 【输入格式】 输入二个数，即m和n的值。【输出格式】 输出最大公约数。【输入样例】 8 6【输出样例】 gcd=2,31,t课件,6、双色Hanoi塔问题【问题描述】 设A、B、C是3 个塔座。开始时，在塔座A 上有一叠共n 个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1，2，n，奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移

25、动规则： 规则(1)：每次只能移动1 个圆盘； 规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则(3)：任何时刻都不允许将同色圆盘叠在一起； 规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C 中任一塔座上。,试设计一个算法，用最少的移动次数将塔座A 上的n个圆盘移到塔座B 上，并仍按同样顺序叠置。,32,t课件,【编程任务】 对于给定的正整数n，编程计算最优移动方案。【输入格式】 由文件hanoi.in给出输入数据。第1 行是给定的正整数n。【输出格式】 将计算出的最优移动方案输出到文件hanoi.out。文件的每一行由一个正整数k和2个字符c1和c2

26、组成，表示将第k个圆盘从塔座c1移到塔座c2上。【输入样例】3 【输出样例】1 A B2 A C1 B C3 A B1 C A2 C B1 A B,33,t课件,7、背包问题【问题描述】 简单的背包问题。设有一个背包，可以放入的重量为s。现有n件物品，重量分别为w1,w2，wn，（1in）均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。找到一组解即可。【输入格式】 第一行是物品总件数和背包的载重量，第二行为各物品的重量。【输出格式】 各所选物品重量。【输入样例】5 101 2 3 4 5【输出样例】number:1 weight:1number:4 weight:4numb

27、er:5 weight:5,34,t课件,8、2的幂次方（Noip1998）【问题描述】 任何一个正整数都可以用2的幂次方表示。例如： 137=27+23+20 同时约定方次用括号来表示，即ab 可表示为a（b）。 由此可知，137可表示为： 2（7）+2（3）+2（0） 进一步：7= 22+2+20 （21用2表示） 3=2+20 所以最后137可表示为： 2（2（2）+2+2（0）+2（2+2（0）+2（0） 又如： 1315=210 +28 +25 +2+1 所以1315最后可表示为： 2（2（2+2（0）+2）+2（2（2+2（0）+2（2（2）+2（0）+2+2（0）【输入格式】 正

28、整数（n20000）【输出格式】 符合约定的n的0，2表示（在表示中不能有空格）【输入样例】 137,【输出样例】2(2(2)+2+2(0)+2(2+2(0)+2(0),35,t课件,9、数的计数（Noip2001）【问题描述】 我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n（n1000）, 然后对此自然数按照如下方法进行处理： 1不作任何处理； 2在它的左边加上一个自然数，但该自然数不能超过原数(输入的n)的一半； 3加上数后，继续按此规则进行处理，直到不能再加自然数为止。【输入样例】 6 满足条件的数为 6 (此部分不必输出) 16 26 126 36 136

29、【输出样例】6,36,t课件,【编程任务】 给定正整数n 和m，计算出n 个元素的集合1,2, n 可以划分为多少个不同的由m 个非空子集组成的集合。【输入格式】 由文件stir.in提供输入数据。文件的第1 行是元素个数n和非空子集数m。【输出格式】 程序运行结束时，将计算出的不同的由m个非空子集组成的集合数输出到文件stir.out中。【输入样例】4 3 【输出样例】6【算法分析】 所求的是第2类Stirling数，通过可递推出如下递归式： S(n,m)=mS(n-1,m)+S(n-1,m-1); S(n,n+1)=0，S(n,0)=0，S(0,0)=1,37,t课件,10、集合划分问题【

30、问题描述】 n个元素的集合1,2, n 可以划分为若干个非空子集。例如，当n=4 时，集合1，2，3，4可以划分为15 个不同的非空子集如下：1，2，3，4， 1，2，3，4， 1，3，2，4， 1，4，2，3， 2，3，1，4，2，4，1，3， 3，4，1，2， 1，2，3，4， 1，3，2，4， 1，4，2，3，1，2，3，4， 1，2，4，3， 1，3，4，2， 2，3，4，1， 1，2，3，4 其中，集合1，2，3，4由1 个子集组成；集合1，2，3，4，1，3，2，4，1，4，2，3，1，2，3，4，1，2，4，3，1，3，4，2，2，3，4，1由2 个子集组成；集合1，2，3，4，1，3，2，4，1，4，2，3，2，3，1，4，2，4，1，3，3，4，1，2由3 个子集组成；集合1，2，3，4由4 个子集组成。,38,t课件,