[Python3 练习] 006 汉诺塔2 非递归解法
2024-08-30 23:03:18
题目:汉诺塔 II
- 接上一篇 [Python3 练习] 005 汉诺塔1 递归解法
- 这次不使用递归
- 不限定层数
(1) 解决方式
- 利用“二进制”
(2) 具体说明
- 统一起见
- 我把左、中、右三根柱子依次称为 A 塔、B 塔、C 塔
- 金片默认都在 A 塔
- n 片金片从小到大依次编号为 0 号、1 号、……、n-1 号
1) 举个“栗子”
- 假设有一个 4 层高的汉诺塔,设初始值为 0000(2)
- 按 "8"、"4"、"2"、"1" 称呼二进制的各位
- "8"位、"4"位、"2"位、"1"位依次对应 3 号金片、2 号金片、1号金片、0 号金片
- 如图
- 开始累加,每次加 1
- 0000(2) -> 0001(2)
- "1"位由 0 变 1,则将 0 号金片右移,即将 0 号金片由 A 塔移至 B塔
- 补充:若要将 C 塔上的金片右移,则移至 A 塔,三个塔是循环的
- 如图
- 0001(2) -> 0010(2)
- 产生进位;进到哪位,则移动该位对应的金片
- 此时进位至"2"位,则右移 1 号金片
- 右移 1 号金片时,因为 1 号金片不能放在 B 塔的 0 号金片上方,所以继续向右走,C 塔正好符合要求
- 如图
- 0010(2) -> 0011(2)
- "1"位由 0 变 1,则将 B 塔的 0 号金片右移至 C 塔
- 如图
- 0011(2) -> 0100(2)
- 产生进位,此时进至“4”位,则将 A 塔上的 2 号金片右移至 B 塔
- 如图
- 0100(2) -> 0101(2)
- 个位由 0 变 1,则将 C 塔的 0 号金片右移至 A 塔
- 如图
……
- 按这个方法进行下去,当数字变成 "1111" 时,A 塔的 4 片金片就都在 C 塔上了
2) 一些说明
此“二进制”方法可以解决汉诺塔,但奇数金片与偶数金片在结果上有些许不同
- 按照上面的规则,奇数金片最终会移至 B 塔,偶数金片最终会移至 C 塔
- 可借高数中“轮换对称性”的思想,在面对奇数金片时,把原来的 B 塔看成 C 塔,把原来的 C 塔看成 B 塔
上面的操作有 2 个规律
- 规律一
- 因为每走一步,数值加 1,所以该二进制数即为步数
- 该二进制数末尾 0 的个数对应要移动的金片编号
- 没有 0,即为 0 个 0,对应 0 号金片;可回顾图 "0001"、"0011"、"0101"
- 1 个 0,对应 1 号金片;可回顾图 "0010"
- 2 个 0,对应 2 号金片;可回顾图 "0100"
- 依此类推
- 规律二
- 编号为 0、2、4……的金片,总是进行右移操作
- 编号为 1、3、5……的金片,总是进行左移操作
- 三根柱子,右移 2 格即为左移 1 格
- 规律一
3) 计算移动次数
- 按递归的思路,汉诺塔可分成三大步
- 将 A 塔的上面 n-1 片金片移至 B 塔
- 将 A 塔剩余的 1 片金片移至 C 塔
- 将 B 塔的 n-1 片金片移至 C 塔
- 设 f(n) 为 n 片金片完成移动需要的最少次数,则 f(n) = f(n-1) + 1 + f(n-1),即 f(n) = 2f(n-1) + 1
- 若只有 1 片金片,则 f(1) = 1
- 若有 2 片金片,则 f(2) = 3
- 若有 3 片金片,则 f(3) = 7
- 照此规律,可假设 f(n) = 2n - 1
- 莫名想到线代中用的“第一类数学归纳法”,我献丑证一下,算是温故知新
- 证明 f(n) = 2n - 1 成立:
- 当 n = 1 时,f(1) = 21 - 1 = 1,成立
- 当 n = k 时,设 f(k) = 2k - 1 成立
- => 当 n = k + 1 时,f(k+1) = 2f(k) + 1 = 2 * (2k - 1) + 1 = 2k+1 - 1,满足假设
- => 汉诺塔的移动次数为 f(n) = 2n - 1,证毕
(3) 程序
1) 代码
# 不使用递归
def hanoi(n):
tower_belong = [0] * n # 用列表开辟 n 个空间,用于存放 n 个金片各自的编号,编号对应塔号
# 金片移动,编号对应更改
if n % 2 == 0: # 金片数量不同,塔的排序不同
tower_name = ['A', 'B', 'C'] # 若 n 为偶数,最终所有金片恰好能移到右塔
else:
tower_name = ['A', 'C', 'B'] # 若 n 为奇数,最终所有金片会移到中塔
# 用“轮换对称”将 B、C 两塔互换名字,以实现“负负得正”
for step in range(1, 2**n): # n 片金片最少需要移动 2^n - 1 次
bin_step = bin(step) # 求得 step 的二进制数值
gold_num = len(bin_step) - bin_step.rfind('1') - 1
# 计算 step 末尾 0 的个数,得到金片编号;上面说的“规律一”
# 如 step = 0b0001,则 step 末尾 0 的个数为 0,表示此刻应移动 0 号金片
# 如 step = 0b0100,则 step 末尾 0 的个数为 2,表示此刻应移动 2 号金片,依此类推
# rfind 是从 0 开始计数,所以再减个 1
print(f"第 {step:2} 步:移动 {str(gold_num)} 号金片,从 {tower_name[tower_belong[gold_num]]} 塔到", end=' ') # 移出金片的塔
if gold_num % 2 == 0: # 若 num 为 偶数,则右移
tower_belong[gold_num] = (tower_belong[gold_num] + 1) % 3
# 若从 C 塔右移,则又回到了 A 塔
else: # 若 num 为奇数,则左移
tower_belong[gold_num] = (tower_belong[gold_num] + 2) % 3
# 若从 A 塔左移,则又去到了 C 塔
print(tower_name[tower_belong[gold_num]], '塔') # 移入金片的塔
# 清爽、无注释版
def hanoi(n):
tower_belong = [0] * n
if n % 2 == 0:
tower_name = ['A', 'B', 'C']
else:
tower_name = ['A', 'C', 'B']
for step in range(1, 2**n):
bin_step = bin(step)
gold_num = len(bin_step) - bin_step.rfind('1') - 1
print(f"第 {step:2} 步:移动 {str(gold_num)} 号金片,从 {tower_name[tower_belong[gold_num]]} 塔到", end=' ')
if gold_num % 2 == 0:
tower_belong[gold_num] = (tower_belong[gold_num] + 1) % 3
else:
tower_belong[gold_num] = (tower_belong[gold_num] + 2) % 3
print(tower_name[tower_belong[gold_num]], '塔')
2) 运行情况
- 3 层汉诺塔
- 4 层汉诺塔
最新文章
- webapi 控制器接收POST参数时必须以对象的方式接收
- Centos下yum安装PHP
- mina学习(一)
- maven中如何打包源代码
- 2013中国大数据技术大会——BDTC2013
- [Android学习笔记]扩展application
- ACC起来后,usb检测不到
- python多线程爬虫设计及实现示例
- Java - 静态代理详讲
- 洛谷P2617 Dynamic Rankings
- 网络协议 HTTP入门学习
- 关于asyncio知识(一)
- Socket网络编程--网络爬虫(3)
- Jquery在表格中搜索关键字
- c#引用命名空间的作用
- 01-MySql的前戏
- 《Lua程序设计》9.3 以协同程序实现迭代器 学习笔记
- 【转】HttpApplication的认识与加深理解
- IQKeyboardManager 问题锦集
- Redis 实现队列优先级