Label the pegs A, B, C
let n be the total number of discs
number the discs from 1 (smallest, topmost) to n (largest, bottommost)
To move n discs from peg A to peg C:
一般的递归解决方案是这样的:
move n−1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
move n−1 discs from B to C so they sit on disc n
为什么我们不能这样想解决方案?
Move the top disk from A to B
Move the other n-1 disks from A to C
Move the single disk from B to C
我知道第二个解决方案是错误的,但我无法找出原因。有人可以指出为什么第二种解决方案不正确吗?
最佳答案
在你的第二个解决方案中,你将占用 B peg,它不能用于 n-1 盘。
这是因为您将最小的磁盘保留在 B Hook 中。因此,现在没有其他圆盘可以移动到 B,因为所有其他圆盘都比它大。
关于algorithm - 汉诺塔 - 替代解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30702793/