三個水桶等分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 個步驟。

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


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

更多相關文章
  • 0 簡單工廠模式 0.0 簡單工廠模式動機 考慮一個簡單的軟體應用場景,一個軟體系統可提供多個外觀不同按鈕(如圓形、矩形按、菱形按鈕等), 這些按鈕都源自同一個父類,不過在繼承父類後不同的子類修改了部分屬性從而使得它們可呈現不同外觀,如果希望在使用這些按鈕時,不需要知道這些具體按鈕類的名字,只需要知 ...
  • 要想理解持續集成和持續部署,先要瞭解它的部分組成,以及各個組成部分之間的關係。下麵這張圖是我見過的最簡潔、清晰的持續部署和集成的關係圖。 "圖片來源" 持續部署: 如圖所示,開發的流程是這樣的: 程式員從源碼庫(Source Control)中下載源代碼,編寫程式,完成後提交代碼到源碼庫,持續集成( ...
  • 本解決方案是一個Windows應用編程框架和UI庫,包括四個項目: Ligg.EasyWinForm是一個Winform應用編程框架和UI庫。通過這個該框架,不需任何代碼,通過XML配置文件,搭建任意複雜的Windows應用界面,以類似Execel公式的方式實現基本的過程式控制制(賦值、條件判斷、迴圈、 ...
  • (手機橫屏看源碼更方便) 註:java源碼分析部分如無特殊說明均基於 java8 版本。 註:本文基於ForkJoinPool分治線程池類。 簡介 隨著在硬體上多核處理器的發展和廣泛使用,併發編程成為程式員必須掌握的一門技術,在面試中也經常考查面試者併發相關的知識。 今天,我們就來看一道面試題: 如 ...
  • 題目: 鏈接:https://www.nowcoder.com/questionTerminal/6736cc3ffd1444a4a0057dee89be789b?orderByHotValue來源:牛客網牛牛舉辦了一次編程比賽,參加比賽的有3*n個選手,每個選手都有一個水平值a_i.現在要將這些選 ...
  • 1 先談Finalize() finalize()能做的所有工作,使用try-finally或者其他方式都可以做得更好、更及時,所以筆者建議大家完全可以忘掉Java語言中有這個方法的存在。 ——《深入理解JVM》 finalize()方法確實可以實現一次對象的自救,但是其不確定性和昂貴的運行代價都表 ...
  • 通過前面2篇文章我們搭建了SW的基礎環境,監控了微服務,能瞭解所有服務的運行情況。但是當出現服務響應慢,介面耗時嚴重時我們需要立即定位到問題,這就需要我們今天的主角 監控告警,同時此篇也是SW系列的最後一篇。 UI參數 首先我們認識一下SW DashBoard上的幾個關鍵參數,如下圖所示 告警配置 ...
  • 一.docker簡介 1、docker定義:docker是一個用來裝應用的容器,就像杯子可以裝水,筆筒可以裝筆,書包可以放書一樣。你可以把“Hello World!”放到docker中,也可以把網站放到docker中,你可以把任何你想到的程式放到docker中。 2、docker思想: (1)集裝箱 ...
一周排行
  • C#中的DefaultView方法 簡介: 首先可建立一個表,對錶進行填充若幹條數據,代碼如下: //創建Table1 DataTable dt = new DataTable(); //對Table1添加列名,並設置列值類型 DataTable dt1 = new DataTable();//創建 ...
  • 1、運行程式報錯: FailFast: Couldn't find a valid ICU package installed on the system. 解決方法: yum install icu -y 2、程式運行後,本地可以訪問,但其他機器無法訪問,需要開放埠 firewall-cmd - ...
  • 只是一個Demo,所用有很多功能也沒有添加進去如分頁,輸入驗證,頁面也沒有進行精心佈局。 整體先來幾張圖解 ...
  • Core提供二種開發模式:Core Pages和Core MVC,今天介紹的是Core MVC。 1、創建web MVC項目 新建service/h_r.baseservice類庫文件、data/h_r.efdata類庫文件、common/h_r.common類庫文件。 引入需要的CSS文件和JS文 ...
  • 學習網址:https://docs.microsoft.com/zh-cn/visualstudio/get-started/visual-studio-ide?view=vs-2019 示範 vs2019: 變數的重命名的重構,更改該變數命名的同時,引用該變數的地方也會更改,如果該變數有被反射用到 ...
  • 1、在data裡面新建個Entity文件用於存放表映射,設計資料庫,執行如下語句 Scaffold-DbContext -Force "server=.;user=sunyong;password=1qaz!QAZ;database=hr;" Microsoft.EntityFrameworkCor ...
  • 1、發送郵件類,百度一大堆,這裡用的也是直接百度拿過來的 public static bool get_send_email(email email, string Title, string Body) { MailMessage mailMsg = new MailMessage(); mail ...
  • 1、添加用戶列表控制器,用於用戶列表顯示,登錄,增刪改查,郵件發送,下載 public userlistController(MainDbContext _db, ILogger<operatorlog> _logger, IOptions<email> sendMail) { db = _db; ...
  • 1、用戶列表頁面 @{ Layout = Layout = null;}<table id="datalistuser" class="easyui-datagrid" url="/userlist/getuserlist" toolbar="#toolbaruser" rownumbers="tr ...
  • 1、引用包 Microsoft.EntityFrameworkCore.Tools Microsoft.EntityFrameworkCore.SqlServer Microsoft.AspNetCore.Mvc.Razor.RuntimeCompilation Microsoft.AspNetCo ...