问题描述

Problem Description

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

Input

输入数据的第一行是一个数据T，表示有T组数据。

每组数据有一个正整数n(1 <= n <= 20)，表示有n个盘子。

Output

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

Sample Input

2
1
10

Sample Output

2
19684

问题分析

Problem Analyse

递推题

Algorithm Analyse

既然最大的那个盘可以放在最上面，那就不用像汉诺塔III一样吧前n-1个盘全从1搬到3，只要从1搬到2，然后把第n个盘从1搬到2再搬到3，然后把这n-1个从2搬到3。于是问题转换成n个盘搬一步需要几次，但前n-1个盘和汉诺塔III的的规则是一样的。所以，需要先把前n-2从1搬到3，然后把第n-1个盘从1搬到2，再把前n-2个盘从3搬到2。

因为把n个盘按汉诺塔从1搬到3需要3ⁿ - 1(推导见2064)，所以把n-1个盘移动1步，需要f(n) = f(n-1) + 3^n-1；而f(1) = 1，于是 f(n) = 3^n-1 + 3^n-2 + ... + 3 + 1 = (3ⁿ - 1) / 2，所以按汉诺塔IV的规则来，搬n个盘需要m(n) = 2 * f(n-1) + 2 = 3^n-1 + 1。

参考源码