F3[n]为Hanoi塔中3根柱子n个盘子的最少移动次数.pptVIP

F3[n]为Hanoi塔中3根柱子n个盘子的最少移动次数.ppt

  1. 1、本文档共51页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
递推法 在繁杂的世界变化中,许多现象的变化是有规律的,这种规律往往呈现出前因后果的关系。即某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。这一道理就体现了递推的思想。 有类试题,每相邻两项数之间的变化有一定规律性。通过分析考察,建立后项和前项之间的关系。然后从初始条件入手,一步步地按递推关系式递推,直至求出最终结果。如果对一个试题,我们要是能找到后一项数与前一项数的关系并清楚其起始条件,问题就比较容易解决,让计算机一步步计算就可以了。 例4:杨辉三角 分析 组合公式的证明: 昆虫繁殖 科学家在热带森林中发现了一种特殊的昆虫,这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵,每对卵要过两个月长成成虫。假设每个成虫不死,第一个月只有一对成虫,且卵长成成虫后的第一个月不产卵(过X个月产卵),问过Z个月以后,共有成虫多少对?x=1,y=1,z=x 输入:x,y,z的数值 输出:成虫对数 示例: 输入:x=1 y=2 z=8 输出:37 分析 首先我们来看样例:每隔1个月产2对卵,求过8月(即第8+1=9月)的成虫个数 分析 设数组A[i]表示第i月新增的成虫个数。 由于新成虫每过x个月产y对卵,则可对每个A[i]作如下操作: A[i+k*x+2]:=A[i+k*x+2]+A[i]*y (1=k,i+k*x+2=z+1) 因为A [i]的求得只与A[1]~A[i-1]有关,即可用递推求法。 则总共的成虫个数为: 例6:实数数列 一个实数数列共有N项,已知 ai=(ai-1-ai+1)/2+d,(1IN) (N60) 键盘输入N,d,a1,an,m,输出am。 输入数据均不需判错。 分析 根据公式ai=(ai-1-ai+1)/2+d 变形得,ai+1=ai-1-2ai+2d,因此该数列的通项公式为:ai=ai-2-2ai-1+2d,已知a1,如果能求出a2,这样就可以根据公式递推求出am ∵ ai=ai-2-2ai-1+2d ……(1) =ai-2-2(ai-3-2ai-2+2d)+2d =-2ai-3+5(ai-4-2ai-3+2d)-2d =5ai-4-12ai-3+8d …… 一直迭代下去,直到最后,可以建立ai和a1与a2的关系式。 分析 设ai=Pia2+Qid+Ria1,我们来寻求Pi,Qi,Ri的变化规律。 ∵ ai=ai-2-2ai-1+2d ∴ ai=Pi-2a2+Qi-2d+Ri-2a1-2(Pi-1a2+Qi-1d+Ri-1a1)+2d =(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1 ∴ Pi=Pi-2-2Pi-1 ……② Qi=Qi-2-2Qi-1+2 ……③ Ri=Ri-2-2Ri-1 ……④ 显然,P1=0 Q1=0 R1=1 (i=1) P2=1 Q2=0 R2=0 (i=2) 将初值P1Q1R1和P2Q2R2代入②③④可以求出PnQnRn ∵ an=Pna2+Qnd+Rna1 ∴ a2=(an-Qnd+Rna1)/Pn 然后根据公式①递推求出am,问题解决。 改进算法 但仔细分析,上述算法有一个明显的缺陷:在求由于在求a2要运用除法,因此会存在实数误差,这个误差在以后递推求am的过程又不断的扩大。在实际中,当m超过30时,求出的am就明显偏离正确值。显然,这种算法虽简单但不可靠。 为了减少误差,我们可设计如下算法: ∵ ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a2 =Pi-2a4+Qi-2d+Ri-2a3 …… =Pi-2+kak+Qi-2+kd+Ri-2+kak-1 ∴ an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1 ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2 ……⑤ 根据公式⑤,可以顺推a2、a3、…、aM。虽然仍然存在实数误差,但由于Pn-k+2递减,因此最后得出的am要比直接利用公式①精确得多。 问题讨论:青蛙过河(Frog ) 大小各不相同的一队青蛙站在河左岸的石墩(记为A)上,要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1…Ym)和几个石墩(分别记为S1…Sn)。图示如下: 试题描述 青蛙的站队和移动方法规则如下: 每只青蛙只能站在荷叶、石墩,或者仅比它大一号的青蛙背上(统称为合法的落脚点); 一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点; 青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上,允许从河心的石墩和荷叶跳到右岸的石墩

文档评论(0)

jdy261842 + 关注
实名认证
文档贡献者

分享好文档!

1亿VIP精品文档

相关文档