C语言递推与递归.pptx

千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 内容摘要递推算法递归算法计算组合数汉诺塔问题快速排序问题递归思想递推与递归千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推算法例题：古有善切饼者，名庖丙，庖丁之弟也。把一张大饼置于板上，不许离开，每一刀切下去都是一条直线。问切20刀最多能分成多少块？千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推算法a(n)表示切n刀可以分成的块数a(1)=1+1=2/切第1刀多出1块a(2)=2+2=4/切第2刀多出2块a(3)=4+3=7/切第3刀多出3块a(4)=7+4=11/切第4刀多出4块归纳后得到规律：a(n)=a(n-1)+n/切第n刀多出n块a(0)=1/不切时块数是1千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推算法编写函数cutpie求解切n刀后得到的块数千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推算法将复杂运算分解为若干重复的简单运算后一步骤建立于前一步骤之上计算每一步骤的方法相同从开始向后计算出结果使用循环结构，通过多次循环逐渐逼近结果a(i)a(i+1)=a(i)+i;a(0)a(1)a(n)千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推算法练习：递推数列：数列的每一项都可以通过前面若干项计算生成，可用递推公式定义练习：阶乘：1!,2!,3!,4!,(n-1)!,n!a(n)=n*a(n-1)/第n项通过第n1项乘n得到a(1)=1练习：斐波那契数列：1,1,2,3,5,8 a(n)=a(n-1)+a(n-2)a(0)=a(1)=1千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推算法练习：老人死后留下一堆枣子，ABCDE五兄弟要来分。A先来了后把枣子平均分成5份后发现多出1个，就取走了其中一份和多出来的1个。B来后把剩下的枣子平均分成5份发现多出1个，就取走了其中一份和多出来的1个。CDE来了之后，分别使用同样的做法。编程求解最初至少有多少枣子。思路提示：BCDE看到的个数肯定应该是4的倍数每人都能把枣子分成5份多一个，说明他们看到的枣子数应该是5的倍数加1从小到大找到一个同时满足上面条件的数，即为E看到的数目千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推算法千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递归算法若一个过程直接或间接的调用自己，这个过程就是递归的过程一个比较复杂的问题，如果可以分解成为几个相对简单或规模较小且解法相同或类似的子问题时，只要解决了这些子问题，那么原来的问题也就可以解决了。这种策略称为分而治之法比如：求10！，只要求出子问题 9!,乘上10就得到了10!;要求 9!,只要求出了8!,乘上9就得到了9!当分解出的子问题可以直接解决时，就停止分解。直接可以解决的子问题称为递归结束条件。比如：0!=1就是结束条件递归过程可以通过编写自我调用的递归函数来简单的解决千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递归算法切饼问题 a(n)=a(n-1)+n也可用以下递归方法求解n=0，返回1n0,返回 n-1 的结果加上n千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递归算法参数：1 计算cutpie(0)+1 返回(2)参数：2 计算cutpie(1)+2 返回(4)参数：3 计算cutpie(2)+3 返回(7)参数：4 计算cutpie(3)+4 返回(11)main函数参数：0 直接返回1 返回(1)千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递归算法练习：使用递归方法求解斐波那契数列第n项a(n);练习：用递归方法求两个整数m和n的最大公约若 m%n 为零是，n是m和n的最大公约数若 m%n 不为零，n和m%n 的最大公约数即为m和n的最大公约数练习：用递归的方法求整数1n的前n项和练习：让用户从键盘输入10个整数，逆序显示示例输入：1 2 3 4 5 9 10 0 9 8示例输出：8 9 0 10 9 5 4 3 2 1练习：从键盘输入底边长，在屏幕上打印倒三角形千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 计算组合数编程实现组合计数C(10,3)C(m,n)=1;当m=nC(m,n)=m;当n=1C(m,n)=C(m-1,n)+C(m-1,n-1)思路提示m个球取出来的n个，包含两种情况：n在其中和n不在其中编程实现使用递归思想编写递归函数 int cmn(int m,int n)千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 计算组合数千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 汉诺塔问题据说在古代印度bramah神庙中，有个和尚整天把3根柱子上的金盘倒来倒去。初始在柱子A上有64个盘子串在一起，每一个盘子都比它下面的盘子小，可以在ABC三个柱子之间互相移动，最终要全部移动到柱子C上。移动规则如下：每次只允许移动一个，且较大的盘子永远不能放在较小的盘子上。如果每秒移动一个的话，移完需要5800亿年。若初始时盘子数是n,编程求出移动的过程盘子从小到大（从上到下）编号依次为1,2 n-1,n千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 汉诺塔问题假如n=1，直接移动到C假如n=2，则需要先把1号盘移到B上，再把2号盘移动到C上，最后把1号盘移动到C上。(1)(2)(3)千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 汉诺塔问题假如初始时有n个盘，把1到n-1看作一个整体第一步把n-1个盘子，从A借助C移动到B第二步把第n个盘子，从A移动到B第三步把n-1个盘子，从B借助A移动到C编写递归函数void move(int n,char x1,char x2,char x3)表示x1上有n个盘，move函数需要把n个盘从x1上移动到x3上；x2上无盘，或x2上任何一个盘都比较x1上的所有的盘大；移动过程可以借助x2千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 汉诺塔问题千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 快速排序问题快速排序思路如下将要排序的数据放在数组array中取a0变在变量m中，通过分区处理把m排在适当的位置，使m左边的数都比m小，m右边的数都比m大按照常上面的思路分别处理m左边和右边的数据如果分区长度是1，停止处理使用递归函数编程void qsort(int array,int start,int end)把数组下标为start到end的元素进行快速排序千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 快速排序问题573814262738145625381476243815762435187624315876143258761234587612345678千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 快速排序问题千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递归思想递归定义阶乘函数 a(n+1)=a(n)*(n+1)幂函数(n+1)!=n!*(n+1)斐波那契数列 f(n)=f(n-1)+f(n-2)递归数据结构链表结构，结点next指向的也是一个链表树结构，每个结点下面都是一棵子树递归算法汉诺塔解法快速排序千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推与递归递推算法从头开始，通过循环迭代逐渐逼近结果使用循环语句执行效率高不易理解和写程序循环加大程序的复杂程序递归算法到着开始，每一次递归都缩小问题规模，直到问题足够小使用选择分支语句多次函数调用带来开销，效率低下比较自然的反应问题，容易理解和写程序程序清晰，结构简单千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推与递归从软件工程的角度来说，递归使用程序更加简单清晰从效率角度来说，递推会比递归效率高很多清晰 VS 效率一般选择使用递推代替递归，以适当的增加程序复杂性的代价来换取效率千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 其他问题？