DIV CSS 佈局教程網

用 JS 實現杯子倒水問題的自動求解
編輯:關於JavaScript     

智力測試題中經常出現這樣的邏輯題:給你幾個容量不等的杯子,要求倒出指定數量的水。安卓平台上甚至有一款專門玩這個題的遊戲,叫做 Water Logic。

我把這款遊戲的幾十個關卡通了一遍,整體感覺關卡設計還有改進空間:難度並非遞增,有些後面的關卡反而相當簡單,同時也缺乏真正高難度的挑戰。

對身為程式設計師的我們來說,這類題目大多不成問題——10 步以內可以輕鬆搞定,10 步以上也能完成,只是未必能以最少步數達成。

出於對三星滿足的執著,我寫了一個自動求解的小程式,從此這類問題再也難不倒我了。

演算法基本邏輯

每個杯子都有「倒滿」、「倒空」、「倒入其他杯子」三種操作,因此總操作數為:杯子數 ×(杯子數 - 1 + 2)。

以 3 個杯子為例,每一步可選的操作有 12 種;若為 2 個杯子,則每步有 6 種可選操作。

求解時遍歷每一種操作,記錄操作完成後各杯子內的水量,並以水量計算出一個 key 來建立 map。在遍歷各種倒水操作的過程中,如果某個 key 已經存在,且當前步數大於先前記錄的步數,則捨棄該操作,以此保證得到最少步數。

值得一提的是,這個小程式目前只能解決 2 個或 3 個杯子的倒水問題,尚未寫成支援 N 個杯子的通用版本,代碼中存在不少 hard code。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved