求水杯问题的终极解答！

mathematica

我需要一般的，比较透彻的、简单的回答！！！！！！！！！！！！！！！

mathematica

hujunhua,你能解决吗？？？？？？？？？？？？？？

litaoye

我感觉3个杯子的话，还是交给计算机思考比较好，先求一下gcd，看是否有解，再广搜一下，记录个状态Hash，状态不会太多。

hujunhua

litaoye说得有道理。为了得到最短的到达路径，状态演进遵循最短路径原则，按此原则作出的演进图如下：

共是25个状态, 幸运的是包括（6,6,0），到达(6,6,0)的最短路径长度为7，20#给出的并不是最短路径。

按照最短路径原则生成的演进图不包括那些迂回的路径。作图时各条分枝是同步生长的，向下、斜向下或者水平的箭头都被“最短路径原则”滤掉了。
所以2楼的那条迂回路径在10#的演进图上是看不到的。那条路径是从第2条（从左到右）支路的顶端(11,1,0)横向第1支路的顶端(6,1,5)，然后向下走一步。

hujunhua

一条可行的路径可以由解不定方程 12+8x+5y=6 得到。 这个方程的意思是B12只用B8和B5定量出入，从而得到6.
方程的一种解是（-2，2），表示要从B12中倒出两杯B8, 倒入两杯B5. 这刚好是演进树中的最短路径。

litaoye

口算的，可能不是最优的，利用好8-11这一段，这部分等价于有一个无限大的空杯子。

8 8 0 -> 0 0 0 0
8 5 3 -> 0 0 0 0
8 5 0 -> 3 0 0 0
8 2 3 -> 3 0 0 0
8 0 3 -> 3 2 0 0
8 3 0 -> 3 2 0 0
5 3 3 -> 3 2 0 0
5 6 0 -> 3 2 0 0
2 6 3 -> 3 2 0 0
2 8 1 ->  3 2 0 0
2 8 0 -> 3 2 1 0
0 8 2 -> 3 2 1 0
0 7 3 -> 3 2 1 0
3 7 0 -> 3 2 1 0
3 4 3 -> 3 2 1 0
6 4 0 -> 3 2 1 0
6 1 3 -> 3 2 1 0
6 0 3 -> 3 2 1 1
8 0 1 -> 3 2 1 1
8 0 0 -> 4 2 1 1
5 0 3 -> 4 2 1 1
5 0 0 -> 4 2 4 1
2 0 3 -> 4 2 4 1
2 0 0 -> 4 2 4 4
0 0 0 -> 4 4 4 4

hujunhua

可以用Mathematica解出所有的状态Hash:

1. {x,y,z}/.Solve[x+y+z==12&&yz(8-y)(5-z)==0&&0<=x<=12&&0<=y<=8&&0<=z<=5,{x,y,z},Integers]

复制代码

输出：

1. {{0,7,5},{0,8,4},{1,6,5},{1,8,3},{2,5,5},{2,8,2},{3,4,5},{3,8,1},{4,3,5},{5,2,5}, {5,7,0},{6,1,5},{6,6,0},{7,5,0},{8,0,4},{8,4,0},{9,0,3},{9,3,0},{10,0,2}, {10,2, 0},{11,0,1}, {11,1,0},{4,8,0},{7,0, 5},{12,0,0}}

复制代码

刚好25个。

hujunhua

26# litaoye 是最短路径。其中082-3210可以替换为253-3210，603-3211可以替换为811-3210，所以共是4条最短路径。

演进图不是树。

平常心

口算的，可能不是最优的，利用好8-11这一段，这部分等价于有一个无限大的空杯子。
5 3 3 -> 3 2 ...
litaoye 发表于 2012-8-30 02:35

很好的方法，学习了。
只是我不理解“利用好8-11这一段，这部分等价于有一个无限大的空杯子”的意思。
原题已经明确“把酒平均的分给4个人喝”，这隐含了一个重要条件——4个人相等于4个4两的酒杯，这4个杯子只能倒进而不能倒出。因此不需要“无限大的空杯子”这个假设。

mathtime

这个问题最终可以对应于一个简单的数学运算,我想这是你想看到的结果。曾经在实际中遇到类似的问题，冥思苦想最后发现只是一个求余等简单的运算。对于现在的问题我也人为是这样的，但我现在一时看不出，毕竟像欧拉、费马那样的人不多。