三壶问题（水杯倒水问题）

最近有看到一道算法题，题虽简单，但网上给出的解释大都不太完善，甚至还有一言不合直接贴代码的，今天正好有时间，就写一下自己对这道问题的理解。题目如下：

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

这类问题会给你两个或三个没有刻度的杯子，让你倒出指定容量的水。问法一般有两种：能不能倒出指定容量的水|最少倒几次能倒出指定容量的水

注意，这两种问法的处理方式是不同的。

能否倒出指定容量的水

这里问的是能否导出，所以我们不需要知道具体的步骤，只用弄懂该问题是否有解。

要倒出4品脱的水，也就是说8品脱壶要有4品脱水，剩下两个空壶共享4品脱水，这里就成了一个函数问题：5x + 3y = 4有没有整数解（包括正和负）。根据裴蜀定理（对于给定的正整数a，b，方程ax + by = c有解的充要条件为c是gcd(a,b)的整数倍），本题转化成了求解最大公约数问题，可以用欧几里得算法，连续整数检测算法，以及中学时代的算法（质因数）求解。

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

毫无疑问，遇到这种求最少又不复杂的问题，可以考虑广度优先算法。

初始状态是[8,0,0]，做一次倒水之后的情况有[3,5,0]，[5,0,3]。照着这个思路一步步走下去，即可找出最优解。挂一张盗来的图：

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

Lua实现如下：

local tBeginWater = {8, 0, 0}
local tCups = {8, 3, 5}
local nResultWater = 4
local tQueue = {tBeginWater}  --lua没有队列容器，这里用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实现：

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

总结

可以先判断是否能倒出，再用广度优先求出最小次数

最后编辑于：2020.08.29 11:57:01