PID380 / 郁闷的电子词典
题目描述

在衡中,众所周知,所有的电子设备是一律禁物。但是总是有小强以身犯险,atttx123很荣幸的成为其中的一员。在每天13个小时的埋头苦学之后,他总要抽出一点点时间在被窝里搞自己的电子词典,小强atttx123很强悍地依然去玩那HANOI(汉诺塔),话说他玩了很长很长时间了呢……

对于汉诺塔问题,大家一定很熟悉。给定A,B,C三根足够长的细柱,在A柱上放有n个中间有圆孔的圆盘,且从下向上半径依次减小,共有n个不同的尺寸(下图为n=4的情形)。现要将 这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。

因为他的电子词典的特殊性,这个游戏要有新的要求:

(1) 每次光标只能移动一下,且只能移动到相临的柱子上;

(2) 光标从A柱上向左移动则到达C柱,从C柱上向右移动则到达A柱;

(3) 当某个盘子被选择之后计数器开始计数,此后每移动光标一次步数加一(盘子不跟随光标移动),当光标到达目标位置释放后盘子直接到达目标位置,计数器停止计数,故不用考虑光标移动过程中每个柱子上盘子的大小次序问题的;

(4)A、B、C三根细柱上的圆盘都要保持上小下大的顺序(释放以后);

(5)最终计数器的显示数就为移动的步数;

atttx123很喜欢玩这个游戏,以至于要立志每天玩完1盘,他的电子词典向右移动按钮失灵了(谁叫他光玩呢—↓—),于是他想正常的Hanoi塔游戏对于n个盘则最少步数为2^n-1,那么只用向左移动键玩,则对于n个盘最小步数是多少?

他要估计自己玩完一盘到底要多少时间~~~~~。

【数据范围】

0<=30%<=30

0<=100%<=1000

样例解释

1号盘: a===》c (一步)

2号盘: a===》b (两步)

1号盘: c===》b (一步)

3号盘: a===》c (一步)

1号盘: b===》a (一步)

2号盘: b===》c (两步)

1号盘: a===》c (一步)

共:1+2+1+1+1+2+1=9步

输入格式

输入为一个整数n (0≤n≤1000),表示在A柱上放有n个圆盘。

输出格式

输出仅一行,包含一个整数,为完成上述任务所需的最少移动次数An(保证 An≤10 ^1000)。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论