最近有看到一道算法題，題雖簡單，但網(wǎng)上給出的解釋大都不太完善，甚至還有一言不合直接貼代碼的，今天正好有時(shí)間，就寫一下自己對(duì)這道問題的理解。題目如下：

Snipaste_2019-08-09_16-38-27.png

這類問題會(huì)給你兩個(gè)或三個(gè)沒有刻度的杯子，讓你倒出指定容量的水。問法一般有兩種：能不能倒出指定容量的水|最少倒幾次能倒出指定容量的水

注意，這兩種問法的處理方式是不同的。

能否倒出指定容量的水

這里問的是能否導(dǎo)出，所以我們不需要知道具體的步驟，只用弄懂該問題是否有解。

要倒出4品脫的水，也就是說8品脫壺要有4品脫水，剩下兩個(gè)空壺共享4品脫水，這里就成了一個(gè)函數(shù)問題：5x + 3y = 4有沒有整數(shù)解（包括正和負(fù)）。根據(jù)裴蜀定理（對(duì)于給定的正整數(shù)a，b，方程ax + by = c有解的充要條件為c是gcd(a,b)的整數(shù)倍），本題轉(zhuǎn)化成了求解最大公約數(shù)問題，可以用歐幾里得算法，連續(xù)整數(shù)檢測算法，以及中學(xué)時(shí)代的算法（質(zhì)因數(shù)）求解。

最少倒幾次能倒出指定容量的水

毫無疑問，遇到這種求最少又不復(fù)雜的問題，可以考慮廣度優(yōu)先算法。

初始狀態(tài)是[8,0,0]，做一次倒水之后的情況有[3,5,0]，[5,0,3]。照著這個(gè)思路一步步走下去，即可找出最優(yōu)解。掛一張盜來的圖：

Snipaste_2019-08-09_18-13-00.png

Lua實(shí)現(xiàn)如下：

local tBeginWater = {8, 0, 0}
local tCups = {8, 3, 5}
local nResultWater = 4
local tQueue = {tBeginWater}  --lua沒有隊(duì)列容器，這里用table模擬

function CheckFinished()
    for k,v in ipairs(tQueue[1]) do
        if v == nResultWater then
            return true
        end
    end
end

function CheckSameWater(tWater)
    local tPreWater = tWater.tPreWater
    local nSameValueCount
    while tPreWater do
        nSameValueCount = 0
        for k,v in ipairs(tPreWater) do
            if v ~= tWater[k] then
                break
            else
                nSameValueCount = nSameValueCount + 1
            end
        end

        if nSameValueCount == #tCups then
            return true
        else
            tPreWater = tPreWater.tPreWater
        end
    end

    return false
end

function PourWater(tCurWater)  --bfs
    for i=1,#tCups do
        if tCurWater[i] > 0 then
            for j=1, #tCups - 1 do
                local nCupId = i+j > #tCups and i+j-#tCups or i+j
                if tCups[nCupId] > tCurWater[nCupId] then
                    local nRemainCapacity = tCups[nCupId] - tCurWater[nCupId]
                    local nDumpWater = nRemainCapacity > tCurWater[i] and tCurWater[i] or nRemainCapacity
                    local tNextWater = clone(tCurWater)
                    tNextWater[i] = tNextWater[i] - nDumpWater
                    tNextWater[nCupId] = tNextWater[nCupId] + nDumpWater
                    tNextWater.tPreWater = tCurWater
                    if not CheckSameWater(tNextWater) then
                        table.insert(tQueue, tNextWater)
                    end
                end
            end
        end
    end
    table.remove(tQueue, 1)
end

while not CheckFinished() do
    local tCurWater = tQueue[1]
    PourWater(tCurWater)
end

clone實(shí)現(xiàn)：

function clone(object)
    local lookup_table = {}
    local function _copy(object)
        if type(object) ~= "table" then
            return object
        elseif lookup_table[object] then
            return lookup_table[object]
        end
        local newObject = {}
        lookup_table[object] = newObject
        for key, value in pairs(object) do
            newObject[_copy(key)] = _copy(value)
        end
        return setmetatable(newObject, getmetatable(object))
    end
    return _copy(object)
end

總結(jié)

可以先判斷是否能倒出，再用廣度優(yōu)先求出最小次數(shù)