杭电ACM(lecture-03)递推课件_第1页
杭电ACM(lecture-03)递推课件_第2页
杭电ACM(lecture-03)递推课件_第3页
杭电ACM(lecture-03)递推课件_第4页
杭电ACM(lecture-03)递推课件_第5页
已阅读5页,还剩38页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、ACM程序设计第三讲 递推求解9/14/20221先来看一个超级简单的例题:有5人坐在一起,当问第5个人多少岁,他说比第4个人大2岁,问第4个人多少岁,他说比第3个人大2岁,依此下去,问第一个人多少岁,他说他10岁,最后求第5个人多少岁?如果所坐的不是5人而是n人,写出第n个人的年龄表达式。 9/14/20222显然可以得到如下公式:化简后的公式:F(n)=10+(n-1)*29/14/20223再来一个简单题:20139/14/202242013 蟠桃记 第一天悟空吃掉桃子总数一半多一个,第二天又将剩下的桃子吃掉一半多一个,以后每天吃掉前一天剩下的一半多一个,到第n天准备吃的时候只剩下一个桃

2、子。聪明的你,请帮悟空算一下,他第一天开始吃的时候桃子一共有多少个呢?9/14/20225Fibnacci 数列:即:1、2、3、5、8、13、21、349/14/20227思考:递推公式的伟大意义?有了公式,人工计算的方法?常见的编程实现方法?(优缺点?)注意:如果你不能直接求出解析式,可 用递推,但不要用递归9/14/20228简单思考题:在一个平面上有一个圆和n条直线,这些直线中每一条在圆内同其他直线相交,假设没有3条直线相交于一点,试问这些直线将圆分成多少区域。9/14/202210是不是这个F(1)=2; F(n) = F(n-1)+n;化简后:F(n) = n(n+1)/2 +1;

3、第n条直线与前n-1条直线有n-1个交点,第n条直线被分成n条线段,每条线段将一个区域一分为二9/14/202211太简单了?来个稍微麻烦一些的9/14/202212输入输出样例样例输入12样例输出279/14/202214思考2分钟:如何解决?9/14/202215结论:Fn = 2n ( 2n + 1 ) / 2 + 1 - 2n= 2 n2 n + 1为什么?9/14/202217总结:递推求解的基本方法:首先,确认:能否容易的得到简单情况的解?然后,假设:规模为N-1的情况已经得到解决。最后,重点分析:当规模扩大到N时,如何枚举出所有的情况,并且要确保对于每一种子情况都能用已经得到的数

4、据解决。强调:1、编程中的空间换时间的思想2、并不一定只是从N-1到N的分析9/14/202218编程中的空间换时间的思想2013蟠桃记程序一#includeint main()int n,i,s;while(scanf(%d,&n)!=EOF)s=1;for(i=2;i=n;i+) s=(s+1)*2;printf(%ldn,s);return 0;9/14/202219编程中的空间换时间的思想2013蟠桃记程序二#includeint main()int n,i,s; int a31; a1=1; for(i=2;i30;i+) ai=(ai-1+1)*2;while(scanf(%d,&

5、n)!=EOF)printf(%dn,an);return 0;9/14/20222064位整数的使用_int64 a60;printf(%I64dn,an)9/14/202221问题的提出: 设有n条封闭曲线画在平面上,而任何两条封闭曲线恰好相交于两点,且任何三条封闭曲线不相交于同一点,问这些封闭曲线把平面分割成的区域个数。思考题:平面分割方法9/14/202222某人写了n封信和n个信封,如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。 1465 不容易系列之一9/14/202224分析思路:1、当N=1和2时,易得解,假设F(N-1)和F(N-2)已经得到,重点分析下

6、面的情况:4、后者简单,只能是没装错的那封和第N封交换信封,没装错的那封可以是前面N-1封中的任意一个,故有 F(N-2) * (N-1)种两种情况相加F(N)= (N-1)(F(N-1)+F(N-2)3、前者,对于每种错装,可从N-1封信中任意取一封和第N封错装,故有F(N-1)*(N-1)种2、当有N封信的时候,前面N-1封信可以有N-1或者 N-2封错装9/14/202225在2n的长方形方格中,用n个12的骨牌铺满方格,例如n=3时,为23方格,骨牌的铺放方案有三种(如图), 输入n ,输出铺放方案的总数思考题(2046):9/14/202227归纳分析F(n-2)F(n-1)F(n)

7、=f(n-1)+f(n-2)9/14/202228有1n的一个长方形,用11、12、13的骨牌铺满方格。例如当n=3时为13的方格(如图),此时用11,12,13的骨牌铺满方格,共有四种铺法。 输入: n(0=n3)然后就是对n=4)1.若前n-1合法,则首尾不同,再添1个时,只有1种方法;2.若前n-1不合法,而添1个时合法,即只是因为首尾相同引起的不合法,这样前n-2必定合法。此时第n个的添 加有2种方法。3.f(1)=3;f(2)=6;f(3)=6.至此,可得。 9/14/2022391480_钥匙计数之二一把钥匙有N个槽,2N26槽深为1,2,3,4,5,6。每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5。求这样的钥匙的总数。 本题无输入对2N26,输出满足要求的钥匙的总数。 附加思考题(2):9/14/202240详见解题报告:/forum/read.php?tid=2294&page=1&toread=1仔细阅读,耐心品味,关键掌握从n-1到n的推导过程。9/14/202241Any question?9/14/202242课后任务:一、DIY在线作业(3):2008ACM ProgrammingExercise(3)_递推求解二、常规练习(包含以上作业)1290 献给杭电五十

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论