河内塔非递归：我的代码是否正确？

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“环”，并把它们放在'中'堆栈，然后将其余环从'左'堆栈移动到'右'堆栈（目标堆栈）。我以为河内塔的工作方式是每次移动一个环？

因此，在你的情况下，当Num = 3，Aux = 2后1移动，这应该是不可能的。

也许看看这里：http://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution 它描述了许多不同形式的河内问题的塔。