Hdu-2064 汉诺塔III

亦凉 2022-03-10 06:36 119阅读 0赞

**1. 问题描述**  
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。  
现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。  
Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？

**时间限制： 1000/1000 MS (Java/Others)  
空间限制： 32768/32768 K (Java/Others)**

样例输入：  
1  
3  
12  
样例输出：  
2  
26  
531440

**2. 问题分析**  
先不考虑最少的移动，先正常去考虑这个问题。如果把n个盘子从第1个柱子上移动到第3个柱子，那么移动第n个盘子需要如下步骤：

1.  先把n-1个盘子移动到2个柱子上，再移动到第三个柱子上。
2.  把 第n个盘子 移动到第2个柱子上。
3.  把n-1个盘子移动到第2根柱子上，再移动到第1根柱子上。  
    \---------第n个盘子移动了两次，前n-1个盘子移动了4次，  
    同理：移动第n-1个盘子时，需要单独移动两次，前n-2个盘子又移动了4次，  
    那么 第n个盘子一共移动了2次，第n-1个盘子一共移动了（2+4）次，第n-2个盘子移动移动了（2+4 \* 4）次 … 第1个盘子移动了(2+4^(n-1))次。  
    那么总移动次数等于2\*n+\[(4^n-4)\]/3,这个通过等比数列的求和公式很容易得到。

现在我们考虑是在什么时候产生最少移动次数的。  
其实我们不难看到，当我们有n个盘子的时候，刚才我们把n-1个盘子看成了一个整体进行分析的，其实这时候有两种选择供我们选择：  
现在我先强调一下我们移动的目标是什么，我们的目标是让前n-1个盘子全部移动到第3根柱子上，这样做的原因就是给第n根柱子腾空。  
1.第一种就是和刚才一样，把n-1个盘子看成一个整体那么总移动次数就是**2\*n+\[(4^n-4)\]/3**  
2.第二种就是  
1）先把前n-2个盘子从第1根柱子上移动到第2根柱子上，再移动到第3根柱子上  
2）把第n-1个盘子移动到第2根柱子上  
3）把前n-2个盘子从第3根柱子上移动到第2根柱子上，再移动到第1根柱子上  
4）把第n-1个盘子移动到第3根柱子上  
5）再把前n-2个盘子从第1根柱子上移动到第2根柱子上，再移动到第3根柱子上  
这样我们分成了5步把前n-1个盘子移动到了第3根柱子上，可能大家觉得这样做的移动次数比第一种多多了，可是直觉有时候会骗人的吗，事实证明当n超过某个数值时，第二种的移动次数会比第一种更优，

好了，最优值也已经分析出来怎么产生的了，剩下的工作就交给动态规划求最优值就可以了，另外一些小细节（比如int类型会爆掉），还需大家亲自调代码，毕竟计算机是个实践科学。

另外如果单单对于这个题目来说的话，我们不需要知道每个盘子的移动次数，我们可以根据递推表达式很容易得到所有盘子的移动次数，经过刚才的分析大家也不难得到 **F\[n\] = 3 \* F\[n-1\] + 2**。

**3. 详细代码**

#include <iostream>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    typedef long long ll;
    
    ll num[40];
    
    ll moveone(int n)
    {
        
    	ll res = 2 * n + ((ll)pow(4, n) - 4) / 3;
    	return res;
    }
    
    ll calc(int n)
    {
        
    	num[1] = 2;
    	num[2] = 8;
    	for (int i = 3; i <= n; i++)
    	{
        
    		ll tmp = num[i - 2] * 6 + num[i - 1] + 6;
    		num[i] = min(moveone(i), tmp);
    	}
    	return num[n];
    }
    
    int main()
    {
        
    	int n;
    	while (cin >> n)
    	{
        
    		cout << calc(n) << endl;
    	}
    }