还记得汉诺塔 III 吗? 他的规则是这样的: 不允许直接从最左 (右) 边移到最右 (左) 边(每次移动一定是移到中间杆或从中间移出), 也不允许大盘放到小盘的上面. xhd 在想如果我们允许最大的盘子放到最上面会怎么样呢?(只允许最大的放在最上面)当然最后需要的结果是盘子从小到大排在最右边.
Input
输入数据的第一行是一个数据 T, 表示有 T 组数据.
每组数据有一个正整数 n(1 <= n <= 20), 表示有 n 个盘子.
Output
对于每组输入数据, 最少需要的摆放次数.
- Sample Input
- 2 1 10
- Sample Output
- 2
- 19684
- // 几乎能独立写出来了
- #include<stdio.h>
- /* 从左到右分别记柱子为 a,b,c.
- #1 将前 n-1 个盘子从 a 移到 b.
- 将第 n 个盘子从 a 移到 b, 再从 b 移到 c.
- 将前 n-1 个盘子从 b 移到 c.
- 则 g(n)=2*f(n-1)+2.
- #2 将前 n-1 个盘子从 a 移到 b, 再从 b 移到 c.
- 将第 n 个盘子从 a 移到 b.
- 将前 n-1 个盘子从 c 移到 b.
- 则 f(n)=3*f(n-1)+1.
- */
- int f[21]={0};
- void table()
- {
- for(int i=1;i<21;i++)
- f[i]=3*f[i-1]+1;
- }
- int main()
- {
- int t,n;
- table();
- scanf("%d", &t);
- while(t--)
- {
- scanf("%d", &n);
- printf("%d\n", 2*f[n-1]+2);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2947244.html