简答题
偏难
#23657
Hanoi双塔问题 【问题描述】 给定A、B、C三根足够长的细柱,在A柱上放有2n个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆…
Hanoi双塔问题
【问题描述】
给定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】

【输入输出样例2】

【限制】
对于50%的数据,1<=n<=25
对于100%的数据,1<=n<=200
【提示】
设法建立An与An-1的递推关系式。
答案与解析
正确答案:<p>#include<bits/stdc++.h></p><p>using namespace std;</p><p> </p><p>int a[1000],len_a;</p><p>int main()</p><p>{</p><p> int n,len;</p><p> freopen("hanoi.in","r",stdin);</p><p> freopen("hanoi.out","w",stdout);</p><p><span style="white-space:pre"> </span>cin>>n;</p><p> a[1]=2; //第一个2次 </p><p> len_a=1; //数字长度为1 </p><p> for(int i=1;i<=n;i++) // 做n次*2的高精乘法 </p><p> {</p><p> </p><p> for(int j=len_a;j>=1;j--) // 从高位做起 </p><p> {</p><p> a[j]=a[j]*2; //乘2 </p><p> if(a[j]>=10) //进位 </p><p> {</p><p> a[j+1]++;</p><p> a[j]-=10;</p><p> }</p><p> }</p><p> while(a[len_a+1]>0) len_a++; //进最高位 </p><p> }</p><p> a[1]=a[1]-2; // 不能忘记-2 </p><p> for(int i=len_a;i>=1;i--) //输出 </p><p> cout<<a[i];</p><p> fclose(stdin);</p><p> fclose(stdout);</p><p> return 0;</p><p>}</p>
这道题暂未补解析。