4122: 【07NOIP普及组】Hanoi双塔问题
Memory Limit:64 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
给定$A,B,C$三根足够长的细柱,在$A$柱上放有$2n$个中间有空的圆盘,共有$n$个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为$n=3$的情形)。现要将这些圆盘移到$C$柱上,在移动过程中可放在$B$柱上暂存。要求: n(1)每次只能移动一个圆盘; n(2)$A、B、C$三根细柱上的圆盘都要保持上小下大的顺序; n任务:设$A_n$为$2n$个圆盘完成上述任务所需的最少移动次数,对于输入的$n$,输出$A_n$。 n
Input
一个正整数$n$,表示在$A$柱上放有$2n$个圆盘。
Output
仅一行,包含一个正整数,为完成上述任务所需的最少移动次数$A_n$。
Sample Input Copy
1
Sample Output Copy
2