SSL-ZYC Hanoi双塔问题

2024-01-30 11:18

文章标签 问题 ssl 双塔 hanoi zyc

本文主要是介绍SSL-ZYC Hanoi双塔问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：
给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求:
这里写图片描述
(1)每次只能移动一个圆盘；
(2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。

思路：
这道题的思路有两种：
（1）尝试建立a[n]和a[n-1]的关系。
（2）直接用公式推出a[n]的值。

那么两种思路自然有两种解法：
（1）我们可以发现，这一组数列为2,6,14,30,62······仔细一看，就找到了规律：a[n]=a[n-1]*2+2。那我们就可以从a[1]开始递推，推到a[n]为止。
（2）如果直接求a[n]的值的话，我们就得先找规律。这道题的规律是a[n]=（2^n-1）*2。利用这条公式，我们就可以求出a[n]的值。

这道题由于答案很大，所以要用高精度。
这道题我用的是第2种方法，下面给大家贴上代码：

代码：

#include <cstdio>
using namespace std;
const int maxn=100;
int a[maxn+1],t,n;int main()
{freopen("hanoi.in","r",stdin);freopen("hanoi.out","w",stdout);scanf("%d",&n);a[maxn]=1;  //初始化，2的0次方是1 for (int i=1;i<=n;i++)  //计算2的n次方 {t=0;for (int j=maxn;j>=1;j--)  //高精乘 {a[j]=a[j]*2+t;t=a[j]/10;a[j]%=10;}} a[maxn]-=1;  //由于2的任何次方（0次方和负次方除外）的尾数为2,4,6,8，所以这里减1可以不用考虑退位问题。 t=0;for (int i=maxn;i>=1;i--)  //高精乘 {a[i]*=2;a[i]+=t;t=a[i]/10;a[i]%=10; }int i=1;while (a[i]==0) i++;  //去掉前导0 for (int j=i;j<=maxn;j++) printf("%d",a[j]);  //输出最终结果 return 0;
}