python实现三壶谜题的示例详解
作者:仙九玖玖 时间:2021-12-09 19:56:15
目录
前言
一、算法思想
算法分析
思想图解
二、代码展示
1.创建树节点结构
2.实现倾倒动作
主递归函数
数据初始化
总结
前言
有一个充满水的8品脱的水壶和两个空水壶(容积分别是5品脱和3品脱)。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式,在其中的一个水壶中得到4品脱的水。
一、算法思想
算法分析
采用的算法思想是将某个时刻水壶中水的数量看作一个状态,用一个长度为3的数组表示。
初始状态便为[8,0,0],再拓展他的下一结点的可能结构。
若下一结点的结构已经被拓展过了便放弃,若没有拓展过则加入拓展列表(open_list)中。然后递归上述操作。
直到拓展列表(open_list)为空或者找到目标为止。
思想图解
这里的第一个数就代表着是那个8品脱的瓶子,依次分别是8品脱,5品脱,3品脱
就如同上图一样,使用层次遍历一次一次递归扩展新的结点,知道找到4品脱的水或者无结点可扩展为止(类似于广度优先遍历)。
二、代码展示
1.创建树节点结构
节点包括两个属性,一个属性是数组类型的,存储当前三个水壶的容量状态,另一个属性是记录它是由哪个结点扩展过来的,以便找到解决路径:
class node: # 创建树节点
def __init__(self, data):
self.data = data # 存储三个壶的容量状态
self.per = None # 存储上一时刻三个壶的容量状态
2.实现倾倒动作
由于这里只有三个壶,互相倾倒的方案可以枚举出来,所有我就没使用二重嵌套循环,而是使用一层循环:
def pour(n): # 扩展子节点
r_list = n.data # 记录当前三个水壶的容量状态
max_list = [8, 5, 3] # 水壶的最大容量
for i, j in ((0, 1), (0, 2), (1, 2), (1, 0), (2, 0), (2, 1)):
if r_list[i] != 0:
n_list = r_list.copy() # 初始化下一结点的水壶状态
if r_list[i] + r_list[j] > max_list[j]:
n_list[i] = r_list[i] - (max_list[j] - r_list[j])
n_list[j] = max_list[j]
else:
n_list[j] = r_list[i] + r_list[j]
n_list[i] = 0
flag = True # 记录水壶的状态是否已经发生过(扩展过)
for one in closed_list:
if one.data == n_list: # 比较当前水壶状态和以往记录过得水壶状态
flag = False
if flag:
print("扩展的新节点是:",n_list)
new_node = node(n_list) # 创建新节点存储水壶的新状态
new_node.per = n
open_list.append(new_node)
主递归函数
查看当前是否已经扩展到4品脱的水或者是否还有结点可以扩展。
def BFS_node(root_1): # 递归查找子节点的扩展状态以及查验是否找到4品脱的水壶
n = root_1
print("当前节点:",n.data)
if open_list is None:
return "没有找到4品脱的水"
nodelist = n.data
if 4 in nodelist:
print("找到了4品脱的水")
print_node(n)
return "找到了4品脱的水"
closed_list.append(open_list.pop(0))
pour(n)
print("*******")
BFS_node(open_list[0])
数据初始化
数据初始化,以及找到4品脱水后打印路径的打印函数。
def print_node(n): # 打印正确的水壶操作路径
if n.per == None:
return ""
print(n.data)
print_node(n.per)
# 初始化数据
root = node([8, 0, 0])
open_list = [root] # 存储已找到却未被扩展的子节点
closed_list = [] # 存储已找到且被扩展的子节点
BFS_node(open_list[0])
来源:https://blog.csdn.net/qq_41580347/article/details/109428704
标签:python,三壶谜题
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
导航设计与信息架构
2008-01-13 22:08:00
python中GIL的原理及用法总结
2023-03-11 07:43:13
22个HTML5的初级技巧
2010-12-17 12:39:00
![](https://img.aspxhome.com/file/UploadPic/201012/17/01-40s.jpg)
Django框架中间件(Middleware)用法实例分析
2021-01-04 09:27:38
![](https://img.aspxhome.com/file/2023/4/85154_0s.png)
用途相似的标签
2008-05-23 13:11:00
php控制反转与依赖注入举例讲解
2023-06-10 10:30:22
![](https://img.aspxhome.com/file/2023/4/55364_0s.png)
asp 去除最后一个逗号为空字符串的代码
2010-06-09 19:18:00
sklearn线性逻辑回归和非线性逻辑回归的实现
2021-06-16 04:04:31
![](https://img.aspxhome.com/file/2023/3/72213_0s.png)
Python使用lxml模块和Requests模块抓取HTML页面的教程
2021-08-29 20:55:33
python绘制已知点的坐标的直线实例
2023-03-12 08:36:11
python随机模块random的22种函数(小结)
2022-08-11 18:09:03
![](https://img.aspxhome.com/file/2023/5/76715_0s.png)
Python 输出详细的异常信息(traceback)方式
2023-01-17 11:43:48
![](https://img.aspxhome.com/file/2023/3/89283_0s.jpg)
Python协程的2种实现方式分享
2022-12-21 12:42:56
分享5个python提速技巧,速度瞬间提上来了
2023-11-04 13:04:06
Python 标准库 fileinput与文件迭代器
2023-10-31 22:36:50
Python文本特征抽取与向量化算法学习
2023-07-19 09:44:29
![](https://img.aspxhome.com/file/2023/1/81501_0s.jpg)
thinkPHP5.0框架简单配置作用域的方法
2023-11-14 10:24:51
python 列表套json字典根据相同的key筛选数据
2022-06-01 08:52:02
oracle10g 数据备份与导入
2009-06-10 18:21:00
美之鉴 – 女人与Web设计
2009-12-09 15:36:00
![](https://img.aspxhome.com/file/UploadPic/200912/9/web_and_beauty-36s.jpg)