三个水桶等分8升水的问题 -《算法的乐趣》

智力题目
有三个容积分别为3升、5升、8升的水桶,其中容积为8升的水桶中装满了水,容积为3升和容积为5升的水桶都是空的。三个水桶都没有刻度,现在需要将大水桶中的8升水等分成两份,每份都是4升水,附加条件是只能这三个水桶,不能借助其他辅助容器。

“恩,是的,这是一个很经典的问题。”

“然而,我们并不能想全,不信请继续往下看。”

答案
”废话不多说,直接看方法吧。“

第一种(7步)
将8L的水桶中的水,倒满5L的水桶,这时:8L水桶为3L、5L水桶为5L、3L水桶为0L

将5L的水桶中的水,倒满3L的水桶,这时:8L水桶为3L、5L水桶为2L、3L水桶为3L

将3L的水桶中的水,倒入8L的水桶,这时:8L水桶为6L、5L水桶为2L、3L水桶为0L

将5L的水桶中的水,倒入3L的水桶,这时:8L水桶为6L、5L水桶为0L、3L水桶为2L

将8L的水桶中的水,倒入5L的水桶,这时:8L水桶为1L、5L水桶为5L、3L水桶为2L

将5L的水桶中的水,倒满3L的水桶,这时:8L水桶为1L、5L水桶为4L、3L水桶为3L

将3L的水桶中的水,倒入8L的水桶,这时:8L水桶为4L、5L水桶为4L、3L水桶为0L

第二种(8步)
将8L的水桶中的水,倒满3L的水桶,这时:8L水桶为5L、5L水桶为0L、3L水桶为3L

将3L的水桶中的水,倒入5L的水桶,这时:8L水桶为5L、5L水桶为3L、3L水桶为0L

将8L的水桶中的水,倒满3L的水桶,这时:8L水桶为2L、5L水桶为3L、3L水桶为3L

将3L的水桶中的水,倒满5L的水桶,这时:8L水桶为2L、5L水桶为5L、3L水桶为1L

将5L的水桶中的水,倒入8L的水桶,这时:8L水桶为7L、5L水桶为0L、3L水桶为1L

将3L的水桶中的水,倒入5L的水桶,这时:8L水桶为7L、5L水桶为1L、3L水桶为0L

将8L的水桶中的水,倒满3L的水桶,这时:8L水桶为4L、5L水桶为1L、3L水桶为3L

将3L的水桶中的水,倒入5L的水桶,这时:8L水桶为4L、5L水桶为4L、3L水桶为0L

我相信答案肯定不止两个,到底有多少种答案?

带着这个疑问,我们来设计一个算法吧。

问题分析
人的思维
解决这个问题的关键是怎么通过倒水凑出确定的1升水或能容纳1升水的空间。

例如,当8L水桶或5L水桶或3L水桶有1L水时,都能快速倒出4L水。

计算机思维
“穷举法”

水桶初始状态:8L水桶装满水,3L和5L的水桶为空。
水桶最终状态:3L水桶为空,5L和8L的水桶各4L水。

假设将每个状态下三个水桶中的水的体积作为status。

从 $status = array(8,0,0) 得到 $status = array(4,4,0)。

当然还会有一些限制:

1.各个水桶的都有最大值:

0 <= status[0] <= 8;

0 <= status[1] <= 5;

0 <= status[2] <= 3;

2.当前倒水之后各个水桶的状态,与历史倒水之后各个水桶的状态,不能相同。

3.当前水桶为空时,不能倒给其他水桶。

4.当前水桶为最大容积时,其他水桶不能再向这个水桶倒水。

程序代码(PHP)

PHP源码

运行结果
一共有 16 种倒水方法,方法如下:

...

(16种方法,贴上去太长了,大家在本地尝试下,如需要源码,请关注公众号进行留言。)

小结
运行代码之后,一共找到了 16 种倒水的方法,最快的方法需要 7 个步骤。

“怎么样,是不是没想到会有这么多方法吧,去考考你身边的小伙伴吧。”

原创: 訢亮

微信公众号:訢亮先森

原文地址

php算法

我来吐槽

*

*

已有 14 条评论

  1. shansan

    霍,太强了

  2. 清秋的沙海

    有点意思,我也想写一个

  3. 心语难诉

    看到算法就头痛,看来只能一辈子搬砖了!

    1. Hoe

      我看到算法也头痛

  4. 马也随笔

    虽然很复杂,还是过来点赞下!

  5. 张波博客

    图片不可看了,编程很好算出来

  6. nice

    选择狗带😂

    1. Hoe

      🚗我也选择狗带

  7. 戏子

    图片防盗链了。

    1. Hoe

      😂感谢提醒!