递归求解汉诺塔:6-start_rods-end_rods作用及移动逻辑疑问
汉诺塔递归实现疑问解答
先贴出你参考的递归实现代码:
def Tower_of_Hanoi(Number_of_disc, start_rods = 1, end_rods = 3): if Number_of_disc: Tower_of_Hanoi(Number_of_disc-1, start_rods, 6-start_rods-end_rods) print(f"Move disc {Number_of_disc}, from start {start_rods} to {end_rods}") Tower_of_Hanoi(Number_of_disc-1, 6-start_rods-end_rods, end_rods)
问题1:6-start_rods-end_rods的作用是什么?它是类似append、sort的操作还是有特定含义的语法?
这既不是Python内置操作也不是特殊语法,就是一个算术计算式。
汉诺塔的三个柱子编号固定为1、2、3,三者总和是6。当你知道起始柱子start_rods和目标柱子end_rods时,用6减去这两个数,就能直接算出剩下的那个「中间过渡柱子」的编号。
比如:
- 起始是1,目标是3,6-1-3=2,中间柱子就是2
- 起始是1,目标是2,6-1-2=3,中间柱子就是3
- 起始是2,目标是3,6-2-3=1,中间柱子就是1
这个式子只是用数学方式快速确定第三个柱子,避免写一堆条件判断。
问题2:运行Number_of_disc=5的案例时,圆盘(如disc1)的移动逻辑是怎样的?为何会出现从1→3再从3→2的移动,这与上述表达式有何关联?
汉诺塔的递归逻辑核心是:要把n个盘子从A移到C,先把n-1个盘子从A移到B,再把第n个盘子从A移到C,最后把n-1个盘子从B移到C。这个过程会层层递归下去,直到处理最小的盘子(disc1)。
以disc1的移动为例,当处理不同层级的递归时,start_rods和end_rods会变化,通过6-start_rods-end_rods算出的过渡柱子也跟着变,导致disc1的移动路径不断切换:
- 首先要把4个盘子从1移到2(为了把disc5从1移到3),这时候递归到处理disc1时,它的起始是1,目标是3(因为6-1-2=3),所以会输出
Move disc 1 from 1 to 3。 - 当处理把3个盘子从3移到1(为了把disc4从2移到3)时,disc1的起始是3,目标是2(6-3-1=2),所以会输出
Move disc 1 from 3 to 2。
简单说,disc1的移动方向完全由当前递归层的「起始柱」和「目标柱」决定,而6-start_rods-end_rods每次都帮程序算出了当前需要的过渡柱,进而影响了下一层递归中disc1的移动目标。
内容的提问来源于stack exchange,提问作者Aflah
相关产品推荐
相关产品推荐

