厦门大学短学期acm班4讲解材料.ppt

  1. 1、本文档共28页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
厦门大学短学期acm班4讲解材料.ppt

厦门大学ACM班 * * 第四讲 递推求解 * * 先来看一个超级简单的例题: 有5人坐在一起,当问第5个人多少岁,他说比第4个人大2岁,问第4个人多少岁,他说比第3个人大2岁,依此下去,问第一个人多少岁,他说他10岁,最后求第5个人多少岁? 如果所坐的不是5人而是n人,写出第n个人的年龄表达式。 * * 显然可以得到如下公式: 化简后的公式: F(n)=10+(n-1)*2 * * Fibnacci 数列: 即:1、2、3、5、8、13、21、34… * * 思考: 有了公式,人工计算的方法? 常见的编程实现方法?(优缺点?) * * 简单思考题: 在一个平面上有一个圆和n条直线,这些直线中每一条在圆内同其他直线相交,假设没有3条直线相交于一点,试问这些直线将圆分成多少区域。 * * 是不是这个—— F(1)=2; F(n) = F(n-1)+n; 化简后: F(n) = n(n+1)/2 +1; * * 思考:如何用递推解决? 结论—— F(n)=F(n-1)+4(n-1)+1 * * 另外一种结论: Zn = 2n ( 2n + 1 ) / 2 + 1 - 2n = 2 n^2 – n + 1 为什么? * * 总结:递推求解的基本方法: 首先,确认:能否容易的得到简单情况的解? 然后,假设:规模为N-1的情况已经得到解决。 最后,重点分析:当规模扩大到N时,如何枚举出所有的情况,并且要确保对于每一种子情况都能用已经得到的数据解决。 强调: 1、编程中的空间换时间的思想 2、并不一定只是从N-1到N的分析 * * 问题的提出: 设有n条封闭曲线画在平面上,而任何两条封闭曲线恰好相交于两点,且任何三条封闭曲线不相交于同一点,问这些封闭曲线把平面分割成的区域个数。 思考题:平面分割方法 * * 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 * * 在2×n的长方形方格中,用n个1×2的骨牌铺满方格, 例如n=3时,为2×3方格,骨牌的铺放方案有三种(如图), 输入n ,输出铺放方案的总数 思考题(2046): * * 有1×n的一个长方形,用1×1、1×2、1×3的骨牌铺满方格。例如当n=3时为1×3的方格(如图),此时用1×1,1×2,1×3的骨牌铺满方格,共有四种铺法。 输入: n(0=n=30); 输出: 铺法总数 再思考题: * * 仔细分析最后一个格的铺法,发 现无非是用1×1,1×2,1×3三种铺法,很容易就可以得出: f(n)=f(n-1)+f(n-2)+f(n-3); 其中f(1)=1,f(2)=2,f(3)=4 典型例题 分析过程: * * 最后一个思考题(有点难度) * * 分析过程(1) 设:F(n)表示n个人的合法队列,则: 按照最后一个人的性别分析,他要么是男,要么是女,所以可以分两大类讨论: 1、如果n个人的合法队列的最后一个人是男,则对前面n-1个人的队列没有任何限制,他只要站在最后即可,所以,这种情况一共有F(n-1); * * 2、如果n个人的合法队列的最后一个人是女,则要求队列的第n-1个人务必也是女生,这就是说,限定了最后两个人必须都是女生,这又可以分两种情况: 分析过程(2)

文档评论(0)

youngyu0329 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档