河內塔非遞歸：我的代碼是否正確？

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 它描述了許多不同形式的河內問題的塔。