递推求解new课件.ppt
《递推求解new课件.ppt》由会员分享,可在线阅读,更多相关《递推求解new课件.ppt(38页珍藏版)》请在三一文库上搜索。
1、2019/4/11,1,ACM 程序设计,计算机学院 刘春英,2019/4/11,2,今天,,你 了吗?,AC,2019/4/11,3,每周一星(2):,06057231杨振华,2019/4/11,4,第三讲 递 推 求 解,2019/4/11,5,先来看一个超级简单的例题:,有5人坐在一起,当问第5个人多少岁,他说比第4个人大2岁,问第4个人多少岁,他说比第3个人大2岁,依此下去,问第一个人多少岁,他说他10岁,最后求第5个人多少岁?,如果所坐的不是5人而是n人,写出第n个人的年龄表达式。,2019/4/11,6,显然可以得到如下公式:,化简后的公式: F(n)=10+(n-1)*2,201
2、9/4/11,7,再来一个简单题:,2019/4/11,8,再来一个简单题:,蟠桃记,2019/4/11,9,递推公式?,F(n)=(F(n-1)+1)*2,2019/4/11,10,Fibnacci 数列:,即:1、2、3、5、8、13、21、34,2019/4/11,11,思考:,递推公式的伟大意义?,有了公式,人工计算的方法?,常见的编程实现方法?(优缺点?),2019/4/11,12,简单思考题:,在一个平面上有一个圆和n条直线,这些直线中每一条在圆内同其他直线相交,假设没有3条直线相交于一点,试问这些直线将圆分成多少区域。,2019/4/11,13,是不是这个,F(1)=2; F(n
3、) = F(n-1)+n;,化简后: F(n) = n(n+1)/2 +1;,2019/4/11,14,太简单了?,来个稍微麻烦一些的,2019/4/11,15,例: (2050)折线分割平面,问题描述: 平面上有n条折线,问这些折线最多能将平面分割成多少块? 样例输入 1 2 样例输出 2 7,2019/4/11,16,思考2分钟:如何解决?,2019/4/11,17,结论:,Zn = 2n ( 2n + 1 ) / 2 + 1 - 2n = 2 n2 n + 1,为什么?,2019/4/11,18,趁热打铁,,来个差不多的,2019/4/11,19,说起佐罗,大家首先想到的除了他脸上的面具
4、,恐怕还有他每次刻下的“Z”字。我们知道,一个“Z”可以把平面分为2部分,两个“Z”可以把平面分为12部分,那么,现在的问题是:如果平面上有n个“Z”,平面最多可以分割为几部分呢? 说明1:“Z”的两端应看成射线 说明2:“Z”的两条射线规定为平行的,附加思考题(还没加到OJ): “佐罗”的烦恼,2019/4/11,20,总结:递推求解的基本方法:,首先确认,是否能很容易的得到简单情况的解,假设规模为N-1的情况已经得到解决,重点分析:当规模扩大到N时,如何枚举出所有的情况,并且要确保对于每一种子情况都能用已经得到的数据解决。,强调: 1、编程中的空间换时间的思想 2、并不一定是从N-1到N的
5、分析,2019/4/11,21,问题的提出: 设有n条封闭曲线画在平面上,而任何两条封闭曲线恰好相交于两点,且任何三条封闭曲线不相交于同一点,问这些封闭曲线把平面分割成的区域个数。,思考题:平面分割方法,2019/4/11,22,F(1)=2 F(n)=F(n-1)+2(n-1),2019/4/11,23,某人写了n封信和n个信封,如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。,1465 不容易系列之一,2019/4/11,24,分析思路:,1、当N=1和2时,易得解,假设F(N-1)和F(N-2)已经得到,重点分析下面的情况:,4、后者简单,只能是没装错的那封信和第N封
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 求解 new 课件
链接地址:https://www.31doc.com/p-2578716.html