0

最近、私は C++ 開発者のポジションの面接を受けていて、3 列で 1000000 ディスクのハノイ タワー パズルを解くプログラムを作成するように依頼されました。 "1->2" など)、ハノイ タワーの移動の最小量は 2 乗 n - 1 であり、1000000 の場合、これは非常に大きくなるため、これは非常に大きなファイルになると彼らに伝えました。どのハードドライブにも収まらない大きな数、彼らは、古典的なアルゴリズムは間違っていて、1000000 枚のディスクでもこのパズルを解けるアルゴリズムがあると言っています。そのようなアルゴリズムが存在するのか、それとも単に私に嘘をついているのか知りたいですか?

ありがとう、ティムール。

4

2 に答える 2

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 に答える