python - 汉诺塔非递归: Is my code correct?

Question

我使用非递归方法为汉诺塔问题编写了以下代码。我猜这是不正确的，因为移动次数不是 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()

Answer 1

我认为您的算法存在根本性缺陷(无罪):

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

按照我的阅读方式，您从“左”堆栈中取出 num-1 个“环”并将它们放在“中间”堆栈中，然后将剩余的环从“左”堆栈移至“右”堆栈(目标堆栈)。我以为汉诺塔的工作方式是一次移动 1 个环？

因此，在您的情况下，当 Num = 3 时，Aux = 2 后 1 步，这是不可能的。

也许在这里看看:http://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution它以多种不同的形式描述了汉诺塔问题。