如何用Python编写示例详解三壶分水谜题？

本文共计1113个文字，预计阅读时间需要5分钟。

前言：有一种充满创意的实验，只需一个装满水的8品脱水壶和两个空水壶（容量分别为5品脱和3品脱），通过将水壶完全倒满和倒空，可以在其中一个水壶中得到4品脱的水。

一、算法：通过以下步骤进行实验：

1. 将8品脱水壶完全倒满水。

2.将8品脱水壶中的水倒入5品脱水壶，直到5品脱水壶满。

3.将5品脱水壶中的水倒掉，然后将8品脱水壶中剩余的水倒入5品脱水壶。

4.再次将8品脱水壶完全倒满水。

5.将8品脱水壶中的水倒入5品脱水壶，直到5品脱水壶满。

6.将5品脱水壶中的水倒掉，然后将8品脱水壶中剩余的水倒入5品脱水壶。

7.此时，5品脱水壶中有4品脱的水。

前言

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

一、算法思想

算法分析

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

思想图解

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

就如同上图一样，使用层次遍历一次一次递归扩展新的结点，知道找到4品脱的水或者无结点可扩展为止（类似于广度优先遍历）。