开发者社区> 问答> 正文

求汉诺塔递归全过程的算法详解图,记得一定要是图释哦!!!

求汉诺塔递归全过程的算法详解图,记得一定要是图释哦!!!

展开
收起
知与谁同 2018-07-18 20:50:17 1408 0
2 条回答
写回答
取消 提交回答
  • 有三个圈至少要2的3次方减1次
    有四个圈至少要2的4次方减1次
    有五个圈至少要2的5次方减1次
    .........以此类推
    2019-07-17 22:54:56
    赞同 展开评论 打赏
  • 静静的看着你们
    图解是什么意思呀。
    这个算法 那么简单没必要搞得那么复杂吧。
    an = an-1 + 1;
    你明白这个等式的意义吗。
    这个等式已经包含了递归算法的全部含义。

    an 表示 n个数的和,an-1 表示n-1个数的和 ,an = an-1 + 1;表示n个数的和可以通过n-1个数的和来求的。
    上述说明哪些情况可以使用递归呢。
    那就是:已知前一个步骤可以求得后一个步骤的结果的情况,并且前一个步骤和后一个步骤是有规律过度的。
    比如汉诺塔问题:
    移n个盘是已移n-1个盘为条件的,两者的共同点是移盘。所以可以用f(n)表示移n个盘,f(n-1)表示移n-1个盘,那么移n个盘和移n-1个盘有什么关系呢。
    这就需要预先分析问题才能得出具体的关系
    在这个问题中,把n个盘从a移到c需要三个步骤来完成。
    1.n-1个盘从a移到b
    2 1个盘从a移到c
    3 n-1个盘从b移到c
    已知n-1个盘从a移到b是可行的,为什么。
    因为移1个盘是可行,那么移2个盘也是可行,移 3个盘是已移2个盘为条件的,所以移3个盘也是可行的,所以移n个 盘是可行的。
    所以根据已知条件可以解得:
    设f(n, a, b,c) 表示 把n个盘从a移到c 借助b --------------------------这里很关键,这是搞懂递归的关键关键。
    那么把n-1个盘从a移到b 借助c 怎样表示呢。
    很明显是:f(n-1, a, c,b)
    那么把1个盘从a移到c怎样表示呢?
    很明显是:f(1, a, b,c)
    那么把n-1个盘从b移到c 借助a 怎样表示呢。
    很明显是:f(n-1, b, a,c)

    所以f(n, a, b,c) = ( f(n-1, a,c,b) , f(1, a, b,c), f(n-1, b,a,c))
    这和等差等比数列一个原理。
    没有什么 特别的。

    记住是问题有这样递推关系才可以使用这种方法。
    如果要你计算1+2+8+22 的结果 你就不能使用递归。
    因为该问题的后一步骤与前一步骤不具有规律性,所以已知前一个步骤并不能求的后一个步骤的值
    1+2+3+4 ...+ 111111111111111111111111111111
    这个问题就可以使用递归
    原因你懂了吧。
    至于爬楼梯问题,无限级分类 问题等一些递归问题,那不过时小菜一碟。
    一句话:后一步骤依赖前一步骤并且二者联系具有规律性,运用递归必然成功。
    2019-07-17 22:54:56
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载