C语言递归算法ppt课件

1、第四章第四章 递归算法递归算法1;. 前面曾经引见了关于递归调用这样一种操作，而递归程序设计是C+言语程序设计中的一种重要的方法，它使许多复杂的问题变得简单，容易处置了。递归特点是：函数或过程调用它本人本身。其中直接调用本人称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。 2【例【例1】 给定给定nn=1,用递归的方法计算用递归的方法计算1+2+3+4+.+(n-1)+n。 【算法分析】【算法分析】 此题可以用递归方法求解，其缘由在于它符合递归的三个条件：此题可以用递归方法求解，其缘由在于它符合递归的三个条件： (1)此题是累加问题：当前和此题是累加问题：当前和=前一次和前一次和+当

2、前项，而前一次和的计算方法与其一样，只是数据不当前项，而前一次和的计算方法与其一样，只是数据不同同s(n)=s(n-1)+n; (2)给定给定n,所以是有限次的递归调用；所以是有限次的递归调用； (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;r

3、eturn(fac(n-1)+n); /调用下一层递归调用下一层递归 3 运转程序，当T=5时，输出结果：S=15，其递归调用执行过程是：设T=3 递归调用过程，本质上是不断调用过程或函数的过程，由于递归调用一次，一切子程序的变量部分变量、变参等、地址在计算机内部都有用特殊的管理方法栈先进后出来管理，一旦递归调用终了，计算机便开场根据栈中存储的地址前往各子程序变量的值，并进展相应操作。 4【例【例2】 设有设有N个数曾经按从大到小的顺序陈列，如今输入个数曾经按从大到小的顺序陈列，如今输入X，判别它能否在这，判别它能否在这N个数中，个数中，假设存在那么输出：假设存在那么输出：“YES 否那么输出

4、否那么输出“NO。 【算法分析】【算法分析】 该问题属于数据的查找问题，数据查找有多种方法，通常方法是：顺序查找和二分查该问题属于数据的查找问题，数据查找有多种方法，通常方法是：顺序查找和二分查找，当找，当N个数排好序时，用二分查找方法速度大大加快。二分查找算法：个数排好序时，用二分查找方法速度大大加快。二分查找算法： 1 设有设有N个数，存放在个数，存放在A数组中，待查找数为数组中，待查找数为X，用，用L指向数据的高端，用指向数据的高端，用R指向数据指向数据的低端，的低端，MID指向中间：指向中间： 2 假设假设X=AMID 输出输出 “YES； 3假设假设XAMID那么到数据前半段查找：那

5、么到数据前半段查找：L不变，不变，R=MID-1，计算新的，计算新的MID值，并进值，并进展新的一段查找；展新的一段查找； 5假设假设LR都没有查找到，那么输出都没有查找到，那么输出“NO。 该算法符合递归程序设计的根本规律，可以用递归方法设计。该算法符合递归程序设计的根本规律，可以用递归方法设计。 5【参考程序】【参考程序】 #include#includeusing namespace std;int a11;void search(int,int,int);int main() /主程序主程序int k,x,L=1,R=10;cout输入输入10个从大到小顺序的数：个从大到小顺序的数：e

6、ndl;for (k=1;kak;cinx;search(x,L,R); system(pause); void search(int x,int top,int bot) /二分查找递归过程二分查找递归过程int mid; if (top=bot) mid=(top+bot)/2; /求中间数的位置求中间数的位置 6 if (x=amid) coutYESendl; /找到就输出找到就输出 else if (xamid) search(x,mid+1,bot); /判别在前半段还是后半段查找判别在前半段还是后半段查找 else search(x,top,mid-1); else coutNO

7、C; (2)当当N=2时，那么需求挪动三次：时，那么需求挪动三次： A- 1 - B, A - 2 - C, B - 1- C. (3)假设假设N=3，那么详细挪动步骤为：，那么详细挪动步骤为：89 假设把第3步，第4步，第7步抽出来就相当于N=2的情况把上面2片捆在一同，视为一片：10 所以可按“N=2的挪动步骤设计： 假设N=0，那么退出，即终了程序;否那么继续往下执行; 用C柱作为协助过渡，将A柱上的N-1片移到B柱上，调用过程mov(n-1, a,b,c); 将A柱上剩下的一片直接移到C柱上; 用A柱作为协助过渡，将B柱上的N-1移到C柱上，调用过程mov (n-1,b,c,a)。【参

8、考程序】 #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 k :from a cendl;mov(n-1,b,c,a ); /用a柱作为协助过渡，将b柱上的n-1移到c柱上11int main() coutn;mov(n,a,c,b); 12 程序定义了把n片从A柱移到C柱的过程mov

9、 (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就减少了一片，直至减少到n=0时就退出，不再调用。exit是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。 mov过程中出现了本人调用本人

10、的情况，在Pascal中称为递归调用，这是Pascal言语的一个特征。对于没有递归调用功能的程序设计言语，那么需求将递归过程重新设计为非递归过程的程序。 13【例【例4】用递归的方法求斐波那契数列中的第】用递归的方法求斐波那契数列中的第N个数个数 【参考程序】【参考程序】#includeusing namespace std;int a11;int fib(int);int main() int m; cinm; coutfib(m)=k，k0)。w 下面，我们来确定S(n，k)的边境条件,首先不能把n个元素不放进任何一个集合中去，即k=0时，S(n，k)0；也不可以在不允许空盒的情况下把n个

11、元素放进多于n的k个集合中去，即kn时,S(n，k)0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是1，即k=1或k=n时，S(n,k)=1。w 因此，我们可以得出划分数S(n，k)的递归关系式为：w S(n，k)S(n1，k1) + k * S(n1，k) (nk，k0)w S(n，k)0 (nk)或(k0)w S(n，k)1 (k=1)或(kn)18w【参考程序】【参考程序】w #includewusing namespace std;wwint s(int n, int k) /数据还有可以越界，请用高精度计算数据还有可以越界，请用高精度计算ww if (n n

12、k;w cout s(n,k);w return 0;w19w【例【例6 6】数的计数】数的计数(Noip2001)(Noip2001)w【问题描画】【问题描画】w我们要求找出具有以下性质数的个数包括输入的自然数我们要求找出具有以下性质数的个数包括输入的自然数n n。先输入一个自然数。先输入一个自然数n nn1000n1000，然后对此自然数按照如下方法进展处置：，然后对此自然数按照如下方法进展处置：w不作任何处置；不作任何处置；w在它的左边加上一个自然数，但该自然数不能超越原数的一半；在它的左边加上一个自然数，但该自然数不能超越原数的一半；w加上数后，继续按此规那么进展处置，直到不能再加自然

13、数为止。加上数后，继续按此规那么进展处置，直到不能再加自然数为止。w输入：自然数输入：自然数n nn1000n1000w输出：满足条件的数输出：满足条件的数w【输入样例】【输入样例】w 6 6 满足条件的数为满足条件的数为 6 ( 6 (此部分不用输出此部分不用输出) )w 16 16w 26 26w 126 126w 36 36w w【输出样例】【输出样例】w 6 620【方法一】【方法一】用递归，用递归，f(n)=1+f(1)+f(2)+f(div/2)，当，当n较大时会超时，时间应该为指数级。较大时会超时，时间应该为指数级。【参考程序】【参考程序】#includeusing namesp

14、ace std;int ans;void dfs(int m) /统计统计m所扩展出的数据个数所扩展出的数据个数 int i; ans+; /每出现一个原数，累加器加每出现一个原数，累加器加1； for (i = 1; i n; dfs(n); cout ans; return 0; 21w【方法二】：用记忆化搜索，实践上是对方法一的改良。设【方法二】：用记忆化搜索，实践上是对方法一的改良。设hi表示自然数表示自然数i满足题意三个条满足题意三个条件的数的个数。假设用递归求解，会反复来求一些子问题。例如在求件的数的个数。假设用递归求解，会反复来求一些子问题。例如在求h4时，需求再求时，需求再求h

15、1和和h2的值。如今我们用的值。如今我们用h数组记录在记忆求解过程中得出的一切子问题的解，当遇到重叠数组记录在记忆求解过程中得出的一切子问题的解，当遇到重叠子问题时，直接运用前面记忆的结果。子问题时，直接运用前面记忆的结果。w【参考程序】【参考程序】w#includewusing namespace std;wint h1001;wvoid dfs(int m)ww int i;w if (hm != -1) return; /阐明前面曾经求得阐明前面曾经求得hm的值，直接援用即可，不需求再递归的值，直接援用即可，不需求再递归w hm = 1; /将将hm置为置为1，表示，表示m本身为一种情况

16、本身为一种情况w for (i = 1; i n;w for (int i = 1; i = n; i+)w hi = -1; /h数组初始化为数组初始化为-1w dfs(n); /由顶到下记忆化递归求解由顶到下记忆化递归求解w cout hn; w return 0;w22【方法三】【方法三】 用递推，用用递推，用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

17、(i)=1+h(1)+h(2)+h(i/2)。此算法的时间度为。此算法的时间度为O(n*n)。设设hi-i按照规那么扩展出的自然数个数按照规那么扩展出的自然数个数(1in)。下表列出了。下表列出了hi值及其方案：值及其方案：23w【参考程序】【参考程序】w#includewusing namespace std;wint h10001;wint main()ww int n;w cin n;w for (int i = 1; i = n; i+) /按照递增顺序计算扩展出的自然数的个数按照递增顺序计算扩展出的自然数的个数w w hi = 1; /扩展出的自然数包括扩展出的自然数包括i本身本身w

18、 for (int j = 1; j = i/2; j+) w /i左边分别加上左边分别加上1自然数自然数 按规那么扩展出的自然数按规那么扩展出的自然数w hi += hj; w w cout hn;w return 0;w24【方法四】【方法四】是对方法三的改良，我们定义数组是对方法三的改良，我们定义数组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() int n; cin

19、 n; for (int i = 1; i = n; i+) hi = 1 + si/2; si = si-1 + hi; /s是是h的前缀累加和的前缀累加和 cout hn; return 0;25【方法五】【方法五】 还是用递推，只需作仔细分析，其实我们还可以得到以下的递推公式还是用递推，只需作仔细分析，其实我们还可以得到以下的递推公式: (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

20、 n; cin n; h1 = 1; for (int i = 2; i = n; i+) hi = hi-1; if (i % 2 = 0) hi = hi-1 + hi/2; cout 0，n0) 【输入格式】【输入格式】 输入二个数，即输入二个数，即m和和n的值。的值。【输出格式】【输出格式】 输出最大公约数。输出最大公约数。【输入样例】【输入样例】 8 6【输出样例】【输出样例】 gcd=2316、双色、双色Hanoi塔问题塔问题【问题描画】【问题描画】 设设A、B、C是是3 个塔座。开场时，在塔座个塔座。开场时，在塔座A 上有一叠共上有一叠共n 个圆盘，这些圆盘自下而上，由大个圆盘，

21、这些圆盘自下而上，由大到小地叠在一同。各圆盘从小到大编号为到小地叠在一同。各圆盘从小到大编号为1，2，n，奇数号圆盘着蓝色，偶数号圆盘着红，奇数号圆盘着蓝色，偶数号圆盘着红色，如以以下图。现要求将塔座色，如以以下图。现要求将塔座A 上的这一叠圆盘移到塔座上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠置。在挪动上，并仍按同样顺序叠置。在挪动圆盘时应遵守以下挪动规那么：圆盘时应遵守以下挪动规那么： 规那么规那么(1)：每次只能挪动：每次只能挪动1 个圆盘；个圆盘； 规那么规那么(2)：任何时辰都不允许将较大的圆盘压在较小的圆盘之上；：任何时辰都不允许将较大的圆盘压在较小的圆盘之上； 规那么规那么(

22、3)：任何时辰都不允许将同色圆盘叠在一同；：任何时辰都不允许将同色圆盘叠在一同； 规那么规那么(4)：在满足挪动规那么：在满足挪动规那么(1)-(3)的前提下，可将圆盘移至的前提下，可将圆盘移至A，B，C 中任一塔座上。中任一塔座上。 试设计一个算法，用最少的挪动次数将塔座A 上的n个圆盘移到塔座B 上，并仍按同样顺序叠置。32【编程义务】【编程义务】 对于给定的正整数对于给定的正整数n，编程计算最优挪动方案。，编程计算最优挪动方案。【输入格式】【输入格式】 由文件由文件hanoi.in给出输入数据。第给出输入数据。第1 行是给定的正整数行是给定的正整数n。【输出格式】【输出格式】 将计算出的

23、最优挪动方案输出到文件将计算出的最优挪动方案输出到文件hanoi.out。文件的每一行由一个正整数。文件的每一行由一个正整数k和和2个字个字符符c1和和c2组成，表示将第组成，表示将第k个圆盘从塔座个圆盘从塔座c1移到塔座移到塔座c2上。上。【输入样例】【输入样例】3 【输出样例】【输出样例】1 A B2 A C1 B C3 A B1 C A2 C B1 A B337、背包问题、背包问题【问题描画】【问题描画】 简单的背包问题。设有一个背包，可以放入的分量为简单的背包问题。设有一个背包，可以放入的分量为s。现有。现有n件物品，分量分别为件物品，分量分别为w1,w2，wn，1in均为正整数，从均

24、为正整数，从n件物品中挑选假设干件，使得放入背包的分量之件物品中挑选假设干件，使得放入背包的分量之和正好为和正好为s。找到一组解即可。找到一组解即可。【输入格式】【输入格式】 第一行是物品总件数和背包的载分量，第二行为各物品的分量。第一行是物品总件数和背包的载分量，第二行为各物品的分量。【输出格式】【输出格式】 各所选物品分量。各所选物品分量。【输入样例】【输入样例】5 101 2 3 4 5【输出样例】【输出样例】number:1 weight:1number:4 weight:4number:5 weight:5348、2的幂次方的幂次方Noip1998【问题描画】【问题描画】 任何一个正

25、整数都可以用任何一个正整数都可以用2的幂次方表示。例如：的幂次方表示。例如： =27+23+20 同时商定方次用括号来表示，即同时商定方次用括号来表示，即ab 可表示为可表示为ab。 由此可知，可表示为：由此可知，可表示为： 27+23+20 进一步：进一步：7= 22+2+20 21用用2表示表示 3=2+20 所以最后可表示为：所以最后可表示为： 222+2+20+22+20+20 又如：又如： 1315=210 +28 +25 +2+1 所以所以1315最后可表示为：最后可表示为： 222+20+2+222+20+222+20+2+20【输入格式】【输入格式】 正整数正整数n20000【

26、输出格式】【输出格式】 符合商定的符合商定的n的的0，2表示在表示中不能有空格表示在表示中不能有空格【输入样例】【输入样例】 【输出样例】【输出样例】2(2(2)+2+2(0)+2(2+2(0)+2(0)359、数的计数、数的计数Noip2001【问题描画】【问题描画】 我们要求找出具有以下性质数的个数我们要求找出具有以下性质数的个数(包含输入的自然数包含输入的自然数n): 先输入一个自然数先输入一个自然数nn1000, 然后对此自然数按照如下方法进展处置：然后对此自然数按照如下方法进展处置： 1不作任何处置；不作任何处置； 2在它的左边加上一个自然数，但该自然数不能超越原数在它的左边加上一个自然数，但该自然数不能超越原数(输入的输入的n)的一半；的一半； 3加上数后，继续按此规那么进展处置，直到不能再加自然数为止。加上数后，继续按此规那么进展处置，直到不能再加自然数为止。【输入样例】【输入样例】 6 满足条件的数为满足条件的数为 6 (此部分不用输出此部分不用输出) 16 26 126 36 【输出样例】【输出样例】636【编程义务】【编程义务】 给