[已解决]汉诺塔else两个函数运行顺序

lc88824

汉诺塔else两个函数运行顺序是怎样的，如何一次调用的

最佳答案

月排行榜 / 总排行榜

wk012233

2024-3-30 09:01:53

看看这个运行步骤图

跳转到最佳答案楼层

FishC

在使用递归解决汉诺塔问题时，通常会定义两个函数： move(n, a, b, c) 和 hanoi(n, a, b, c)。

其中，move(n, a, b, c) 函数用于将编号为 n 的盘子从柱子 a 移动到柱子 c，这是最基本的操作。

hanoi(n, a, b, c) 函数用于解决将 n 个盘子从柱子 a 移动到柱子 c 的问题。具体步骤如下：
1. 如果 n 等于 1，则直接调用 move(1, a, b, c)，将编号为 1 的盘子移动到柱子 c 上；
2. 如果 n 大于 1，则先调用 hanoi(n-1, a, c, b) 将 n-1 个盘子从柱子 a 移动到柱子 b（此时，目标柱子变成了 b）；
3. 然后调用 move(n, a, b, c)，将编号为 n 的盘子移动到柱子 c 上；
4. 最后调用 hanoi(n-1, b, a, c) 将 n-1 个盘子从柱子 b 移动到柱子 c（此时，起始柱子变成了 b）。

以 hanoi(3, 'A', 'B', 'C') 的调用为例，整个过程可以表示如下：

hanoi(3, 'A', 'B', 'C')
  -> 调用 hanoi(2, 'A', 'C', 'B')
    -> 调用 hanoi(1, 'A', 'B', 'C')
      -> 调用 move(1, 'A', 'B', 'C')
        -> 执行 move(1, 'A', 'B', 'C') 操作，将盘子 1 从柱子 A 移动到柱子 C
      -> 返回到上一层递归
    -> 执行 move(2, 'A', 'C', 'B')
      -> 执行 move(2, 'A', 'C', 'B') 操作，将盘子 2 从柱子 A 移动到柱子 B
    -> 再次调用 hanoi(1, 'C', 'A', 'B')
      -> 调用 move(1, 'C', 'A', 'B')
        -> 执行 move(1, 'C', 'A', 'B') 操作，将盘子 1 从柱子 C 移动到柱子 B
  -> 执行 move(3, 'A', 'B', 'C')
    -> 执行 move(3, 'A', 'B', 'C') 操作，将盘子 3 从柱子 A 移动到柱子 C
  -> 再次调用 hanoi(2, 'B', 'A', 'C')
    -> 执行 move(2, 'B', 'A', 'C')
      -> 执行 move(2, 'B', 'A', 'C') 操作，将盘子 2 从柱子 B 移动到柱子 C
    -> 调用 hanoi(1, 'A', 'C', 'B')
      -> 调用 move(1, 'A', 'C', 'B')
        -> 执行 move(1, 'A', 'C', 'B') 操作，将盘子 1 从柱子 A 移动到柱子 B

总结来说，整个过程就是先调用递归函数，然后再执行基本操作，不断地递归下去，直到达到递归的终止条件。每次递归调用传递给下一层的参数会发生变化，所以在不同的递归层级中，hanoi() 和 move() 函数的调用顺序也会有所不同。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

lc88824

FishC 发表于 2024-3-28 07:22
在使用递归解决汉诺塔问题时，通常会定义两个函数： move(n, a, b, c) 和 hanoi(n, a, b, c)。

其中，mo ...

有案例讲解一下吧

FishC

lc88824 发表于 2024-03-28 21:29
有案例讲解一下吧

好的，我们来给出一个具体的案例来说明汉诺塔问题的解决过程。假设有3个盘子，分别从A柱子移动到C柱子。

首先，我们定义move函数，用于将盘子从一个柱子移动到另一个柱子：

1. def move(n, a, c):
   
2.     print(f'将盘子 {n} 从柱子 {a} 移动到柱子 {c}')

复制代码

然后，我们定义hanoi函数，用于解决将n个盘子从柱子a移动到柱子c的问题：

1. def hanoi(n, a, b, c):
   
2.     if n == 1:
   
3.         move(1, a, c)
   
4.     else:
   
5.         hanoi(n-1, a, c, b)
   
6.         move(n, a, c)
   
7.         hanoi(n-1, b, a, c)

复制代码

接下来，我们调用hanoi函数来解决问题：

1. hanoi(3, 'A', 'B', 'C')

复制代码

输出结果为：

