gpt4 book ai didi

recursion - 汉诺塔 : Recursive Algorithm

转载 作者:行者123 更新时间:2023-12-03 01:40:23 27 4
gpt4 key购买 nike

虽然我在理解递归方面没有任何问题,但我似乎无法理解汉诺塔问题的递归解决方案。这是来自 Wikipedia 的代码:

procedure Hanoi(n: integer; source, dest, by: char);
Begin
if (n=1) then
writeln('Move the plate from ', source, ' to ', dest)
else begin
Hanoi(n-1, source, by, dest);
writeln('Move the plate from ', source, ' to ', dest);
Hanoi(n-1, by, dest, source);
end;
End;

我了解基本情况以及将问题分解为更小部分的概念,直到您能够移动单个磁盘。但是,我无法弄清楚非基本情况下的两个递归调用如何一起工作。也许有人可以帮助我?谢谢。

最佳答案

实际上,section from where you took that code还提供了解释:

To move n discs from peg A to peg C:

  1. move n−1 discs from A to B. This leaves disc #n alone on peg A
  2. move disc #n from A to C
  3. move n−1 discs from B to C so they sit on disc #n

很明显,您首先必须删除 n - 1 张光盘才能访问第 n 光盘。而且你必须先将它们移动到另一个钉子上,而不是你希望整个塔出现的位置。

除了光盘数量之外,您帖子中的代码还包含三个参数:钉、目的地钉和临时钉其间可以存储哪些光盘(每个大小为 n - 1 的光盘都适合)。

递归实际上发生了两次,一次在 writeln 之前,一次在之后。 writeln 之前的一个会将 n - 1 个光盘移动到临时 Hook 上,使用目标 Hook 作为临时存储(递归调用中的参数顺序不同)。之后,剩余的圆盘将被移动到目标桩,然后第二次递归通过将 n - 1 塔从临时桩移动到目标桩来强制移动整个塔。光盘n.

关于recursion - 汉诺塔 : Recursive Algorithm,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1223305/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com