题目链接
题解题目本身很简单,但是我想提醒几点:
- 会推导出结论 2 n − 1 2^n-1 2n−1;
- 特殊的输出方式.
对于汉诺塔问题,存在递推公式: 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
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?