方案：河内塔（递归）

Question

首先我想说这是作业；所以我不是在寻求解决方案，只是一些提示。大约一个星期以来，我一直在思考这个问题。我提出的每个解决方案都不会递归地执行它，因为我无法集中精力以列表作为唯一参数递归地执行它。我的教授说他们可以用大约 6 个辅助函数来完成。

如前所述，我必须解决将列表作为唯一参数的问题。这是我最近尝试的一个例子。

(define (sumSublists lst)
  (if (= (length lst) 0)
      0
      (+ (length (car lst)) (sumSublists (cdr lst)))
  )
)

(define (hanoi towersNum)
  (sub1 (sumSublists towersNum))

    (if (= (sumSublists towersNum) 1)
        (print towersNum)
        (begin (if (= (sumSublists towersNum) 1)
                   (print towersNum)
                   (hanoi '((car towersNum) (cddr towersNum) (cadr towersNum)))
               )
               (if (= (sub1 (sumSublists towersNum)) 1)
                   (print towersNum)
                   (hanoi '((car towersNum) (cadr towersNum) (cddr towersNum)))
               )
               (if (= (sub1 (sumSublists towersNum)) 1)
                   (print towersNum)
                   (hanoi '((cddr towersNum) (cadr towersNum) (car towersNum))) 
               )
        )
    )
)

sumSublists returns 游戏中有多少个磁盘。我得到一个无限循环，因为每次使用它时它都采用相同的值，因此永远不会减少该值。我的问题是，我已经习惯了使用变量的命令式和 OOP，以至于我不确定当 Hanoi 只接受一个参数时我该如何做到这一点。

Hanoi 的代码是我尝试将我的项目从 C++ 转换为 Scheme。

感谢任何帮助。顺便说一句，我正在使用 Dr. Racket 作为我的 IDE。

Answer 1

汉诺塔本质上是一个递归问题，它有一个优雅的递归解决方案。我不会直接给你解决方案，但我会解释解决方案背后的直觉。考虑：

        +---+                     |                       |
        | 1 |                     |                       |
    +-----------+                 |                       |
    |     2     |                 |                       |
+-------------------+             |                       |
|         3         |             |                       |
+-------------------+   +-------------------+   +-------------------+

          A                       B                       C

给定 n 个圆盘，最小的圆盘标记为 1，最大的圆盘标记为 n。我们的工作是将所有圆盘从堆栈 A 移动到堆栈 C，同时保持较大圆盘永远不会放在较小圆盘顶部的不变性。没有这个不变量，解决方案将是微不足道的。

现在，我们可以将圆盘 n 从 A 移动到 C 的唯一方法是首先将其上方的所有圆盘从 A 移动到 B.

          |                       |                       |
          |                       |                       |
          |                     +---+                     |
          |                     | 1 |                     |
+-------------------+       +-----------+                 |
|         3         |       |     2     |                 |
+-------------------+   +-------------------+   +-------------------+

          A                       B                       C

我们的解决方案现在很简单。我们可以通过三个简单的步骤解决我们的问题。首先，我们将 n 以上的所有棋子从 A 移动到 B。接下来，我们将圆盘 n 从 A 移动到 C。最后，我们将剩余的圆盘从 B 移动到 C.

我们将所有圆盘从 A 移动到 C 的问题现在已分为两个子问题：

将所有小于圆盘 n 的圆盘从 A 移动到 B。
将所有小于圆盘 n 的圆盘从 B 移动到 C.

我们如何解决这些子问题？我们不必。通过递归原理，我们已经解决了这些子问题。

现在，我们有三个标记为 A、B 和 C 的堆栈。但是，我们想从源栈、目标栈和辅助栈的角度来讨论这些栈。在解决将圆盘 n 从 A 移动到 C 的问题时，我们称 A 为源，C 为目标。此外，我们还需要使用我们称之为辅助堆栈的B。

需要注意的一件重要事情是源、目标和辅助堆栈不断变化。对于“将光盘 n 从 A 移动到 C” 的问题，源是 A，目标是 C。但是，对于“将光盘 n - 1 从 A 移动到 B” 的问题，源是 A，但目标是 B。第三个堆栈（不是源也不是目标）始终是辅助堆栈。

这应该会给您足够的洞察力来解决汉诺塔问题。当您真正解决它时，您会惊讶地发现与命令式代码相比，该解决方案是多么简单、优雅和直接。

Answer 2

如果你知道如何用包含三个列表 A、B 和 C 的三个参数来解决它，你已经知道如何用一个参数来解决它列表中的三个列表，(A B C)。

问题是计数，因为您不允许使用单独的参数来保存其中的数字。没关系，你可以通过列表来计算，它的长度作为数量。如果一个列表的长度是 n，很容易从中创建一个长度为 n-1 的列表。所以最后你只需要 null?.

此方案会让您始终将项目从参数列表的第一个条目移动到第二个条目，使用 head 元素作为临时元素，您可以根据需要打开和关闭新的 "levels"。这三个 "poles" 必须命名，才能排序回最终的 return.

的原始顺序

（参见，其中讨论了实际的递归算法本身）。

方案：河内塔（递归）

Scheme: Towers of Hanoi (recursion)

recursion

scheme

towers-of-hanoi

racket