你正在下载：《

(HDUACM)递推求解.ppt

》 [预览]

格式：PPT ，页数：32 ，大小：174.50KB ,
资源ID：12815625 下载积分：10 金币

快捷注册下载

登录下载

邮箱/手机：
温馨提示：	快捷下载时，用户名和密码都是您填写的邮箱或者手机号，方便查询和重复下载（系统自动生成）。如填写123，账号就是123，密码也是123。
特别说明：	请自助下载，系统不会自动发送文件的哦；如果您已付费，想二次下载，请登录后访问：我的下载记录
支付方式：
验证码：	换一换

开通VIP

温馨提示：由于个人手机设置不同，如果发现不能下载，请复制以下地址【https://www.zixin.com.cn/docdown/12815625.html】到电脑端继续下载（重复下载【60天内】不扣币）。

已注册用户请登录：

账号：
密码：
验证码：	换一换
当日自动登录忘记密码？

三方登录：

1、咨信平台为文档C2C交易模式，即用户上传的文档直接被用户下载，收益归上传人（含作者）所有；本站仅是提供信息存储空间和展示预览，仅对用户上传内容的表现方式做保护处理，对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿，我们不确定上传用户享有完全著作权，根据《信息网络传播权保护条例》，如果侵犯了您的版权、权益或隐私，请联系我们，核实后会尽快下架及时删除，并可随时和客服了解处理情况，尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确)，网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据，个别因单元格分列造成显示页码不一将协商解决，平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺，下载前须认真查看，确认无误后再购买，务必慎重购买；若有违法违纪将进行移交司法处理，若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传，付费前请自行鉴别，如您付费，意味着您已接受本站规则且自行承担风险，本站不进行额外附加服务，虚拟产品一经售出概不退款（未进行购买下载可退充值款），文档一经付费（服务费）、不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印，是因预览和防盗链等技术需要对页面进行转换压缩成图而已，我们并不对上传的文档进行任何编辑或修改，文档下载后都不会有水印标识（原文档上传前个别存留的除外），下载后原文更清晰；试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓；PPT和DOC文档可被视为“模板”，允许上传人保留章节、目录结构的情况下删减部份的内容；PDF文档不管是原文档转换或图片扫描而得，本站不作要求视为允许，下载前可先查看【教您几个在下载文档中可以更好的避免被坑】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用；网站提供的党政主题相关内容(国旗、国徽、党徽－－等)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
6、文档遇到问题，请及时联系平台进行协调解决，联系【微信客服】、【QQ客服】，若有其他问题请点击或扫码反馈【服务填表】；文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“【版权申诉】”，意见反馈和侵权处理邮箱：1219186828@qq.com；也可以拔打客服电话：0574-28810668；投诉电话：18658249818。

本文（(HDUACM)递推求解.ppt）为本站上传会员【精***】主动上传，咨信网仅是提供信息存储空间和展示预览，仅对用户上传内容的表现方式做保护处理，对上载内容不做任何修改或编辑。若此文所含内容侵犯了您的版权或隐私，请立即通知咨信网（发送邮件至1219186828@qq.com、拔打电话4009-655-100或【微信客服】、【 QQ客服】），核实后会尽快下架及时删除，并可随时和客服了解处理情况，尊重保护知识产权我们共同努力。
温馨提示：如果因为网速或其他原因下载失败请重新下载，重复下载【60天内】不扣币。【服务填表】

(HDUACM)递推求解.ppt

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,(HDUACM_03)递推求解,今天，,你了吗？,AC,12/10/2025,2,每周一星（2）：,Hoxily,12/10/2025,3,第三讲,递推求解,12/10/2025,4,先来看一个,超级,简单的,例题,:,有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他10岁，最后求第5个人多少岁？,如果所坐的不是5人而是n人，写出第n个人的年龄表达式。,12/10/2025,5,显然可以得到如下公式:,化简后的公

2、式:,F(n)=10+(n-1)*2,12/10/2025,6,Fibnacci 数列：,即：,1、2、3、5、8、13、21、34,12/10/2025,7,思考:,递推公式的意义？,有了公式，人工计算的方法？,常见的编程实现方法？（优缺点？）,12/10/2025,8,简单思考题:,在一个平面上有一个圆和n条直线，这些直线中每一条在圆内同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域。,12/10/2025,9,是不是这个,F(1)=2;,F(n)=F(n-1)+n;,化简后：,F(n)=n(n+1)/2+1;,12/10/2025,10,太简单了?,来个稍微麻烦一

3、些的,12/10/2025,11,例:（2050）折线分割平面,问题描述,：,平面上有n条折线，问这些折线最多能将平面分割成多少块?,样例输入,1,2,样例输出,2,7,12/10/2025,12,思考:如何用递推解决?,结论,F(n)=F(n-1)+4(n-1)+1,12/10/2025,13,另外一种结论:,Zn=2n(2n+1)/2+1-2n,=2 n2 n+1,为什么?,12/10/2025,14,总结：递推求解的基本方法：,首先，确认：能否容易的得到简单情况的解？,然后，假设：规模为N-1的情况已经得到解决。,最后，重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一

4、种子情况都能用已经得到的数据解决。,强调：,1、编程中的空间换时间的思想,2、并不一定只是从N-1到N的分析,12/10/2025,15,问题的提出：,设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。,思考题：平面分割方法,12/10/2025,16,F(1)=2,F(n)=F(n-1)+2(n-1),简单分析,1,1,3,2,4,1,2,3,4,6,5,7,8,1,2,3,4,5,6,7,10,8,9,11,12,13,14,n=1,n=2,n=3,n=4,2,12/10/2025,17,在2n的长方形方格

5、中,用n个12的骨牌铺满方格,例如n=3时,为23方格，骨牌的铺放方案有三种(如图),输入n,输出铺放方案的总数,思考题（2046）：,12/10/2025,18,有1n的一个长方形，用11、12、13的骨牌铺满方格。例如当n=3时为13的方格（如图），此时用11，12，13的骨牌铺满方格，共有四种铺法。,输入：,n（0=n3),然后就是对n=3 的一些特殊情况的处理了，显然：,F(0)=1,(没有人也是合法的，这个可以特殊处理，就像0的阶乘定义为1一样),F(1)=1,F(2)=2 F(3)=4,12/10/2025,26,不容易系列之(3)LELE的RPG难题,有排成一行的个方格，用红(R

6、ed)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色求全部的满足要求的涂法.,附加题（看看效果）：,12/10/2025,27,某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。,附加题：,1465不容易系列之一,12/10/2025,28,分析思路：,1、当N=1和2时，易得解，假设F(N-1)和F(N-2)已经得到，重点分析下面的情况：,4、后者简单，只能是没装错的那封和第N封交换信封，没装错的那封可以是前面N-1封中的任意一个，故=F(N-2)*(N-1),3、前者，对于每种错装，可从N-1封信中任意取一封和第N封错装，故=F(N-1)*(N-1),2、当有N封信的时候，前面N-1封信可以有N-1或者 N-2封错装,12/10/2025,29,得到如下递推公式：,基本形式：d1=0;d2=1递归式：dn=(n-1)*(dn-1+dn-2),这就是著名的错排公式,12/10/2025,30,课后任务：,DIY在线作业:,201003ACM程序设计在线作业（3）递推求解,12/10/2025,31,Welcome to HDOJ,Thank,You,12/10/2025,32,