搜索
当前位置: 678彩票官网 > 递归算法 >

请教高人 递归算法编写思路技巧

gecimao 发表于 2019-04-18 14:23 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部一个子程序(过程或函数)的定义中又直接或间接地调用该子程序本身,称为递归。递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清晰,具有很好的可读性。递归算法的基本思想是:把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题,并且小到一定程度可以直接得出它的解,从而得到原来问题的解。

  一、决定问题规模的参数。需要用递归算法解决的问题,其规模通常都是比较大的,在问题中决定规模大小(或问题复杂程度)的量有哪些?把它们找出来。

  二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解?这就是问题的边界条件及边界值。

  三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题,需要通过哪些步骤或等式来实现?这是解决递归问题的难点。把这些步骤或等式确定下来。

  分析: 当 n = 0 或 n = 1 时,多项式的值都可以直接求出来,只是当 n > 1 时,才使问题变得复杂,决定问题复杂程度的参数是 n 。根据题目提供的已知条件,我们也很容易发现,问题的边界条件及边界值有两个,分别是:当 n = 0 时 P n (x) = 1 和当 n = 1 时 P n (x) = x 。解决问题的通式是:

  例 2 : Hanoi 塔问题:传说印度教的主神梵天创造世界时,在印度北部佛教圣地贝拿勒斯圣庙里,安放了一块黄铜板,板上插着三根宝石针,在其中一根宝石针上,自下而上地放着由大到小的 64 个金盘。这就是所谓的梵塔( Hanoi ),如图。梵天要求僧侣们坚持不渝地按下面的规则把 64 个盘子移到另一根针上:

  梵天宣称,当把他创造世界之时所安放的 64 个盘子全部移到另一根针上时,世界将在一声霹雳声中毁灭。那时,他的虔诚的信徒都可以升天。

  分析: 为了使问题更具有普遍性,设共有 n 个金盘,并且将金盘由小到大依次编号为 1 , 2 ,…, n 。要把放在 s(source) 针上的 n 个金盘移到目的针 o(objective) 上,当只有一个金盘,即 n = 1 时,问题是比较简单的,只要将编号为 1 的金盘从 s 针上直接移至 o 针上即可。可定义过程 move(s,1,o) 来实现。只是当 n1 时,才使问题变得复杂。决定问题规模的参数是金盘的个数 n ;问题的边界条件及边界值是:当 n = 1 时, move(s,1,o) 。

  当金盘不止一个时,可以把最上面的 n - 1 个金盘看作一个整体。这样 n 个金盘就分成了两个部分:上面 n - 1 个金盘和最下面的编号为 n 的金盘。移动金盘的问题就可以分成下面三个子问题(三个步骤):

  (3) 借助 s 针,将 i 针上的 n - 1 个金盘(依照上述法则)移至 o 针上。如图

  其中第二步只移动一个金盘,很容易解决。第一、第三步虽然不能直接解决,但我们已经把移动 n 个金盘的问题变成了移动 n - 1 个金盘的问题,问题的规模变小了。如果再把第一、第三步分别分成类似的三个子问题,移动 n - 1 个金盘的问题还可以变成移动 n - 2 个金盘的问题,同样可变成移动 n - 3 ,…, 1 个金盘的问题,从而将整个问题加以解决。

本文链接:http://windsorflowers.net/diguisuanfa/108.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部