algorithm - 汉诺塔算法使用递归，同时显示步数

Question

我们都知道解决汉诺塔问题的 python 代码如下:

def hanoi(n, a, b, c):
    if n == 1:
        print a, '-->', c
        return
    hanoi(n-1, a, c, b)
    print a, '-->', c
    hanoi(n-1, b, a, c)

hanoi(4, 'A', 'B', 'C')

我的问题是在哪里添加 print('stepCount ={}'.format(stepCount)) 以显示每个步骤的 stepCount。

****更新和澄清*****而上面代码的输出显示:

A > C
A > B
C > B
A > C
B > A
B > C
A > C

我想知道是否可以将 print 语句添加到代码中以将输出更改为:

stepCount: 1
A > C
stepCount: 2
A > B
stepCount: 3
C > B
stepCount: 4
A > C
stepCount: 5
B > A
stepCount: 6
B > C
stepCount: 7
A > C

Answer 1

@emplatetypedef 描述了如下解决方案:

def hanoi(n, a, b, c, count):
    if n > 0:
        count = hanoi(n-1, a, c, b, count)
        count += 1
        print('stepCount: {}'.format(count))
        print('{} --> {}'.format(a, c))
        count = hanoi(n-1, b, a, c, count)
    return count

hanoi(3, 'A', 'B', 'C', 0)

它也可以用一个全局变量来实现(是的，我知道呃......):

def hanoi(n, a, b, c):
    global stepCount
    if n > 0:
        hanoi(n-1, a, c, b)
        stepCount += 1
        print('stepCount: {}'.format(stepCount))
        print('{} --> {}'.format(a, c))
        hanoi(n-1, b, a, c)


stepCount = 0
hanoi(3, 'A', 'B', 'C')

输出(两个代码片段)

stepCount: 1
A --> C
stepCount: 2
A --> B
stepCount: 3
C --> B
stepCount: 4
A --> C
stepCount: 5
B --> A
stepCount: 6
B --> C
stepCount: 7
A --> C