2012年蓝桥杯省赛-汉诺塔

题目

题目链接

题解

题目本身很简单，但是我想提醒几点：

1. 会推导出结论 2 n − 1 2^n-1 2n−1；
2. 特殊的输出方式.

对于汉诺塔问题，存在递推公式： f ( n ) = 2 f ( n − 1 ) + 1 f(n)=2f(n-1)+1 f(n)=2f(n−1)+1

f ( n ) + 1 = 2 f ( n − 1 ) + 2   f ( n ) + 1 f ( n − 1 ) + 1 = 2   f(n)+1=2f(n-1)+2 \\ \space \\ \frac{f(n)+1}{f(n-1)+1} = 2 \\ \space \\ f(n)+1=2f(n−1)+2 f(n−1)+1f(n)+1​=2 

令 f ( n ) + 1 = F ( n ) f(n)+1=F(n) f(n)+1=F(n)，则

F ( n ) F ( n − 1 ) = 2 \frac{F(n)}{F(n-1)}=2 F(n−1)F(n)​=2

又因为 F ( 1 ) = f ( 1 ) + 1 = 2 F(1)=f(1)+1=2 F(1)=f(1)+1=2，故

F ( n ) = F ( 1 ) ∗ 2 n − 1 = 2 n   f ( n ) + 1 = 2 n   f ( n ) = 2 n − 1 F(n)=F(1)*2^{n-1}=2^n \\ \space \\ f(n)+1 = 2^n \\ \space \\ f(n) = 2^n-1 F(n)=F(1)∗2n−1=2n f(n)+1=2n f(n)=2n−1

之所以推导这个公式，是因为可能存在其他汉诺塔问题的变形，学会“渔”方可“渔”。

对于本问题的输出， 2 64 − 1 2^{64}-1 264−1，直接用pow函数算得到的结果是1.84467e+019，科学计数法会出错；

当然可以将pow(2,64)-1赋值给一个unsigned long long变量，再进行输出；

更简单点，直接输出ULONG_LONG_MAX，其表示的含义为unsigned long long所能表示的最大数，即 2 64 − 1 2^{64}-1 264−1，这需要一定的计算机基础知识。

代码

#include
using namespace std;

int main()
{
	cout