双塔问题
成绩 | 100 | 开启时间 | 2020年02月19日 星期三 14:35 |
折扣 | 0.8 | 折扣时间 | 2020年02月19日 星期三 14:35 |
允许迟交 | 是 | 关闭时间 | 2020年02月19日 星期三 14:35 |
输入文件 | hanoi2.in | 输出文件 | hanoi2.out |
【题目描述】双塔问题(hanoi2)
如图4.13所示,给定A,B,C三根足够长的细柱,在A柱上放有2n个中间有空的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的,图为n=3的情形。现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存,每次只能移动一个圆盘,每个柱子的圆盘保持上小下大的顺序,要求输出最少移动次数。
图4.13
【输入格式】
输入为一个正整数,表示A柱上有2n个圆盘。
【输出格式】
输出仅一行,包含一个正整数,为最少移动次数。
【输入样例1】
1
【输出样例1】
2
【输入样例2】
2
【输出样例2】
6
【数据范围】
对于50%的数据,1≤n≤25;
对于100%数据,1≤n≤200。