2 
def printMove(source, destination): 
    print('move From ' + str(source) + ' to destination ' + str(destination))
    count +=1
    print count

def Towers(n, source, destination, spare):
    if not count in  locals():
        count = 0
    if n == 1:
        printMove(source, destination)
        count +=1   
    else:
        Towers(n-1, source, spare, destination)
        Towers(1, source, destination, spare)
        Towers(n-1, spare, destination, source)

我写了这个脚本来解决“河内塔”。该脚本运行良好，但我还想打印解决问题所需的移动次数。我只是无法弄清楚如何放置一种可以计数的计数器：

  1. 解决所需的移动次数。
  2. “Towers”函数执行的次数。

if not count in locals():条件是计算将要解决的移动次数的失败尝试之一。反正我是在正确的轨道上吗？

另外，这个算法有效吗？或者有没有更好的方法来解决这个问题？

此外，有人能告诉我河内塔的一些有用应用和递归的优势吗？我唯一能想到的是它的简单性。

4

6 回答 6

3

一种方法是让计数器通过所有这样的调用：

def towers(n, source, destination, spare, count=0):
    if n == 1:
        count += 1
        print('move From', source, ' to destination ', destination, count)
    else:
        count = towers(n-1, source, spare, destination, count)
        count = towers(1, source, destination, spare, count)
        count = towers(n-1, spare, destination, source, count)
    return count

towers(3, 1, 2, 3)

产量

move From 1  to destination  2 1
move From 1  to destination  3 2
move From 2  to destination  3 3
move From 1  to destination  2 4
move From 3  to destination  1 5
move From 3  to destination  2 6
move From 1  to destination  2 7

关于效率，http ://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution说：“通过数学归纳法，很容易证明上述过程需要尽可能少的移动，并且产生的解决方案是只有一个动作最少的人。”。

递归的主要优点是这些解决方案往往是优雅的。对于某些类型的问题，迭代解决方案比递归解决方案更复杂。

于 2013-02-24T14:45:54.017 回答
1

最简单的方法是使用全局变量：

count = 0

def runTowers(...):
    global count
    count = 0
    Towers(...)

def Towers(...):
    global count
    count += 1
    ...
于 2013-02-24T14:37:57.370 回答
1

您可以创建一个函数对象而不是函数：

class Towers:

    def __init__(self):
        self.count = 0

    def __call__(self, n, source, destination, spare):
        if n == 1:
            self.printMove(source, destination)
            self.count +=1   
        else:
            self(n-1, source, spare, destination)
            self(1, source, destination, spare)
            self(n-1, spare, destination, source)

    def printMove(self, source, destination):
        print('move From ' + str(source) + ' to destination ' 
              + str(destination))
        print(self.count)

towers = Towers()
towers(3, 1, 2, 2)
于 2013-02-24T14:49:00.980 回答
1

我更喜欢这个版本，没有额外的参数“count”：

def towers(n, source, destination, spare):
    count = 0
    if n == 1:
        print('move From', source, ' to destination ', destination)
        return 1
    else:
        count += towers(n-1, source, spare, destination)
        count += towers(1, source, destination, spare)
        count += towers(n-1, spare, destination, source)
        return count

print(towers(3, 1, 2, 3))

产量

move From 1  to destination  2
move From 1  to destination  3
move From 2  to destination  3
move From 1  to destination  2
move From 3  to destination  1
move From 3  to destination  2
move From 1  to destination  2
7
于 2013-02-24T17:10:18.040 回答
0

上面的答案应该会给你答案:)

就效率而言，您的解决方案似乎适用于 n 个塔。如果您希望更有效地解决经典问题，请查看此链接：

http://www.vogella.com/articles/JavaAlgorithmsTowersOfHanoi/article.html

最后，递归的设计目的是制作非常简单的算法，可以使用基本代码执行复杂的计算。缺点是它是内存密集型的（每次调用都会在最后一次调用的堆栈上放置一个新的内存地址）。

于 2013-02-24T14:39:40.947 回答
0

没有时间暂停它，它会很快达到递归限制

import time
def loop_forever(count):
    if count == 0:
        print(count)
        time.sleep(1)
        loop_forever(1)
    if count > 0:
        print(count)
        time.sleep(1)
        loop_forever(count + 1)


loop_forever(0)
于 2019-10-18T15:46:55.350 回答