lc88824 发表于 2024-3-28 07:22:00

汉诺塔else两个函数运行顺序

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

FishC 发表于 2024-3-28 07:22:21

在使用递归解决汉诺塔问题时,通常会定义两个函数: 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 发表于 2024-3-28 21:29:38

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

其中,mo ...

有案例讲解一下吧

FishC 发表于 2024-3-28 21:30:00

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

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

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

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

然后,我们定义hanoi函数,用于解决将n个盘子从柱子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函数来解决问题:

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

输出结果为:

将盘子 1 从柱子 A 移动到柱子 C
将盘子 2 从柱子 A 移动到柱子 B
将盘子 1 从柱子 C 移动到柱子 B
将盘子 3 从柱子 A 移动到柱子 C
将盘子 1 从柱子 B 移动到柱子 A
将盘子 2 从柱子 B 移动到柱子 C
将盘子 1 从柱子 A 移动到柱子 C

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

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

lc88824 发表于 2024-3-28 22:26:07

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 发表于 2024-3-28 22:26:25

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 发表于 2024-3-28 23:03:17

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 发表于 2024-3-28 23:03:30

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。

总结一下,函数的正确写法是:
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)

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

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

lc88824 发表于 2024-3-29 07:21:16

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 发表于 2024-3-29 07:21:27

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 发表于 2024-3-29 16:31:55

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

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

FishC 发表于 2024-3-29 16:32:18

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 发表于 2024-3-30 09:01:53

看看这个运行步骤图
页: [1]
查看完整版本: 汉诺塔else两个函数运行顺序