Hanoi汉诺塔问题：古代有一个梵塔，塔内有3个柱子A、B、C，开始时，A柱上有64个金盘，金盘大小不等，大的在下，小的在上。有一个老和尚想把这64个金盘从A柱移动到C柱，但规定每次只允许移动一个盘，且在移动过程中在3个柱上都始终保持大盘在下，小盘在上。在移动过程中可以利用B柱。要求编程计算总共需要移动多少次盘子。据说移动完成就是世界的末日。

一、提出问题

我们先明确一下问题：

要把n 个盘子从 A 柱移动到 C 柱，
假设需要的移动次数是f(n)。

那我们想知道：
这个f(n)到底等于多少？

二、拆分问题

直接想 n 个盘子怎么移，会比较乱。
所以我们把它拆成三步来看。

要把 n 个盘子从 A 移到 C，
最关键的一步，是把最底下那个盘子从 A 移到 C。

那为了做到这一点，需要先做什么？

第一步：
把上面n-1 个盘子从 A 移到 B。
这一步需要的次数，就是f(n-1)。

第二步：
把最底下那个盘子，从 A 移到 C。
这一步只需要1 次。

第三步：
再把 B 上的n-1 个盘子移到 C。
这一步需要的次数，同样是f(n-1)。

所以总的移动次数就是：f(n)=f(n−1)+1+f(n−1)

合并一下：f(n)=2f(n−1)+1

三、边界条件

那 n 等于 1 的时候呢？

只有一个盘子，直接从 A 移到 C，
所以：

f(1)=1

这样我们就有了完整的递推关系：

f(n)=2f(n−1)+1, f(1)=1

四、展开递推

写成C语言的代码是：

long long hanoi_count(int n)
{
if (n == 1)
return 1;
else
return 2 * hanoi_count(n - 1) + 1;
}

或者更简洁：

long long f(int n)
{
return n == 1 ? 1 : 2 * f(n - 1) + 1;
}