python - 如何避免在河内塔进行无限次数的操作

Question

我需要计算解决河内塔问题所需的步骤数（借助递归）。我的脚本只适用于较少数量的磁盘，但如果我尝试像 12 之类的东西，它表明我需要无限数量的操作来计算结果。我无法弄清楚我的错误在哪里：

steps = 0

def req_steps(num_disks):
    global steps
    if num_disks >= 1:
        req_steps(num_disks - 1)
        #steps += 1
        req_steps(num_disks - 1)
        steps += 1
        return steps
    return -1

if __name__ == '__main__':
    print(3, req_steps(12))

标签： pythonrecursiontowers-of-hanoi

Answer 1

要计算河内塔的移动次数，有（至少）三种方法。

1.) 求解河内塔并使用全局变量进行计数

• 添加一个全局变量作为计数器
• 对河内的塔实施解决方案，
• 删除所有打印语句
• 在您将移动磁盘的每个位置增加全局计数器

现在运行这个解决方案。将全局变量重置为 0，运行您的脚本并在最后检查全局变量的结果

2.) 实现 Towers of Hanoi 并让函数返回每个解决方案的移动次数（只需删除打印语句）

我认为这个解决方案更干净，因为它不需要全局。

3.) 不要写程序，只要做一个数学证明，解是 2**n -1 （这种方法叫做数学归纳法）

附上2的解决方案。）

def req_steps(num_disks):
    if num_disks > 1:
        steps = req_steps(num_disks - 1)
        steps += req_steps(num_disks - 1)
        steps += 1
        return steps
    return 1

if __name__ == '__main__':
    for i in range(1,13):
        print("%2d %4d %4d" % (i, req_steps(i), 2 ** i - 1))

输出应如下所示：

 1    1    1
 2    3    3
 3    7    7
 4   15   15
 5   31   31
 6   63   63
 7  127  127
 8  255  255
 9  511  511
10 1023 1023
11 2047 2047
12 4095 4095