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

前言

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


一、算法思想

算法分析

  1. 采用的算法思想是将某个时刻水壶中水的数量看作一个状态,用一个长度为3的数组表示。
  2. 初始状态便为[8,0,0],再拓展他的下一结点的可能结构。
  3. 若下一结点的结构已经被拓展过了便放弃,若没有拓展过则加入拓展列表(open_list)中。然后递归上述操作。
  4. 直到拓展列表(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])

总结

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

到此这篇关于python实现三壶谜题的示例详解的文章就介绍到这了,更多相关python三壶谜题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • python实现单目标、多目标、多尺度、自定义特征的KCF跟踪算法(实例代码)

    单目标跟踪: 直接调用opencv中封装的tracker即可. #!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Created on Sun Jan 5 17:50:47 2020 第四章 kcf跟踪 @author: youxinlin """ import cv2 from items import MessageItem import time import numpy as np ''

  • Python实现常见的几种加密算法(MD5,SHA-1,HMAC,DES/AES,RSA和ECC)

    生活中我们经常会遇到一些加密算法,今天我们就聊聊这些加密算法的Python实现.部分常用的加密方法基本都有对应的Python库,基本不再需要我们用代码实现具体算法. MD5加密 全称:MD5消息摘要算法(英语:MD5 Message-Digest Algorithm),一种被广泛使用的密码散列函数,可以产生出一个128位(16字节)的散列值(hash value),用于确保信息传输完整一致.md5加密算法是不可逆的,所以解密一般都是通过暴力穷举方法,通过网站的接口实现解密.Python代码: i

  • python应用Axes3D绘图(批量梯度下降算法)

    本文实例为大家分享了python批量梯度下降算法的具体代码,供大家参考,具体内容如下 问题: 将拥有两个自变量的二阶函数绘制到空间坐标系中,并通过批量梯度下降算法找到并绘制其极值点 大体思路: 首先,根据题意确定目标函数:f(w1,w2) = w1^2 + w2^2 + 2 w1 w2 + 500 然后,针对w1,w2分别求偏导,编写主方法求极值点 而后,创建三维坐标系绘制函数图像以及其极值点即可 具体代码实现以及成像结果如下: import numpy as np import matplot

  • python基于三阶贝塞尔曲线的数据平滑算法

    前言 很多文章在谈及曲线平滑的时候,习惯使用拟合的概念,我认为这是不恰当的.平滑后的曲线,一定经过原始的数据点,而拟合曲线,则不一定要经过原始数据点. 一般而言,需要平滑的数据分为两种:时间序列的单值数据.时间序列的二维数据.对于前者,并非一定要用贝塞尔算法,仅用样条插值就可以轻松实现平滑:而对于后者,不管是 numpy 还是 scipy 提供的那些插值算法,就都不适用了. 本文基于三阶贝塞尔曲线,实现了时间序列的单值数据和时间序列的二维数据的平滑算法,可满足大多数的平滑需求. 贝塞尔曲线 关于

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

    前言 有一个充满水的8品脱的水壶和两个空水壶(容积分别是5品脱和3品脱).通过将水壶完全倒满水和将水壶的水完全倒空这两种方式,在其中的一个水壶中得到4品脱的水. 一.算法思想 算法分析 采用的算法思想是将某个时刻水壶中水的数量看作一个状态,用一个长度为3的数组表示. 初始状态便为[8,0,0],再拓展他的下一结点的可能结构. 若下一结点的结构已经被拓展过了便放弃,若没有拓展过则加入拓展列表(open_list)中.然后递归上述操作. 直到拓展列表(open_list)为空或者找到目标为止. 思想

  • Python中三种花式打印的示例详解

    目录 1. 引言 2. 打印圣诞树 2.1 问题描述 2.2 问题分析 3. 打印字母版圣诞树 3.1 问题描述 3.2 问题分析 4. 打印字母版菱形 4.1 问题描述 4.2 问题分析 5. 总结 1. 引言 在Python中有很多好玩的花式打印,对厉害的高手来说可能是小菜一碟,对入门的小白来说往往让人望而退步,我们今天就来挑战下面三个常见的花式打印吧... 2. 打印圣诞树 2.1 问题描述 编码实现函数christmas_tree(height),该函数输入参数为一个整数表示圣诞树的高度

  • python计算机视觉opencv卡号识别示例详解

    目录 一.模板预处理 1.将模板设置为二值图 2.检测模板的轮廓 3.对模板轮廓排序,并将数字和轮廓一一对应,以字典存储 4.备注 二.图片预处理 1.初始化卷积核 2.图片预处理第一部分 3.图像预处理第二部分 三.轮廓处理 1.大轮廓过滤 2.小轮廓分割 模板图片如下: 需识别的图片如下: 一.模板预处理 1.将模板设置为二值图 2.检测模板的轮廓 3.对模板轮廓排序,并将数字和轮廓一一对应,以字典存储 排序的函数如下: 排序并存储: 4.备注 ①每一个数字对应的是二值图截出来的那个数字图的

  • python编程开发时间序列calendar模块示例详解

    目录 calendar模块 设置每周第一天-setfirstweekday 1.默认情况:礼拜一是第一天 2.设置任意一天 是否闰年-isleap 年份间的闰年数-leapdays(y1, y2) 星期几-weekday(year, month, day) monthrange(year, month) 月的日历矩阵-monthcalendar(year, month) 月的日历-prmonth(year, month, w, l) 年的日历-calendar.calendar(year) 格式

  • Python matplotlib实现图表主题变换示例详解

    目录 一.更换主题样式 二.线条变换 三.将图表保存成本地图片 四.添加辅助线 五.调整画图的大小和清晰度 六.使用动漫风格 七.横坐标的倾斜度 八.横纵坐标轴转换 有时候因为jupyter notebook本身的主题不同,导致画图的时候与图表的颜色冲突,看不清坐标轴,这时候可以通过更换坐标轴风格来解决: 一.更换主题样式 plt.style.available ## 主题如下: ['Solarize_Light2', '_classic_test_patch', 'bmh', 'classic

  • Python实现日志实时监测的示例详解

    目录 介绍 观察者模式类图 观察者模式示例 1.创建订阅者类 2.创建发布者类 3.应用客户端-Map_server_client.py 4.测试 介绍 观察者模式:是一种行为型设计模式.主要关注的是对象的责任,允许你定义一种订阅机制,可在对象事件发生时通知多个"观察"该对象的其他对象.用来处理对象之间彼此交互. 观察者模式也叫发布-订阅模式,定义了对象之间一对多依赖,当一个对象改变状态时,这个对象的所有依赖者都会收到通知并按照自己的方式进行更新. 观察者设计模式是最简单的行为模式之一

  • Python实现为图片添加水印的示例详解

    目录 1.引言 2.filestools介绍 2.1 安装 2.2 filestools 功能介绍 2.3 watermarker模块介绍 2.4 代码实例 补充 1.引言 小屌丝:鱼哥,这个周末过得咋样 小鱼:酸爽~ ~ 小屌丝:额~~ 我能想到的,是这样吗? 小鱼:有多远你走多远. 小屌丝:唉,鱼哥,你别说,我觉得这个图片,跟你平时的表情挺贴切的. 小鱼:你想咋的!!!! 小屌丝:突然想到,能不能给你来一个专属的图片,例如追加水印啥的,让别人无图可盗!! 小鱼:嘿~ 你别说,还真的可以哈,

  • Python+Matplotlib绘制3D图像的示例详解

    目录 1. 绘制3D柱状图 2. 绘制3D曲面图 示例1 示例2 3.绘制3D散点图 4. 绘制3D曲线图 1. 绘制3D柱状图 绘制3D柱状图使用的是axes3d.bar()方法. 可能跟我们中学学的有一点不同的是,其语法如下: bar(left, height, zs=0, zdir=‘z’, *args, **kwargs) 其中left表示指向侧边的轴,zs表示指向我们的方向的轴,height即表示高度的轴.这三者都需要是一维的序列对象.在调用相关方法的时候,比如设置轴标签,还有一点需要

  • 详解Python中生成随机数据的示例详解

    目录 随机性有多随机 加密安全性 PRNG random 模块 数组 numpy.random 相关数据的生成 random模块与NumPy对照表 CSPRNG 尽可能随机 os.urandom() secrets 最佳保存方式 UUID 工程随机性的比较 在日常工作编程中存在着各种随机事件,同样在编程中生成随机数字的时候也是一样,随机有多随机呢?在涉及信息安全的情况下,它是最重要的问题之一.每当在 Python 中生成随机数据.字符串或数字时,最好至少大致了解这些数据是如何生成的. 用于在 P

  • Python+FuzzyWuzzy实现模糊匹配的示例详解

    目录 1. 前言 2. FuzzyWuzzy库介绍 2.1 fuzz模块 2.2 process模块 3. 实战应用 3.1 公司名称字段模糊匹配 3.2 省份字段模糊匹配 4. 全部函数代码 在日常开发工作中,经常会遇到这样的一个问题:要对数据中的某个字段进行匹配,但这个字段有可能会有微小的差异.比如同样是招聘岗位的数据,里面省份一栏有的写“广西”,有的写“广西壮族自治区”,甚至还有写“广西省”……为此不得不增加许多代码来处理这些情况. 今天跟大家分享FuzzyWuzzy一个简单易用的模糊字符

随机推荐