三柱 64 环：最少移动次数

the minimum number of moves you need to make to achieve the task?

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: QuantQuestion

题目详情

你面前有三根柱子，其中一根柱子上叠着 64 个圆环（上轻下重，最上 1 盎司，最下 64 盎司）。

目标是把所有圆环移动到另外两根柱子的其中一根上，并保持同样的顺序。

规则：一次只能移动一个圆环；只能从一根柱子移到另一根柱子；任何时候都不能把较重的环放在较轻的环上（即使临时也不行）。

问：最少需要多少步？

In front of you are three poles. One pole is stacked with 64 rings ranging in weight from one ounce (at the top) to 64 ounces (at the bottom). Your task is to move all the rings to one of the other two poles so that they end up in the same order. The rules are that you can move only one ring at a time, you can move a ring only from one pole to another, and you cannot even temporarily place a ring on top of a lighter ring.

What is the minimum number of moves you need to make to achieve the task?

解析

这是经典汉诺塔问题。设 $T(n)$ 为移动 $n$ 个环的最少步数，则

T(n)=2T(n-1)+1,

解得

T(n)=2^n-1.

因此 $n=64$ 时最少步数为

\boxed{2^{64}-1}.