0

最近我在接受 C++ 开发者职位的面试，我被要求编写一个程序来解决一个有 3 列和 1000000 个圆盘的河内塔谜题，该程序必须将移动输出写入磁盘（“1->3”， “1->2”，...等等），我告诉他们这将是一个非常大的解决方案文件，因为河内塔的最小移动量是 2 次方 n - 1 而对于 1000000 这将是非常不适合任何硬盘驱动器的大数字，他们说经典算法是错误的，并且有一种算法可以解决这个难题，即使是 1000000 个带有发烧动作的光盘。我想知道是否存在这样的算法或者他们只是在骗我？

谢谢，帖木儿。

4

2 回答 2

0

这是我为 nhahtdh 承诺的代码。

#include <iostream>
#include <conio.h>
#include <math.h>
#include <iomanip>

using namespace std;
char disc[2000000]={0};
int n;
bool validate(int num,int target){
    int t=num+1;
    while(t<n){
        if ((disc[num]==disc[t])||(disc[t]==target))return false;
        t++;
    };
    return true;
};  
int main()
{
    __int64 k=0;
    cout<<"Enter number of discs:";cin>>n;
    cout<<"This would be a "<<setprecision(1000)<<pow(2,n)-1<<" combinations !"<<endl;
    cout<<"To START press a key!"<<endl;
    _getch();
    int num=0,cur=0,t=0,nn=0;
    while(num<n){
        t=2;nn=num;
        while(nn<n){
            if(disc[nn]==t){nn++;continue;}
            if(validate(nn,t)){
                if(nn==num)num++;
                k++;cout<<disc[nn]+1<<"->"<<t+1<<":"<<k<<" move"<<endl;
                disc[nn]=t;
                nn++;
                continue;
            }
            if((disc[nn]==0)&&(t==2)){nn++;t=1;continue;}
            if((disc[nn]==0)&&(t==1)){nn++;t=2;continue;}
            if((disc[nn]==1)&&(t==2)){nn++;t=0;continue;}
            if((disc[nn]==1)&&(t==0)){nn++;t=2;continue;}
            if((disc[nn]==2)&&(t==1)){nn++;t=0;continue;}
            if((disc[nn]==2)&&(t==0)){nn++;t=1;continue;}
        };
    };
    return 0;
}

我希望你能理解，但如果不给我写一封电子邮件到 atlantic-sys@mail.ru，我可以更详细地解释。

于 2013-04-13T12:34:53.427 回答
0

输出确实太大（如您所说的输入大小的指数），但该算法以递归方式编写相当简单。也许这就是他们的意思。

如果你愿意，我可以提供算法。

编辑：只是为了完整性，我会提供算法（它在 Python 中，但在 C++ 中的实现几乎相同）：

n = 3
# using 4 elements just so we're 1-based with three towers
towers = [ [], range(n, 0, -1), [], [] ]

def move (orig, dest, n):
    if n == 1:
        elem = towers[orig].pop()
        print 'moving %d from %d to %d' % (elem, orig, dest)
        towers[dest].append(elem)
    else: 
        through = dest ^ orig
        move(orig, through, n-1)
        move(orig, dest, 1)
        move(through, dest, n-1)

move(1, 3, n)
于 2013-04-13T08:46:32.153 回答