“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有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;
}

评论