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

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

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

于 2012-08-06T10:07:11.833 回答