DDR爱好者之家

python实现三壶谜题的示例详解
站长资源 2024/11/24 佚名
31 1538
DDR爱好者之家 Design By 杰米

前言

有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。

一、算法思想

算法分析

  1. 采用的算法思想是将某个时刻水壶中水的数量看作一个状态，用一个长度为3的数组表示。
  2. 初始状态便为[8,0,0],再拓展他的下一结点的可能结构。
  3. 若下一结点的结构已经被拓展过了便放弃，若没有拓展过则加入拓展列表（open_list）中。然后递归上述操作。
  4. 直到拓展列表（open_list）为空或者找到目标为止。

思想图解

这里的第一个数就代表着是那个8品脱的瓶子，依次分别是8品脱，5品脱，3品脱

python实现三壶谜题的示例详解

就如同上图一样，使用层次遍历一次一次递归扩展新的结点，知道找到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])

总结

主要是用广度优先遍历的思想和树结构，当然如果不在意找到4品脱的水的路径，其实没必要使用树结构。另外打印函数是从最后一层依次往上回溯的，所以显示的是倒序的路径。如果需要变成正向的话，可以加一个栈来实现。

DDR爱好者之家 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
DDR爱好者之家 Design By 杰米
ddrfans.com DDR爱好者之家
8,675无损音乐
1,324高清电影
213破解软件
70,141收录资讯

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米