算法之路(四)----汉诺塔(又称河内之塔)

汉诺塔是很简单也很经典的算法之一。 汉诺塔是根据一个传说形成的数学问题: 有三根杆子A,B,C 。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:

  • 1 每次只能移动一个圆盘;
  • 2 大盘不能叠在小盘上面。

提示:可将圆盘临时置于B杆,也可以将A杆移除的圆盘重新移动回A杆,但都必须遵循上述两条规则。 问:如何移?最少要移动多少次?

3个圆盘的汉诺塔移动

4个圆盘的汉诺塔移动

传说

最早发明这个问题的人是法国数学家爱德华*卢卡斯。 传说印度某间寺院有三根柱子,上串64个金盘。寺院里的僧侣依照一个古老的预言,以上述规则移动这些盘子;预言说当这些盘子移动完毕,世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说,还是他受他人启发。 若传说属实,僧侣们需要264− 1步才能完成这个任务;若他们每秒可完成一个盘子的移动,就需要5849亿年才能完成。整个宇宙现在也不过137亿年。 这个传说有若干变体:寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭,其中一说是位于越南河内,所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。 佛教中确实有“浮屠”()这种建筑;有些浮屠亦遵守上述规则而建。“河内塔”一名可能是由中南半岛在殖民时期传入欧洲的。

解答

如取N=64,最少需移动264− 1次。即如果一秒钟能移动一块圆盘,仍将需5849.42亿年。目前按照宇宙大爆炸理论的推测,宇宙的年龄仅为137亿年。 在真实玩具中,一般N=8;最少需移动255次。如果N=10,最少需移动1023次。如果N=15,最少需移动32767次;这就是说,如果一个人从3岁到99岁,每天移动一块圆盘,他最多仅能移动15块。如果N=20,最少需移动1048575次,即超过了一百万次。

解法

解法的基本思想是递归。假设有A、B、C 三个塔,A塔有N块盘,目标是把这些盘全部移动到C塔。那么先把塔顶部的N-1块盘移动到B塔,再把A塔剩下的大盘移动到C,最后把B塔的N-1块盘移动到C。 每次移动多于一块盘时,则再次使用上述算法来移动。

怎么来理解呢? 我们可以倒着理解,要将A塔上的所有圆盘移动到C塔,且所有圆盘是下大上小。那么必定有一个过程是最大的圆盘(也就是第N个圆盘)从A移动到C。那么必须保证上面的N-1个圆盘全在B塔,且圆盘满足上面小,下面大。当第N个圆盘从A移动到C之后,又得把N-1个圆盘从B塔移动到C塔,这样工作就完成了。 但是怎么把A塔上的N-1个圆盘移动到B塔呢? 这里需要一点想象力,可以想象成只有N-1个圆盘,从A塔移动到B塔(此时的B塔其实就相当于上面的C塔),我们称A塔为A1塔,B塔为C1塔,C塔为B1塔,那么问题就变成了如何将N-1个盘从A1塔移动到C1塔? 同样的需要将上面的N-2个圆盘从A1塔移动到B1塔,然后将第N-1个圆盘从A1塔移动到C1塔,然后再将B1塔上的N-2个圆盘移动到C1塔。 同理,递推第N-2个塔.....。

将 B塔上的 N-1个盘,移动到C塔的过程与上面原理一样。

递归解

以Objective-C语言实现:

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view from its nib.
    int n = 9;
    [self hannoi:n from:@"A" buffer:@"B" to:@"C"];
    NSLog(@"一共 %d 步",count);
}

- (void)hannoi:(int)n from:(NSString *)from buffer:(NSString *)buffer to:(NSString *)to
{
    if (n == 1) {
        NSLog(@"Move disk %d from %@ to %@", n, from, to);
    } else {
        [self hannoi:n-1 from:from buffer:to to:buffer];
        NSLog(@"Move disk %d from %@ to %@", n, from, to);
        [self hannoi:n-1 from:buffer buffer:from to:to];
    }
}

console : 一共 511 步

以C++语言实现:

using namespace std;
#include <iostream>
#include <cstdio>

void hannoi (int n, char from, char buffer, char to)
{
    if (n == 1) {
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
    } else {
        hannoi (n-1, from, to, buffer);
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
        hannoi (n-1, buffer, from, to);
    }
}

int main()
{
    int n;
    cin >> n;
    hannoi (n, 'A', 'B', 'C');
    return 0;
}

通过以上递归过程可知hannoi(n) = 2 * hannoi(n-1) + 1 ,hannoi(n) = 2n-1 + 2n-2 + 2n-3+ ...... + 22 + 2 +1。 对等比数列求和得出hannoi(n) = 2n -1。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏华章科技

穿越十年后看互联网+:家电行业的金矿在哪里?

现在市场上炒得火热的智能家居未来出路在何方?做智能家居的创业者应该注意哪些机会?传统家电厂商又到底如何借助互联网进行转型?本文以智能空调为例,用故事的形式,提前...

8210
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

28040
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.1K20
来自专栏儿童编程

天干地支五行八卦的对应关系

19090
来自专栏儿童编程

儿童创造力教育与编程教育的碰撞——MIT雷斯尼克教授最新理论梗概

儿童编程教育已经在我国各一线二线城市疯狂出现,颇有“烂大街”的趋势。我们不禁要问很多很多问题:

21870
来自专栏儿童编程

一张图理清《梅花易数》梗概

学《易经》的目的不一定是为了卜卦,但是了解卜卦绝对能够让你更好地了解易学。今天用一张思维导图对《梅花易数》的主要内容进行概括,希望能够给学友们提供帮助。

31340
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

17830
来自专栏儿童编程

《动物魔法学校》儿童学编程Scratch之“外观”部分

导读:本文通过一个案例《动物魔法学校》来学习Scratch语言的“外观”部分。之后通过一系列其他功能的综合运用对作品功能进行了扩展。

19140
来自专栏儿童编程

声音功能让儿童编程更有创造性

导读:Scratch中声音功能非常强大,除了常规的音效,你甚至可以模拟各种乐器的各个发音、设置节拍、休止……如果你愿意,甚至可以用它创作一个交响乐。我们可以引导...

13740
来自专栏儿童编程

我不是算命先生,却对占卜有了疑惑——如何论证“占卜前提”的正确与否

事出有因,我对《周易》感兴趣了很多年。只是觉得特别有趣,断断续续学习了一些皮毛。这几天又偶然接触到了《梅花易数》,觉得很是精彩,将五行八卦天干地支都串联了起来。...

14710

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励