当前位置：首页 - 正文

一文带你吃透汉诺塔和其变形题

发布网友发布时间：2023-02-26 11:56

共1个回答

热心网友时间：2023-06-26 18:46

汉诺塔（港台：河内塔）（Tower of Hanoi）是根据一个传说形成的数学问题：

有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

可以将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

我们从只有一个盘子的时候开始研究。很简单，直接把红色的盘子移到B上就可以了。

步骤：

此时两个盘子都在B上，并且红色盘子在*盘子上面

步骤：

根据上面的规律可以知道：

n盘子从A移动到B = 先把 n - 1 个盘子从A移动到C + 把最底下的盘子移动到B + 最后把 n - 1个盘子从C移动到B上

即：公式 H ( n ) = H ( n - 1 ) + 1 + H ( n - 1 )

现在思路清楚了，我们来讲它的两种解法：

假如有2N个盘子，盘子种类有N种，并且每种盘子有两个（这两个大小和颜色完全相同）

新2n盘子从A移动到B = 2 * 之前n个盘子移动次数

因此，依然有两种解法：

假如A和B直接不能直接移动，那么怎么解决？

步骤：

移动n个盘子需要的次数 = 通过C移动n-1个盘子到B的次数 + 把最底部移动到C上的次数 + 通过C再次移动n-1个盘子到A的次数 + 把最底部盘子移动到B上次数 + 通过C把n-1个盘子移动回B的次数

因此，依然有两种解法：

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。
E-MAIL:11247931@qq.com