python - Python 递归（河内塔）

Question

我是 python 新手，遇到了一个可能很难解决的问题。

def req_steps(num_disks):
    # implement this function
    if num_disks == 0:
        return 1 
    return 2 * req_steps(num_disks-1)

print("For moving {} disks, {} steps are required.".format(3, req_steps(3)))

该函数应该是 (2^n)-1 并且我无法让 -1 工作......它必须是一个递归函数。

提前致谢。

编辑：

最终的公式是=(2^(num_of_disks))-1 这意味着，num_of_disks = 3应该给出7哪个是(2*2*2-1)动作。

标签： pythonrecursion

Answer 1

你可以给出最终答案f(n) = 2^n-1，这是一个通用公式，而问题要求你使用递推公式f(n) = f(n-1) + 1 + f(n-1) when n > 1。

    def req_steps(num_disks):
        if num_disks == 1:
            return 1
        else:
            return 1 + 2 * req_steps(num_disks - 1)
    
    print("For moving {} disks, {} steps are required.".format(3, req_steps(3)))

输出：

For moving 3 disks, 7 steps are required.

下面的递推公式表示当你想将 n 个圆盘从 A 移动到 C 时（假设 3 个放置圆盘的杆分别命名为 A、B 和 C），你可以：

1. 将 n-1 个磁盘从 A 移动到 B，这需要 f(n-1) 步
2. 将第 n 个磁盘从 A 移动到 C，需要 1 步
3. 将 n-1 个磁盘从 B 移动到 C，这需要 f(n-1) 步