三個水桶等分8升水的問題 -《演算法的樂趣》

来源:https://www.cnblogs.com/it-3327/archive/2019/11/08/11823637.html

智力題目有三個容積分別為3升、5升、8升的水桶,其中容積為8升的水桶中裝滿了水,容積為3升和容積為5升的水桶都是空的。三個水桶都沒有刻度,現在需要將大水桶中的8升水等分成兩份,每份都是4升水,附加條件是只能這三個水桶,不能藉助其他輔助容器。“恩,是的,這是一個很經典的問題。”“然而,我們並不能想全, ...


智力題目

有三個容積分別為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)

運行結果

一共有 16 種倒水方法,方法如下:

...

(16種方法,貼上去太長了,大家在本地嘗試下,如需要源碼,請關註公眾號進行留言。)
小結

運行代碼之後,一共找到了 16 種倒水的方法,最快的方法需要 7 個步驟。

“怎麼樣,是不是沒想到會有這麼多方法吧,去考考你身邊的小伙伴吧。”


您的分享是我們最大的動力!

更多相關文章
  • 今天,在Anaconda prompt啟動python遇到瞭如下錯誤: UnicodeDecodeError: ‘gbk’ codec can’t decode byte 0xaf in position 553: illegal multibyte sequence 看了看出錯跟蹤,查看瞭如下位置 ...
  • 許多小伙伴對於java中的三種初始化塊的執行順序一直感到頭疼,接下來我們就來分析一下這三種初始化塊到底是怎麼運行的。有些公司也會將這個問題作為筆試題目。 下麵通過一段代碼來看看創建對象時這麼初始化塊是如何運行的 package com.hxy; public class CodeBlock{ pub ...
  • 字元串或串(String)是由數字、字母、下劃線組成的一串字元。一般記為 s=“a1a2···an”(n>=0)。它是編程語言中表示文本的數據類型。在程式設計中,字元串(string)為符號或數值的一個連續序列,如符號串(一串字元)或二進位數字串(一串二進位數字)。 String類型你一定不陌生,畢 ...
  • 我們知道,swoole中有兩大進程,分別是 master 主進程和 manager 管理進程。 其中 master 主進程中會有一個主 reactor 線程和多個 reactor 線程,主要的作用就是用來維護TCP連接,處理網路IO,收發數據。 而 manager 管理進程,作用則是 fork 和管 ...
  • 1. random模塊 導入的是random模塊,格式是: import random 1.1 隨機小數 取隨機小數 : 數學計算。 print(random.random()) # 取0-1之間的小數print(random.uniform(1,2)) # 取1-2之間的小數 1.2 隨機整數 取 ...
一周排行
x