3531. [POJ 1958]奇怪的汉诺塔

Charlie Darkbrown 参加了另一门无聊的电脑课：此刻，老师仅仅在解释标准的 Hanoi Tower 问题，这让 Charlie 感到极其无聊

老师指着黑板（图4）说：“这就是我们的问题。

• 有三个塔：A，B 和 C。
  
• 有 $n$ 个塔盘。在智力游戏中，$n$ 是一个常见的数。
  
• 每一个塔盘的大小均不相同。
  
• 塔盘最初堆叠在塔A上，从顶到底大小依次增加。
  
• 这个游戏的目标是把所有的塔盘从塔 A 移至塔 C。
  
• 一个塔盘如果可以移到另一个塔上，那么这个塔必定是一个空塔或者塔顶的塔盘比这个塔盘大

因此，你的任务就是编写一个程序，计算将所有塔盘从塔A移到塔C所需的最小移动次数。”

“这实在太无聊了——所有人都知道这可以用简单的递归解决。我拒绝编写这么简单的东西！”

Charlie说道。老师长叹一声，“好吧，Charlie，让我们考虑一下我能为你做些什么：为你提供第四层塔 D

请你计算把所有的塔盘从塔A移到塔D所需的最小步数！”

Charlie很生气：“额.....好吧，我不知道四个塔的最佳算法。”

所以真正要解决的问题并不是Charlie所擅长的。事实上，Charlie唯一擅长的事是“坐在能解决这个问题的人的旁边”

而现在，你正是坐在他身边的人，并且，他已经在瞄着你的屏幕了。

 一个整数 $n(1 \le n \le 12)$，表示总共有多少个塔盘在塔 A 上

 一个整数，表示把这 $n$ 个塔盘从塔 A 移动到塔 D 上所需的最小步数

3

5

 结合 $3$ 塔hanoi解决