汉诺塔的解法

2020/01/06 310

算法 递归

什么是汉诺塔

汉诺塔(港台:河内塔)是根据一个传说形成的数学问题:

有三根杆子 X,Y,Z。X 杆上有 N 个 (N>=1) 穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 Z 杆:

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

提示:可将圆盘临时置于 Y 杆,也可将从 X 杆移出的圆盘重新移回 X 杆,但都必须遵循上述两条规则。

问:如何移,最少移动次数?

传说

最早发明这个问题的人是法国数学家爱德华·卢卡斯。

传说越南河内某间寺院有三根银棒,上串 64 个金盘。寺院里的僧侣依照一个古老的预言,以上述规则移动这些盘子;预言说当这些盘子移动完毕,世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说,还是他受他人启发。

若传说属实,僧侣们需要 2^64 - 1 步才能完成这个任务;若他们每秒可完成一个盘子的移动,就需要 5849 亿年才能完成。整个宇宙现在也不过 137 亿年。

这个传说有若干变体:寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭,其中一说是位于越南的河内,所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。

解法

static void HanoiTower(int n, char x, char y, char z)
{
    if (n == 1)
    {
        Console.WriteLine($"把 {n} 从 {x} -> {z}");
    }
    else
    {
        HanoiTower(n - 1, x, z, y);
        Console.WriteLine($"把 {n} 从 {x} -> {z}");
        HanoiTower(n - 1, y, x, z);
    }
}