3

非再帰的アプローチを使用して、ハノイの塔の問題に対して次のコードを作成しました。移動の数が 2**n - 1 ではないため、正しくないと思います。たとえば、3 つのディスクを移動するには、7 つの移動を生成する必要があります。前もって感謝します。

######################
#   Towers of Hanoi  #
######################

numbers = []

def TowersofHanoi():
# Proram to simulate Towers of hanoi
# Objective is to move the disks from A to C 
# with B as a temporary varialbel


    print "Program to simulate Towers of Hanoi"
    print "Users will input numbers of disks, which is 'A'"
    print "The disks have to be moved from A to C"
    print "With B as temporary placeholder"


    print "Enter the number of disks to be moved:",

    Num = int (raw_input("> "))
    Src = Num
    Aux = 0
    Dst = 0
    print "you have entered %d disks to be moved"
    print "Source is -->", Src
    print "Auxillary is -->", Aux
    print "Destination is -->", Dst


    print "Disk positions after the placement:"

    #B = A-1
    #print B
    while Num >= 1: 
        print Num
        Aux = Num-1
        Src = Src-Aux   
        Dst = Src   

        print "Source is -->", Src
        print "Auxillary is -->", Aux
        print "Destination is -->", Dst
        Src = Aux
        Num = Num-1

        numbers.append(Dst)
    print numbers


    print "The task of accomplishing the movements of disk is over"
    print "This completes TOWERS OF HANOI!"
    print "Final disk positions are:"
    print "Source is -->", Src
    print "Auxillary is -->", Aux
    print "Destination is -->", len(numbers)

TowersofHanoi()
4

1 に答える 1

0

あなたのアルゴリズムには根本的な欠陥があると思います（違反はありません）：

Aux = Num-1
Src = Src-Aux   
Dst = Src

私がこれを読んだ方法では、「左」スタックから num-1 の「リング」を取り出して「中央」スタックに置き、残りのリングを「左」スタックから「右」スタック (宛先) に移動します。スタック）。ハノイの塔の仕組みは、一度に 1 つのリングを動かすものだと思っていましたか?

したがって、あなたの場合、Num = 3、Aux = 1 移動後に 2 の場合、これは不可能です。

ここを見てください: http://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution ハノイの塔の問題をさまざまな形で説明しています。

于 2012-08-06T10:07:11.833 に答える