时间戳

首页 > 解决方案 > 需要河内塔的功能说明

python - 需要河内塔的功能说明

问题描述

我目前正在学习一门课程，我们被要求为河内塔数学谜题编写一个函数。

在 youtube 上跟进了一些关于它的视频后，我编译了以下函数：

def hanoi(n , source, target, spare):
    if n == 1:
        print("Move disk 1 from", source, "to", target)
    else:
        hanoi(n-1, source, spare, target)
        print ("Move disk", n, "from", source, "to", target)
        hanoi(n-1, spare, target, source)

假设我将此函数称为hanoi(3, "source", "target", "spare")

我得到的输出是：

Move disk 1 from source to target
Move disk 2 from source to spare
Move disk 1 from target to spare
Move disk 3 from source to target
Move disk 1 from spare to source
Move disk 2 from spare to target
Move disk 1 from source to target

一位朋友建议我将代码写在纸上以便理解，但我无法理解：

非常感谢您的帮助和时间！

编辑：河内塔意味着（默认情况下）有 3 根电线杆。一个极点是source极点（最初放置n 个spare磁盘的地方），第二个极点是用作辅助的极点，第三个极点是target极点（最初放置所有n 个磁盘的地方）。我使用这些变量来表示极点并能够显示磁盘的运动

规则是：一次只能移动 1 个磁盘，不能将较大的磁盘放在较小的磁盘上。

标签： pythonpython-3.x

解决方案

似乎评论太短了，无法清楚地解释。

每个函数调用都从其第一行开始。在函数结束后，代码会回到它被调用的地方。

朋友推荐我把代码写在纸上以便理解

这就是我们要在这里做的。逐行分析代码，看看它什么时候深入，什么时候离开。

  • hanoi(3, "source", "target", "spare")这将转到else. 并hanoi以 n=2运行

    • 所以n = 2，对吗？于是我们else再次进入。hanoi 再次运行，但 n=1
      • 我们更深入！现在n = 1，所以我们终于命中了print！那是Move disk 1 from to target从哪里来的！函数退出。
    • 我们回到它被调用的地方。我们首先hanoi在else. 现在我们又打了一个print。那是Move disk 2 from source to spare从哪里来的。
    • 我们进入下一行。我们hanoi再次以 n=1 运行。
      • 我们又进去了。n=1，所以我们进入if并打印Move disk 1 from target to spare并退出
    • 我们到了调用它的地方（所以我们处于 n=2 级别）但我们没有更多的行要运行。我们退出

  • 我们回到了顶层。现在我们打印Move disk 3 from source to target

  • 下一行。另一个调用hanoi, n=2

    • n = 2，再次：否则，更深入
      • n=1，打印，退出
    • 我们回去了，所以我们打印
    • 再深入一点
      • n=1，打印，退出
    • 出口

  • 出口

要了解递归，您实际上可以在进入和离开时进行调试打印。

def hanoi(n , source, target, spare):
    print(f"   DEBUG: Starting hanoi({n}, {source}, {target}, {spare})")
    if n == 1:
        print("Move disk 1 from", source, "to", target)
    else:
        hanoi(n-1, source, spare, target)
        print ("Move disk", n, "from", source, "to", target)
        hanoi(n-1, spare, target, source)
    print(f"   DEBUG: Exiting hanoi({n}, {source}, {target}, {spare})")

>>> hanoi(3, "src", "trg", "spr")
   DEBUG: Starting hanoi(3, src, trg, spr)
   DEBUG: Starting hanoi(2, src, spr, trg)
   DEBUG: Starting hanoi(1, src, trg, spr)
Move disk 1 from src to trg
   DEBUG: Exiting hanoi(1, src, trg, spr)
Move disk 2 from src to spr
   DEBUG: Starting hanoi(1, trg, spr, src)
Move disk 1 from trg to spr
   DEBUG: Exiting hanoi(1, trg, spr, src)
   DEBUG: Exiting hanoi(2, src, spr, trg)
Move disk 3 from src to trg
   DEBUG: Starting hanoi(2, spr, trg, src)
   DEBUG: Starting hanoi(1, spr, src, trg)
Move disk 1 from spr to src
   DEBUG: Exiting hanoi(1, spr, src, trg)
Move disk 2 from spr to trg
   DEBUG: Starting hanoi(1, src, trg, spr)
Move disk 1 from src to trg
   DEBUG: Exiting hanoi(1, src, trg, spr)
   DEBUG: Exiting hanoi(2, spr, trg, src)
   DEBUG: Exiting hanoi(3, src, trg, spr)

看看添加的打印行如何与我写的内容对齐。

推荐阅读