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

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

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

总结

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