如何在递归函数中创建一个计数器

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)

我写了这个脚本来解决“河内塔”。该脚本工作得非常好，但我也想打印出解决问题所需的移动次数。我只是无法弄清楚我可以如何放置一种计数器：如何在递归函数中创建一个计数器

它需要解决的移动次数。
执行“塔”功能的次数。

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

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

此外，有人能告诉我一些有用的河内塔和递归的优点？唯一能找出的就是它的简单性。

来源

2013-02-24 Tachyon

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

在效率方面，它看起来像你的解决方案将在n塔工作。如果你想更有效地解决这个经典问题，看看这个链接：

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

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

来源

2013-02-24 14:39:40 christopher

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

count = 0 

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

def Towers(...): 
    global count 
    count += 1 
    ...

来源

2013-02-24 14:37:57 Don

是的。但是当我再次运行它时，它会从之前的值开始计数。 :) – Tachyon 2013-02-24 15:03:04

你是对的：我更新了答案 – Don 2013-02-24 23:54:05

一种方式是通过所有这样的呼叫进行计数：

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-24 14:45:54 uselpa

啊，我正要发布这个。哦，你先到它:) – 2013-02-24 14:46:26

糟糕 - 对不起;-) – uselpa 2013-02-24 14:50:09

哦..谢谢.. ..这在Python中效果很好。我实际上正在努力在基于8051的系统上移植此代码，但“count = 0”在C :( – Tachyon 2013-02-24 15:00:37

你可以做一个函数对象而不是函数：

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-24 14:49:00

我还要好喜欢这个版本，没有额外的参数 '计数'：

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-24 17:10:18 uselpa

如何在递归函数中创建一个计数器

回答

相关问题