Hanoi双塔问题 （C++代码）

解题思路:





注意事项:





参考代码:

什么？竟然没有py3的题解？？我来一发

其实很简单，这是在py3中2的x方用2**x表示 代码：

a=int(input())print(2**(a+1)-2)

评论

还没有评论

评论

其实这题非常水，找到规律，用高精度就行了。

我们可以先用深搜打表，设法找到ai与ai+1的关系。

深搜代码略……

n 1 2 3 4 5 ……

a 2 6 14 30 62 ……

其实，a[i]=a[i-1]+2^i;(这是列举众多规律众多一个，dalao勿喷)

a[0]=0;

下面是代码：

#include<cstdio>using namespace std;int l,n;int a[201],b[201];//a是最终结果，b是2的i次方void gjc()//高精乘，算2的i次方{    int t=0;    for (int j=200;j>0;j--)
    {
        l=b[j]*2+t;
        b[j]=l%10;
        t=l/10;
    }
}void gjj()//高精加，把数组B的值加到A里面{    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(){    //freopen("hanoi.in","r",stdin);
   //freopen("hanoi.out","w",stdout);
   scanf("%d",&n);//读入
   b[200]=1;//初值，不能漏掉
   for (int i=1;i<=n;i++)
    {gjc();gjj();}//运算
   int k=1;    while (a[k]==0&&k<200)//去除前导0
    k++;    for (int i=k;i<=200;i++)     printf("%d",a[i]);//输出
   //fclose(stdin);
   //fclose(stdout);}

评论

还没有评论

评论

1760的汉诺塔的数据范围是15000，这个才200.大家应该都能推出单汉诺塔的递推式a[i]=2*a[i-1]+1.然后列出来找规律会发现a[i]=2^i-1.这个双塔和单塔有区别么？圆盘的大小相同，你可以把两个盘视为一个盘移动，就变成了单塔问题。接下来不是乘以2的事情了么？高精度的实现我用了结构体，便于理解。直接用高精加法应该都可以做吧。代码基本就是粘贴了1760的，注释也可以看1760的题解。

#pragma GCC optimize(3)#include<bits/stdc++.h>using namespace std;int n;struct boss{int num[20000],len;
boss(){memset(num,0,sizeof num),len=0;}void print()
 {//   for (;num[len]==0;len--);
 for (int i=len;i>=1;i--) putchar(num[i]+'0');  puts("");
 }
};

boss operator *(boss a,boss b)
{
boss c;int i;for (i=1;i<=a.len;i++) for (int j=1;j<=b.len;j++) c.num[i+j-1]+=a.num[i]*b.num[j];
for (i=1;i<=a.len+b.len-1;i++)
 {
 c.num[i+1]+=c.num[i]/10;
 c.num[i]%=10;
 }for (;c.num[i]==0;i--);
c.len=i;return c;
}int main(){scanf("%d",&n);
boss a,tmp;a.len=tmp.len=1;
a.num[1]=1;tmp.num[1]=2;for (a=a*tmp;n;n>>=1,tmp=tmp*tmp) if (n&1) a=a*tmp;//在开始快速幂之前先乘了一次a.num[1]-=2;//-1之后乘以2,故要-2.也不会出现退位。a.print();
}

评论

还没有评论

评论

双塔和单塔不同的是：双塔的步数是单塔的2倍（肯定的）。

所以只要一个过程就行了。

我们看完题目，不难得出：总数量=2*n；

步数=（n-1块圆盘的步数）*2

可以用阶乘做。

标程：

type ghint=array[0..1000] of longint;\数组别开大，不然会爆。

var  a:ghint;
      i,n:integer;procedure cheng1(var a:ghint;i:integer);\\数组的值要带回来，不然有什么意义。var jw,x:integer;begin
 jw:=0; \\进位变要置0，因为变量在过程里，在主程序里不赋值的话，会自己置0。  for x:=1 to a[0] do \\循环，从1到数组的长度，阶乘。   begin
   a[x]:=a[x]*i+jw;\\i在主程序里为2（因为是双塔），还要加上进位来的值。
   jw:=a[x] div 10;\\如果有进位的话，jw就有值。
  a[x]:=a[x] mod 10;\\没有进位的话也不影响。   end;
 while jw>0 do \\看看还有没有进位了。   begin
    a[0]:=a[0]+1;\\ 数组加一个位置
    a[a[0]]:=jw mod 10;\\在最后一个位置加上进位的最低位
    jw:=jw div 10;\\jw缩小十倍，这样就去掉了刚才被加过的个位。   end;end;begin
 read(n);
 a[0]:=1;a[1]:=0;\\a[0]初始为1，a[1]初始为0，做到了把数组置0
 for i:=1 to n do\\从1到n循环   begin
   a[1]:=a[1]+1; \\根据公式，所以先加1
   cheng1(a,2);\\掉用阶乘过程，每循环一次就掉用一次，这样就能按照公式做   end;  for i:=a[0] downto 1 do \\应为个位在最高位，所以倒着打   write(a[i]);\\输出end.

评论

还没有评论

评论

第一次写题解（灬✪ω✪灬）

先找出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<cstdlib>#include<algorithm>#include<cstring>#include<cmath>//装*的头文件using namespace std;int i,n,a[205],len,j,newl;int main(){    scanf("%d",&n);
   a[1]=2;len=1;//len表示位数，a[1]是个位，a[2]是十位，以此类推
   for(j=1;j<=n;j++)
   {        if(a[len]>=5)    newl=len+1;//首位大于5就要进位
       else    newl=len;        for(i=len;i>=1;i--)
       {
           a[i]=2*a[i];            if(a[i]>=10){
               a[i+1]=a[i+1]+1;
               a[i]=a[i]-10;
           }
       }
       len=newl;
   }
   a[1]=a[1]-2;    for(i=len;i>=1;i--)        printf("%d",a[i]);//倒叙输出
   return 0;
}