编程题：h0890.Strange Towers of Hanoi 汉诺塔问题
查理·达克布朗正坐在另一堂枯燥的计算机科学课上:现在老师只是解释标准的汉诺塔问题，这让查理无聊得要死!
老师指着黑板(图4)说:“那么问题来了:
•有三座塔:A、B和C。
•有n个磁盘。解谜时，数字n是常数。
•所有磁盘大小不同。
•圆盘最初堆叠在塔A上，从上到下逐渐增大。
•谜题的目标是将所有磁盘从A塔转移到C塔。
•每次一个磁盘可以从塔顶移动到空塔顶或塔顶有更大磁盘的塔顶。
所以你的任务是编写一个程序，计算将所有磁盘从a塔移动到c塔所需的最小磁盘移动次数。”
查理:“这太无聊了，大家都知道用简单的递归就能解决。我拒绝编写这么简单的代码!”
老师叹了口气:“好吧，查理，让我们想一件事让你做:对你来说，有第四个塔d。计算最小的磁盘移动次数来移动所有的磁盘从A塔到D塔使用所有的四个塔。”
查理看起来很生气:“呃……嗯，我不知道一个适合四座塔的最佳算法……”
所以真正的问题是，解决问题不属于查理擅长的事情。事实上，查理唯一擅长的就是“坐在一个能
“做好这份工作”。现在你猜怎么着--没错！是你坐在查理旁边，他已经在盯着你看了。
幸运的是，您知道以下算法适用于n<=12：首先，A塔上的k>=1磁盘是固定的，其余的n-k磁盘从A塔移动到B塔。
使用该算法对四座塔，然后从塔A剩余的k盘被移动到塔D，使用该算法的三个塔。最后，B塔的n-k圆盘是
再次移动到D塔，使用算法对四个塔(因此没有移动任何k磁盘已经在塔D)。为所有k2∈{1，.，n}，并找到k与
最少的移动次数。
因此，对于n=3和k=2，首先使用四座塔的算法(一次移动)将1(3-2)圆盘从塔A移动到B塔。然后你会移动剩下的两个磁盘
从塔A到塔D采用三塔算法(三步)。最后一步是将磁盘从B塔移动到D塔，再次使用以下算法
四座塔(又一次行动)。因此，n=3和k=2的解是5次移动。要确保这确实是n=3的最佳解决方案，您需要检查其他可能的值1和3对于k。(但是，顺便说一下，5是最优的...)
提示：3个塔n个磁盘最小移动次数为H(n) = 2^n - 1。
### 输入格式:
输入一个n(1<=n<=12)。
### 输出格式:
对于每个n(1<=n<=12)，打印一行，其中包含解决四个塔和n个磁盘问题的最小移动次数。
### 输入样例:
在这里输入一个数。例如：
in
3
### 输出样例:
out
5
答案：若无答案欢迎评论
老师指着黑板(图4)说:“那么问题来了:
•有三座塔:A、B和C。
•有n个磁盘。解谜时，数字n是常数。
•所有磁盘大小不同。
•圆盘最初堆叠在塔A上，从上到下逐渐增大。
•谜题的目标是将所有磁盘从A塔转移到C塔。
•每次一个磁盘可以从塔顶移动到空塔顶或塔顶有更大磁盘的塔顶。
所以你的任务是编写一个程序，计算将所有磁盘从a塔移动到c塔所需的最小磁盘移动次数。”
查理:“这太无聊了，大家都知道用简单的递归就能解决。我拒绝编写这么简单的代码!”
老师叹了口气:“好吧，查理，让我们想一件事让你做:对你来说，有第四个塔d。计算最小的磁盘移动次数来移动所有的磁盘从A塔到D塔使用所有的四个塔。”
查理看起来很生气:“呃……嗯，我不知道一个适合四座塔的最佳算法……”
所以真正的问题是，解决问题不属于查理擅长的事情。事实上，查理唯一擅长的就是“坐在一个能
“做好这份工作”。现在你猜怎么着--没错！是你坐在查理旁边，他已经在盯着你看了。
幸运的是，您知道以下算法适用于n<=12：首先，A塔上的k>=1磁盘是固定的，其余的n-k磁盘从A塔移动到B塔。
使用该算法对四座塔，然后从塔A剩余的k盘被移动到塔D，使用该算法的三个塔。最后，B塔的n-k圆盘是
再次移动到D塔，使用算法对四个塔(因此没有移动任何k磁盘已经在塔D)。为所有k2∈{1，.，n}，并找到k与
最少的移动次数。
因此，对于n=3和k=2，首先使用四座塔的算法(一次移动)将1(3-2)圆盘从塔A移动到B塔。然后你会移动剩下的两个磁盘
从塔A到塔D采用三塔算法(三步)。最后一步是将磁盘从B塔移动到D塔，再次使用以下算法
四座塔(又一次行动)。因此，n=3和k=2的解是5次移动。要确保这确实是n=3的最佳解决方案，您需要检查其他可能的值1和3对于k。(但是，顺便说一下，5是最优的...)
提示：3个塔n个磁盘最小移动次数为H(n) = 2^n - 1。
### 输入格式:
输入一个n(1<=n<=12)。
### 输出格式:
对于每个n(1<=n<=12)，打印一行，其中包含解决四个塔和n个磁盘问题的最小移动次数。
### 输入样例:
在这里输入一个数。例如：
in
3
### 输出样例:
out
5
答案：若无答案欢迎评论
