python - 使用堆栈的 Hanoi Python 解决方案的递归塔

Question

我正在尝试使用堆栈解决汉诺塔问题。这是我的代码:

Init_stack = [0,1,2,3]
Buffer_stack = []
Final_stack = []
n = len(Init_stack)
def move_disks(Init_stack, Buffer_stack, Final_stack, n):
    if n == 0:
        return
    elif n == 1:
        Final_stack.append(Init_stack.pop())
    elif n == 2:
        Buffer_stack.append(Init_stack.pop())
        Final_stack.append(Init_stack.pop())
        Final_stack.append(Buffer_stack.pop())
    else:
        move_disks(Init_stack, Final_stack, Buffer_stack, n-1)
        Final_stack.append(Init_stack.pop())
        move_disks(Buffer_stack, Init_stack, Final_stack,n-1)

当 Init_stack 的大小很小时，比如 < 10，这工作得很好。但是当我在大小为 100 的 Init_stack 上运行这段代码时，程序需要很长时间才能完成。你能告诉我为什么需要这么长时间吗？

Answer 1

汉诺塔需要 (2^n)-1 移动，其中 n 是环数。即使是极其高效的解决方案也需要很长时间才能完成 Python 中的许多操作。

(2^10)-1 等于 1023(每个计算机科学家都知道)，但是 (2^100)-1 是一个 31 位十进制数.