2077 汉诺塔IV

关键字: 代码分享 杭电100题

问题描述

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需要3n - 1(推导见2064),所以把n-1个盘移动1步,需要f(n) = f(n-1) + 3n-1;而f(1) = 1,于是 f(n) = 3n-1 + 3n-2 + ... + 3 + 1 = (3n - 1) / 2,所以按汉诺塔IV的规则来,搬n个盘需要m(n) = 2 * f(n-1) + 2 = 3n-1 + 1。

参考源码

redraiment使用Emacs Lisp批量迁移《HDU 2070-2079》