自动搬运

查看原文

来自洛谷，原作者为

	违规用户名3(kd,e$A **

搬运于2025-08-24 21:20:52，当前版本为作者最后更新于2019-10-15 13:18:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

哈喽，大家好，我又来了（虽然你可能不认识我），但我还是要把我的开场白说一说，好啦，言归正传。

今天，我来给大家讲一讲Hanoi 双塔问题这道题。

我们先来理解一下题意，题目是说，用最少的次数，把那三个圆柱给移到指定的C柱上，然后把次数输出（要最少的）

首先，容易得到a[n] = 2*b[n]（也即2个同样的圆盘一起移肯定最好）

然后，如图，当A柱上有n个盘时，先移n-1个到B，再移1个到C，再将B上的n-1个移到C

可以得到 b[n] = 2*b[n-1] + 1

下面我给大家分段来分析，首先

定义一个L，一个N;L表示每次去的方法次数，N表示有2N个圆盘。

然后在定义二个数组，分别表示A柱移到C柱的移动过程的储存，因为题目只确定了范围为200，所以我们也不需要定太大，两百足以搞定。

#include<cstdio>
using namespace std;
int l,n;
int a[201],b[201];

第二个部分，GJC函数，这个部分求的是移动过程是的一个操作，具体方法如下

void gjc()
{
    int t=0;//求每次移完后剩下哟多少可以移动的。
    for (int j=200;j>0;j--)
     {
         l=b[j]*2+t;//每次加上b数组的得数乘上二，这里很关键，因为N等于2N个圆盘，所以要把B[J]乘上二，然后再加上剩下的多少才可求出一共有多少个可移动的。
         b[j]=l%10;//每次B【J】要进行递除，不然结果不变
         t=l/10;//每次t要进行递除，不然结果不变
     }
}

可能大家会发现两个函数基本相同，只有一个不同，那就是循环里的第一句话，大家可能会问这个程序段和上个程序段有什么不同，为什么要这样做，这样做作的目的是什么，下面我来给大家解答。

void gjc()
{
    int t=0;
    for (int j=200;j>0;j--)
     {
         l=b[j]*2+t;
         b[j]=l%10;
         t=l/10;
     }
}

void gjj()
{
    int t=0;
    for (int j=200;j>0;j--)
     {
         l=a[j]+b[j]+t;
         a[j]=l%10;
         t=l/10;
     }
}

这个的原因是：因为你移动的过程还可能会发生一些其他问题比如说

你要把第二个柱的大的，把它移到第三个柱，你就需要把哪两个给移走，所以说，你要有一个新的函数，来存储你的移动的过程，第三个的作用就是这些。

这一段，也就是主程序，解释在程序中，望见谅。

int main()
{
    
    scanf("%d",&n);//输入圆盘的个数。
    b[200]=1;//把B数组的第二百位存为1，
    因为本身在一个位置，也要进行判断,否则
    答案会有误差
    for (int i=1;i<=n;
     {gjc();gjj();}//进入函数判断。
    int k=1;
    while (a[k]==0&&k<200)//判断运行次数，并进行累加。
     k++;
    for (int i=k;i<=200;i++)//从k次执行到200次
     printf("%d",a[i]);//输出数量。
    
}

下面进行程序展示，不再进行解释，望见谅。

#include<cstdio>
using namespace std;
int l,n;
int a[201],b[201];
void gjc()
{
    int t=0;
    for (int j=200;j>0;j--)
     {
         l=b[j]*2+t;
         b[j]=l%10;
         t=l/10;
     }
}
void gjj()
{
    int t=0;
    for (int j=200;j>0;j--)
     {
         l=a[j]+b[j]+t;
         a[j]=l%10;
         t=l/10;
     }
}
int main()
{
    
    scanf("%d",&n);
    b[200]=1;
    for (int i=1;i<=n;i++)
     {gjc();gjj();}
    int k=1;
    while (a[k]==0&&k<200)
     k++;
    for (int i=k;i<=200;i++)
     printf("%d",a[i]);
     return 0;
}

写的这么长，就给过了吧，如果过了，麻烦拿拿你们皇帝搬的纤纤玉手帮我点点赞（爱你么么哒）。