汉诺塔有这样一个传说:印度的一座寺庙里,有一座叠着 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 个圆盘,也是这个原因。
