C语言递推与递归.pptx
《C语言递推与递归.pptx》由会员分享,可在线阅读,更多相关《C语言递推与递归.pptx(25页珍藏版)》请在咨信网上搜索。
1、千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 内容摘要递推算法递归算法计算组合数汉诺塔问题快速排序问题递归思想递推与递归千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推算法例题:古有善切饼者,名庖丙,庖丁之弟也。把一张大饼置于板上,不许离开,每一刀切下去都是一条直线。问切20刀最多能分成多少块?千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.o
2、rg 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.m
3、obiletrain.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项通过第n
4、-1项乘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份多一个,说明他们看到的枣子数应该是5的倍数加1从小到大找到一个同时满足上面条件的数,即为E看到的数目千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递推算法千锋千锋3G嵌入式移动互联网技术研发中心嵌入式移动互联网技术研发中心www.mobiletrain.org www.embedtrain.org 递归算法若一个过程直接或间接的调用自己,这个过程就是递归的过程一个比较复杂的问题,如果可以分解成为几个相对简单或规模较小且解法相同或类似的子问题时,只要解决了这些子问题,那么原来的问
6、题也就可以解决了。这种策略称为分而治之法比如:求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嵌入式移动互联网技术研发
7、中心嵌入式移动互联网技术研发中心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的最大公
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 递归
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。