汉诺塔IV

> > Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

(Java/Others) Total Submission(s): 10905 Accepted Submission(s):

7541

Problem Description

还记得汉诺塔III吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。

Input 输入数据的第一行是一个数据T，表示有T组数据。 每组数据有一个正整数n(1 <= n <= 20)，表示有n个盘子。

Output 对于每组输入数据，最少需要的摆放次数。

Sample Input 2 1 10

Sample Output 2 19684

解题思路：

因为每次只能够移一格，最大的可以放在最上面，所以：

先把前n-1个从a移动到b，第n个移动两次到c

再移动n-1个到c。

设从a→c移动次数为f(n)

分类：

①h(n)=f(n-1)+2

//第n个移动的情况，前n-1个只需移动一大次，加上最大的移动两次。(最好画图)

②f(n)=3f(n-1)+2

//剩下n-1个移动的情况：大的不能在小的上方，所以n-2个需要从a到c(a到c移动两次)，c到a，a再到c。所以是三次大移动。

.

#include
    
     using namespace std;int main(){
    	long long int a[25];	a[0] = 2;	for (int i=1;i<20;i++)	{
    		a[i] = a[i - 1] * 3 + 2;	}	int n, m;///m为组数，n为需要移动的个数	cin >> m;	for (int i = 0; i < m; i++)	{
    		long long x = 0;		cin >> n;		switch (n)		{
    		case 1:x = 2; break;		case 2:x = 4; break;		default:x = a[n - 2] + 2; break;		}		cout << x << endl;	}    return 0;}