2018年1月月赛 打卡的汉诺塔 题解
题目背景
比赛总是需要打卡题~~
题目描述
mh和cl最近玩起了汉诺塔。
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。
游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。
操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。现有n个盘子，有A、B、C三个柱子。
mh认为汉诺塔有最优解，而cl认为没有，这可怎么办呢？请你帮忙算算吧。
输入输出格式
输入格式
一行，包含一个正整数n，表示A柱子上有的盘子数量。
输出格式
一行，包含一个整数，表示最少需要的步数。
输入输出样例
输入样例#1：
1 | 2 |
输出样例#1：
1 | 3 |
说明
对于60%的数据，1<=n<=32。
对于100%的数据，1<=n<=64。
样例说明：
按A->B，A->C，B->C的方式即可三步完成。
通过手推n=1,2,3,4的情况，可以发现ans=pow(2,n)-1，故答案最大为2^64-1。
观察数据范围，发现n<=64。
因为int范围-2^31~2^31-1
long long范围-2^63~2^63-1
unsigned long long范围0~2^64-1
所以选用unsigned long long。
但又因为pow函数返回值为double类型，浮点数类型在数字很大时会发生浮点误差，因此用pow只能80分。故采用循环。
代码：1
2
3
4
5
6
7
8
9
10
11
12
using namespace std;
int main()
{
unsigned long long ans=1,n;
cin>>n;
for(int i=1;i<=n;i++) ans*=2;
ans--;
cout<<ans;
return 0;
}
在上述代码中，我们发现，极端情况时ans=2^64，超过unsigned long long的0~2^64-1的范围，发生向上溢出（上溢），此时变为(2^64)-1-(2^64-1)=0。
之后又发生ans–，ans本该变为-1，但因为超过unsigned long long的0~2^64-1的范围，发生向下溢出（下溢），此时变为(-1)+1+(2^64-1)=2^64-1，即是答案。