洛谷 P1096 Hanoi双塔问题
2024-08-25 06:23:09
题目描述
给定A、B、C三根足够长的细柱,在A柱上放有2n个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为n=3的情形)。
现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。要求:
(1)每次只能移动一个圆盘;
(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序;
任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。
输入输出格式
输入格式:
输入文件hanoi.in为一个正整数n,表示在A柱上放有2n个圆盘。
输出格式:
输出文件hanoi.out仅一行,包含一个正整数, 为完成上述任务所需的最少移动次数An。
输入输出样例
说明
【限制】
对于50%的数据,1<=n<=25
对于100%的数据,1<=n<=200
【提示】
设法建立An与An-1的递推关系式。
思路:
先找出An的通项公式,而两个相同的圆盘移动方法和一个圆盘的移动方法差不多,只要最后再乘二就好了,先考虑每种大小一个圆盘
而显然An=2*An-1+1,就相当于先把上面n-1个圆盘先挪走,再挪最大的,再把n-1个挪到它上面
又因为A1=1,因此有An=2^n-1,最后再乘二,An=2^(n+1)-2
写的话用高精度,算出2^(n+1),注意到2的幂的个位数字是2,4,8,6,所有再减二的时候不用考虑退位
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[];
int n,len,newl;
int main(){
scanf("%d",&n);
a[]=;len=;
for(int j=;j<=n;j++){
if(a[len]>=) newl=len+;
else newl=len;
for(int i=len;i>=;i--){
a[i]=*a[i];
if(a[i]>=){
a[i+]=a[i+]+;
a[i]=a[i]-;
}
}
len=newl;
}
a[]=a[]-;
for(int i=len;i>=;i--) printf("%d",a[i]);
return ;
}
最新文章
- Matlab 高脚杯模型切片
- WebGL与three.js
- ThinkPHP 下如何隐藏index.php
- 关于分布式事务的一个误解:使用了TransactionScope就一定会开启分布式事务吗?
- Jmeter—7 测试中使用到的定时器和逻辑控制器
- 503 Service Temporarily Unavailable
- 安装 Dubbo 管理控制台
- weka 文本分类(1)
- ToolBar+DrawerLayout + NavigationView
- cocos2d-x make: *** [clean-box2d_static-armeabi] Error 1
- 24-语言入门-24-cigarettes
- Activiti从当前任务任意回退至已审批任务
- javascript 中的nextSibling和previousSibling使用注意事项
- app图标icon大全
- 解析xml文件的四种方式
- RabbitMQ分布式集群架构和高可用性(HA)
- Python中的那些“坑”
- js获取地址栏传参
- Saltstack_使用指南03_配置管理
- Tomcat优化之容易集合经验