[2007年NOIP普及组] Hanoi双塔问题
2024-10-21 17:32:05
给定A、B、C三根足够长的细柱,在A柱上放有2n个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为n=3的情形)。现要将 这些国盘移到C柱上,在移动过程中可放在B柱上暂存。要求:
(1)每次只能移动一个圆盘;
(2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序;
任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。
(1)每次只能移动一个圆盘;
(2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序;
任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。
输入
输入为一个正整数n,表示在A柱上放有2n个圆盘。
输出
输出仅一行,包含一个正整数,为完成上述任务所需的最少移动次数An。
样例输入
2
样例输出
6
提示
【限制】
对于50%的数据, 1<=n<=25
对于100% 数据, 1<=n<=200
【提示】 设法建立An与An-1的递推关系式。
对于50%的数据, 1<=n<=25
对于100% 数据, 1<=n<=200
【提示】 设法建立An与An-1的递推关系式。
列举数据的解
得出AN=(2^n)-2
因为n<=200
所以AN最大为(2^200)-2
约等于1.6e60
需要使用高精度运算
#include<iostream> using namespace std; int ANS[100],S,M; int main()
{
cin>>S;
ANS[0]=2; for(int i=1;i<=S;++i)
{
for(int j=0;j<=90;++j)
{
ANS[j]*=2;
}
for(int j=0;j<=90;++j)
{
if(ANS[j]>=10)
{
ANS[j+1]+=ANS[j]/10;
ANS[j]%=10;
}
}
} for(int i=90;i>=0;--i)
{
if(ANS[i]!=0)
{
M=i;
break;
}
}
ANS[0]-=2;
for(int i=M;i>=0;--i)
{
cout<<ANS[i];
}
return 0;
}
最新文章
- NSURLSession从网络上下载资源,此程序下载的是视频
- C# Array
- Pig简单入门
- hi3531 SDK 编译 uboot, 改动PHY地址, 改动 uboot 參数 .
- 关于HTML5中audio标签在手机中的autoplay
- linx建立用戶&;組
- Java 多线程详解(四)------生产者和消费者
- 【转】为什么选择Spring Boot作为微服务的入门级微框架
- Java_注解_01_注解(Annotation)详解
- linux下的Shell编程(5)循环
- odoo Model字段的参数
- 初学Python——文件操作第三篇
- 【python】mongo删除数据
- Intel Fortran 调用Delphi编制的DLL
- js脚本 将本地图片路径转换为html
- 结对编程——paperOne基于java的四则运算 功能改进
- redis之hello
- 大厂面试官:Java工程师的“十项全能”
- golang 如何判断变量的类型
- Python之元类详解