python算法:汉诺塔

python算法:汉诺塔

首页休闲益智Tower of Hanoi 汉诺塔更新时间:2024-05-01

把圆盘从A移动到C

一,汉诺塔问题的题目

汉诺塔问题

汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

因为有开发智力的作用,这种玩具也很普及

我们编写代码时要遵循汉诺塔的规则: 小圆盘上不能放大圆盘,即大的圆盘不能放在小的圆盘上面

二,汉诺塔问题的解析

1, 先归纳最简单的情况:
1片圆盘时:
如果A柱上只有一个圆盘,
那么移动圆盘的步骤显然是 从A移动到C,即表示成 A–>C

A柱上只有一片圆盘时

2,2片圆盘时:
如果A柱上有两片圆盘,也很容易想到只要3步就可以完成,

第1步:A上第一块–>B
第2步:A上第二块–>C
第3步:B上第一块–>C

A柱上有2片圆盘时

3,3个圆盘时:

把1,2号盘从源柱子A移动到辅助柱子B,
再把3号盘从源柱子A移动到目标柱子C,
最后把1,2号盘从辅助柱子B移动到目标柱子C

把1,2号盘从源柱子A移动到辅助柱子B

把3号盘从源柱子A移动到目标柱子C,把1,2号盘从辅助柱子B移动到目标柱子C

4,总结规律

总结规律即:有2块及以上圆盘时:
将A上面的n-1个圆盘,从A借助C移动到B

将A上面的n-1个圆盘,从A借助C移动到B

将A上最下面的一个圆盘,从A移动到C

将A上最下面的一个圆盘,从A移动到C

将B上面的n-1个圆盘,从B借助A移动到C

将B上面的n-1个圆盘,从B借助A移动到C

三,程序设计

我们根据得到的规律,用递归的方式编写代码:

只有一块圆盘时: 把圆盘直接从A移动到C
有2块及以上圆盘时:
将A上面的n-1个圆盘,从A借助C移动到B
将A最下面的一个圆盘,从A移动到C
将B上面的n-1个圆盘,从B借助A移动到C
有递归终止条件,
有对自身的调用,很适合用递归函数来解决

四,编写代码:

使用递归方法

# 递归函数 # n: 共几块圆盘 # a: 源柱子 # b: 辅助柱子 # c: 目标柱子 def hanoi(n, a, b, c): if n == 1: # 只有一块圆盘时,把圆盘直接从A移动到C,递归终止 print("{}:{}->{}".format(1, a, c)) else: # 2片及以上时, hanoi(n - 1, a, c, b) # 将A上面的n-1个圆盘,从A借助C移动到B print("{}:{}->{}".format(n, a, c)) # 将A最下面的一个圆盘,从A移动到C hanoi(n - 1, b, a, c) # 将B上面的n-1个圆盘,从B借助A移动到C 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

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved