“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有4根柱子，而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？*****************************************************#include <iostream.h>#include <stdlib.h>long count;long m;const long ccMax=1000;long tt[ccMax];long tc[ccMax];long fc[ccMax];long Hanoi(int n, int a, int b, int c){    long t1,t2;    t1=t2=0;    if ( tc[n] != 0) return tc[n];    if (n==1) return 1;    else if (n>0)    {        t1=Hanoi(n-1,a,c,b);        t2=Hanoi(n-1,b,a,c);    }    return tc[n]=t1+t2+1;}long Hanoi1(int n, int a, int b, int c, int d){    long t[4];    t[0]=t[1]=t[2]=t[3]=0;    if (fc[n] != 0 ) return fc[n];    if (n==1) return 1;    else if (n==2)    {        t[0]=Hanoi(n-1,a,d,c);        t[1]=Hanoi(n-1,c,a,d);        return t[0]+t[1]+1;    }    else    {        long temp;        long min=-1;        for (temp=1; temp<(n-1); temp++)        {            t[0]=Hanoi1(temp,a,d,c,b);            t[1]=Hanoi(n-1-temp,a,d,c);            t[2]=Hanoi(n-1-temp,c,a,d);            t[3]=Hanoi1(temp,b,a,c,d);            long sum=t[0]+t[1]+t[2]+t[3]+1;            if (sum <= fc[n-1] || t[1]<=tc[n-1-temp-1]) continue;            if ( sum< min || min<=0 ) { min=sum; tt[n]=temp; }        }        if (min<=0)         {             cout<<"第"<<n<<"个盘时数据溢出了! 输入任意键，然后回车键退出."<<endl;            int mm;            cin>>m;            exit(1);        }        return fc[n]=min;    }}long Hanoi11(int m)//计算次数{    long cc;    for (int i=1; i<=m; i++)        cc=Hanoi1(i,1,2,3,4);    return cc;}void Hanoi_putout(int n, int a, int b, int c){    if (n==1) cout<<a<<"->"<<c<<endl;    else if (n>0)    {        Hanoi_putout(n-1,a,c,b);        cout<<a<<"->"<<c<<endl;        Hanoi_putout(n-1,b,a,c);    }}void Hanoi1_putout(int n, int a, int b, int c, int d){    if (n==1)     {        cout<<a<<"->"<<d<<endl;    }    else if (n==2)    {        Hanoi_putout(n-1,a,d,c);        cout<<a<<"->"<<d<<endl;        Hanoi_putout(n-1,c,a,d);    }    else    {        int temp=tt[n];        Hanoi1_putout(temp,a,d,c,b);        Hanoi_putout(n-1-temp,a,d,c);        cout<<a<<"->"<<d<<endl;        Hanoi_putout(n-1-temp,c,a,d);        Hanoi1_putout(temp,b,a,c,d);    }}int main(){    cout<<"四塔问题: 它是汉诺塔问题的扩展,该问题其实还是汉诺塔,";    cout<<"不同是它把三个塔变为四个塔,规则一样,但是是要从第一个";    cout<<"移到第四个."<<endl;    cout<<"请输入盘子数:";    cin>>m;    count=Hanoi11(m);    cout<<"四塔时的最少移动步骤为:"<<endl;    cout<<count<<"次"<<endl;    cout<<"是否要输出其具体步骤?(Y/N ?)"<<endl;    char a;    cin>>a;    if (a=='y' || a=='Y')        Hanoi1_putout(m,1,2,3,4);    cout<<"输入任意键，然后回车键退出"<<endl;    cin>>m;}

评论