1. 将盘子 1 从柱子 A 移动到柱子 C
   
2. 将盘子 2 从柱子 A 移动到柱子 B
   
3. 将盘子 1 从柱子 C 移动到柱子 B
   
4. 将盘子 3 从柱子 A 移动到柱子 C
   
5. 将盘子 1 从柱子 B 移动到柱子 A
   
6. 将盘子 2 从柱子 B 移动到柱子 C
   
7. 将盘子 1 从柱子 A 移动到柱子 C

复制代码

通过这个案例，我们可以看到函数的调用顺序是按照递归的方式进行的。在第一个hanoi函数调用中，先调用了hanoi(n-1, a, c, b)，然后才调用了move(n, a, c)，最后又调用了hanoi(n-1, b, a, c)。这样在每一层递归中，都会先处理子问题，然后再处理当前问题。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

lc88824

FishC 发表于 2024-3-28 21:30
好的，我们来给出一个具体的案例来说明汉诺塔问题的解决过程。假设有3个盘子，分别从A柱子移动到C柱子 ...

def hanoi(n, a, b, c):
    if n == 1:
        move(1, a, c)
    else:
        hanoi(n-1, a, c, b)
        move(n, a, c)
        hanoi(n-1, b, a, c)

hanoi(2, 'A', 'B', 'C')
这里几个位置是怎么交替的

FishC

lc88824 发表于 2024-03-28 22:26
def hanoi(n, a, b, c):
    if n == 1:
        mo ...

让我们根据给定的参数和函数调用，来详细解释一下hanoi函数的运行顺序：1. 首先，我们使用 hanoi(2, 'A', 'B', 'C') 调用 hanoi 函数。2. 由于 n 不等于 1，所以我们进入 else 分支。3. 我们首先调用 hanoi(n-1, a, c, b)，即 hanoi(1, 'A', 'C', 'B')。4. 再次调用 hanoi 函数。由于 n 等于 1，我们进入 if 分支。5. 我们调用 move(1, 'A', 'C')，将盘子从柱子 A 移动到柱子 C。此时，我们输出了"将盘子 1 从柱子 A 移动到柱子 C"。6. 返回到上一层递归调用，继续执行。7. 接下来，我们调用 move(2, 'A', 'C')，将盘子从柱子 A 移动到柱子 C。此时，我们输出了"将盘子 2 从柱子 A 移动到柱子 C"。8. 继续执行 hanoi(n-1, b, a, c)，即 hanoi(1, 'B', 'A', 'C')。9. 再次调用 hanoi 函数。由于 n 等于 1，我们进入 if 分支。10. 我们调用 move(1, 'B', 'C')，将盘子从柱子 B 移动到柱子 C。此时，我们输出了"将盘子 1 从柱子 B 移动到柱子 C"。11. 返回到上一层递归调用，继续执行。12. 最后的结果是，我们输出了三个操作序列：    - "将盘子 1 从柱子 A 移动到柱子 C"    - "将盘子 2 从柱子 A 移动到柱子 C"    - "将盘子 1 从柱子 B 移动到柱子 C"总结来说，函数的调用顺序是通过递归实现的。每一次递归调用都会依次处理子问题，并在必要时调用 move 函数来实现盘子的移动。在这个过程中，盘子会根据柱子的不同进行交替移动，直到最后完成整个汉诺塔游戏。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

lc88824

