宁德网站建设制作,如何学剪辑视频教程,沈阳网站建设服务电话,注册好网站以后怎么做汉诺塔也是经典的算法问题 文章目录1 汉诺塔问题1 汉诺塔问题
法国数学家卢卡斯#xff08;Edouard Lucas#xff09;在1883年提出了一个数学游戏#xff1a;
传说在世界中心贝拿勒斯#xff08;印度北部#xff09;的圣庙里#xff0c;一块黄铜板上有三根宝石柱。印度… 汉诺塔也是经典的算法问题 文章目录1 汉诺塔问题1 汉诺塔问题
法国数学家卢卡斯Edouard Lucas在1883年提出了一个数学游戏
传说在世界中心贝拿勒斯印度北部的圣庙里一块黄铜板上有三根宝石柱。印度教的主神大梵天在创造世界的时候在其中一根柱上从下到上地穿好了由大到小的64片金盘。大梵天命令僧侣们将圆盘从下面开始按大小顺序重新摆放在另一根柱子上并且规定 在小圆盘上不能放大圆盘在三根柱子之间一次只能移动一个圆盘。预言说当这些盘子移动完毕时世界就将在一声霹雳中消灭而梵塔、庙宇和众生也都将同归于尽。 考虑该问题的一般形式有 n 个圆盘最初自下而上、自大而小地穿在A柱上 每次按规则上述移动一个圆盘最终将所有圆盘移动到C柱上。
假如现在有如下图的盘子 则一共需要移动7次。自己手动画画就知道了。
那么现在盘子有n个如下图 该如何移动实际上这是递归的问题递归在后面的学习中会学到
先将A柱上所有其他盘子移到B柱上这是一个类似于自己的子问题只留下最下面的盘子也就是n盘子接着将最大的盘子从A柱移到C柱之后不必再管它。最后再将刚才移到B柱上的盘子移到C柱上这又是一个子问题 。
用 T(n) 表示移动 n 个圆盘所需要的步数
根据算法
先把前面 n-1 个盘子转移到B上然后把第 n 个盘子转到C上n这个盘子移动了一次最后再次将B上的 n-1 个盘子转移到C上这n-1个盘子移动了两次
得到递推关系 T(n)2T(n-1)1
这个公式足以使用递归的形式写出代码。下面还可以直接求出具体的值
使用倒推法求解T(n)2T(n-1)1, T(1)1: 回到最初的汉诺塔问题 要将64片金盘重新摆放在另一根柱子上 最少需要 264-1 步 即使僧侣每秒钟移动一步而且每次移动都是正确的方法 那么也需要 5.8*1011 年 即5千多亿年
