汉诺塔

这道题需要经过中间柱，所以可以把操作分为两类：

1. 移到中间柱子上
2. 从中间柱移除

根据汉诺塔的思路，我们可以把汉诺n个盘子分为这样几步:

1. 汉诺前$n-1$个盘子从起始柱子到中间柱子上
2. 汉诺前$n-1$个盘子从中间柱子移出到起始柱子上
3. 移动第$n$个柱子从起始柱子到中间柱（1步）
4. 汉诺前$n-1$个盘子从终点柱子到中间柱子上
5. 汉诺前$n-1$个盘子从中间柱子移出到终点柱子上
6. 移动第$n$个柱子从中间柱移除到终点柱子（1步）
7. 汉诺第$n-1$个柱子从起始柱子到终点柱（递归）
   由于从中间到两边是移动是对称的，所以花的步数是相同的。

令$hanoi2side(n)$表示汉诺$n$个盘子从中间柱到两边柱子最少花费的步数。

令$hanoi2mid(n)$表示汉诺$n$个盘子从两边柱子到中间柱最少花费的步数。

所以按照刚才的过程，汉诺$n$个盘子所需的步骤$hanoi(n)$为

$hanoii2mid(n-1)+hanoii2side(n-1)+1+hanoi2mid(n-1)+hanoii2side(n-1)+hanoi(n-1)$

$=2*(hanoi2mid(n-1)+hanoii2side(n-1)+1)+hanoi(n-1)$