Problem 26398 --【递推】Ⅱ.Hanoi塔问题(例题)

26398: 【递推】Ⅱ.Hanoi塔问题(例题)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 8  Solved: 1
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][84kb]

Description

    问题的提出:Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时,这n个圆盘由大到小依次套在a柱上,如图3-11所示。

    要求把a柱上n个圆盘按下述规则移到c柱上:


    (1)一次只能移一个圆盘;

    (2)圆盘只能在三个柱上存放;

    (3)在移动过程中,不允许大盘压小盘。

    问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次?



Input

    一个正整数n,1=<n<=100。

Output

    移动的总次数。

Sample Input

4

Sample Output

15

HINT

Source

[Submit][Status]