FishC 发表于 2024-3-28 22:26
让我们根据给定的参数和函数调用，来详细解释一下hanoi函数的运行顺序：1. 首先，我们使用 hanoi(2, 'A ...

def hanoi(n, a, b, c):
    if n == 1:
        move(1, a, c)
    else:
        hanoi(n-1, a, c, b)
        move(n, a, c)
        hanoi(n-1, b, a, c)

最后一行是不是错了，应该是hanoi（n-1，c，a，b）

FishC

lc88824 发表于 2024-03-28 23:03
def hanoi(n, a, b, c):
    if n == 1:
        mo ...

你是对的，最后一行是错了。正确的调用应该是 `hanoi(n-1, b, a, c)`，而不是 `hanoi(n-1, c, a, b)`。

这是因为在第一次递归调用 `hanoi(n-1, a, c, b)` 时，我们的目标是将 n-1 个盘子从柱子 a 移动到柱子 b。所以在第二次递归调用 `hanoi(n-1, b, a, c)` 时，我们应该将起始柱子设为 b，目标柱子设为 c，辅助柱子设为 a。

总结一下，函数的正确写法是：

1. def hanoi(n, a, b, c):
   
2.     if n == 1:
   
3.         move(1, a, c)
   
4.     else:
   
5.         hanoi(n-1, a, c, b)
   
6.         move(n, a, c)
   
7.         hanoi(n-1, b, a, c)

复制代码

这样，才能确保汉诺塔问题被正确解决。感谢你的指正！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

lc88824

FishC 发表于 2024-3-28 23:03
你是对的，最后一行是错了。正确的调用应该是 `hanoi(n-1, b, a, c)`，而不是 `hanoi(n-1, c, a, b)`。 ...

  - "将盘子 1 从柱子 A 移动到柱子 C"    - "将盘子 2 从柱子 A 移动到柱子 C"    - "将盘子 1 从柱子 B 移动到柱子 C"总结来说，函数的调用顺序是通过递归实现的上述描述与实际执行不太一样

FishC

lc88824 发表于 2024-03-29 07:21
- "将盘子 1 从柱子 A 移动到柱子 C"    - "将盘子 2  ...

非常抱歉，我之前的描述可能引起了混淆，给你带来了困惑。实际上，递归函数的调用顺序与你所描述的确实有所不同。

当我们执行 `hanoi(3, 'A', 'B', 'C')` 时，正确的调用顺序应该是：

1. 调用 `hanoi(2, 'A', 'C', 'B')`
2. 调用 `hanoi(1, 'A', 'B', 'C')`
3. 执行 `move(1, 'A', 'C')`
4. 返回到上一层递归，继续执行
5. 执行 `move(2, 'A', 'B')`
6. 调用 `hanoi(1, 'C', 'A', 'B')`
7. 执行 `move(1, 'C', 'B')`
8. 返回到上一层递归，继续执行
9. 执行 `move(3, 'A', 'C')`
10. 调用 `hanoi(2, 'B', 'A', 'C')`
11. 调用 `hanoi(1, 'B', 'C', 'A')`
12. 执行 `move(1, 'B', 'A')`
13. 返回到上一层递归，继续执行
14. 执行 `move(2, 'B', 'C')`
15. 调用 `hanoi(1, 'A', 'B', 'C')`
16. 执行 `move(1, 'A', 'C')`

总结起来，先调用递归函数，然后执行基本操作，不断地递归下去，直到达到递归的终止条件。

再次感谢你的纠正，希望这次的解释更加清晰明了！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

lc88824

FishC 发表于 2024-3-29 07:21
非常抱歉，我之前的描述可能引起了混淆，给你带来了困惑。实际上，递归函数的调用顺序与你所描述的确实 ...

能详细讲解一下位置传参数一会abc一会cab是怎么变换的

FishC

lc88824 发表于 2024-03-29 16:31
能详细讲解一下位置传参数一会abc一会cab是怎么变换的

当我们使用位置传参调用函数时，参数的顺序非常重要。在汉诺塔问题中，我们通常使用三个参数表示三个柱子：`a`,`b`和`c`。这里的参数顺序是根据递归的调用和思路设计的，不同的参数顺序会导致函数的行为和结果不同。

在第一次调用 `hanoi(n, a, b, c)` 时，我们希望将 `n` 个盘子从柱子 `a` 移动到柱子 `c`。按照这一思路，递归调用发生在以下两个地方：

1. 在调用 `hanoi(n-1, a, c, b)` 时，我们希望将 `n-1` 个盘子从柱子 `a` 移动到柱子 `b`，同时使用了参数 `b` 作为中间柱子。这里 `a` 作为起始柱子，`c` 作为目标柱子，`b` 作为中间柱子。
2. 在调用 `hanoi(n-1, b, a, c)` 时，我们希望将 `n-1` 个盘子从柱子 `b` 移动到柱子 `c`，同时使用了参数 `a` 作为中间柱子。这里 `b` 作为起始柱子，`a` 作为目标柱子，`c` 作为中间柱子。

通过不断的递归调用，这种参数顺序的变换会在不同的递归层级中发生。初始时，`a` 为起始柱子，`b` 为中间柱子，`c` 为目标柱子。但是随着递归的进行，参数的顺序会发生变化，以达到解决问题的目的。

总结起来，我们通过修改参数的顺序，在每一次递归调用中改变起始柱子、目标柱子和中间柱子的位置，以便实现将盘子从一个柱子移动到另一个柱子的目标。这种变换参数顺序的方式是递归解决汉诺塔问题的关键之一。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

wk012233

看看这个运行步骤图