首页 > 代码库 > 洛谷——P1096 Hanoi双塔问题
洛谷——P1096 Hanoi双塔问题
https://www.luogu.org/problem/show?pid=1096
题目描述
给定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。
输入输出样例
输入样例#1：
【输入样例1】1【输入样例2】2
输出样例#1：
【输出样例1】2【输出样例2】6
说明
【限制】
对于50%的数据，1<=n<=25
对于100%的数据，1<=n<=200
【提示】
设法建立An与An-1的递推关系式。
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 int n,num[233],len; 7 8 void cheng() 9 {10 for(int i=1,x=0;i<=len;i++)11 {12 num[i]=(num[i]<<1)+x;13 if(num[i]>9)14 {15 x=num[i]/10;16 num[i]%=10;17 len=max(len,i+1);18 }19 else x=0;20 }21 }22 23 int main()24 {25 scanf("%d",&n);26 len=1; num[1]=1;27 for(int i=1;i<=n;i++) cheng();28 num[1]-=1; 29 for(int i=1;i<=len;i++)30 if(num[i]<0) num[i]++,num[i+1]--;31 cheng();32 for(int i=len;i;i--) printf("%d",num[i]);33 return 0;34 }
洛谷——P1096 Hanoi双塔问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。