汉诺塔有这样一个传说:印度的一座寺庙里,有一座叠着 64 个金圆盘的塔,僧侣们正按规则不停地移动圆盘。等到全部移完的那一刻,世界就会终结……

那么,要把 64 个圆盘移完,到底要花多长时间呢?

最少也要 2⁶⁴−1 次

圆盘有 n 个时,最少步数是 2ⁿ−1 次(原因在最少步数的文章里有说明)。64 个圆盘的话,就是

2⁶⁴−1 = 18,446,744,073,709,551,615 次

用日语的数量单位来说,约是 1845 京次(1 京 = 10¹⁶)。也就是 1 万亿的 1845 万倍。

如果每秒移动 1 步

假设僧侣不眠不休,每秒移动 1 步,而且一次都不出错。把 1 年按约 3155 万秒(365.25 天)来算,

18,446,744,073,709,551,615 秒 ÷ 31,557,600 秒 ≒ 5845 亿年

就是这么久。

比较对象年数
每秒 1 步移完 64 个圆盘约 5845 亿年
从宇宙诞生到现在约 138 亿年
从地球诞生到现在约 46 亿年

大约是宇宙年龄的 42 倍。就算传说是真的,看来也不用担心世界末日。

换成计算机会怎样

不用人手,而是让每秒能计算 10 亿步的计算机来走一遍步骤。即便如此,

18,446,744,073,709,551,615 ÷ 1,000,000,000 ≒ 184 亿秒 ≒ 约 585 年

也还是要花这么久。每一步的步骤明明很简单,但圆盘一多,步数就成倍地增加。这就是“指数增长”很直观的一个例子。

用手玩的话,最多能玩几个圆盘?

每秒移动 1 步,即使是最少步数,也要花下面这些时间。

圆盘个数最少步数每秒 1 步的用时
7 个127 次约 2 分钟
10 个1,023 次约 17 分钟
15 个32,767 次约 9 小时
20 个1,048,575 次约 12 天

如果想在休息的空当玩一局,7 个左右的长度正合适。“汉诺塔”应用里的“经典”模式用 7 个圆盘,也是这个原因。