双塔问题
成绩 | 100 | 开启时间 | 2016年05月28日 星期六 11:35 |
折扣 | 0.8 | 折扣时间 | 2016年05月28日 星期六 11:35 |
允许迟交 | 是 | 关闭时间 | 2016年05月28日 星期六 11:35 |
输入文件 | hanoi2.in | 输出文件 | hanoi2.out |
【问题描述】双塔问题(hanoi2.cpp/c/pas)
楚继光:“防御系统还真有用,修罗王的魔法炮阵的火力果然减弱了,但好像还差一点点啊?”
墨老师:“哦,是吗,那试试双塔防御体系吧。”
如图所示,给定A,B,C三根足够长的细柱,在A柱上放有2n个中间有空的能量圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的,图为n=3的情形。现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。每次只能移动一个圆盘,每个柱子的圆盘保持上小下大的顺序。要求输出最少移动次数。
【输入格式】
输入文件hanoi2.in为一个正整数,表示A柱上有2n个圆盘。
【输出格式】
输出文件hanoi2.out仅一行,包含一个正整数,为最少移动次数。
【输入样例1】
1
【输出样例1】
2
【输入样例2】
2
【输出样例2】
6
【数据范围】
对于50%的数据,1≤n≤25;
对于100%数据,1≤n≤200。