大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
JOJ 1200 Jugs 题目链接： http://acm.jlu.edu.cn/joj/showproblem.php?pid=1200
题目的意思是，有两个容器，容量分别为 ca 和 cb ， ca < cb ，初始时两个容器都是空的，水无限量供应，问如何用这两个容器量出 n 单位的水放在容量为 cb 的那个容器中？
这个题目给出的数据是保证有解的，而且看到这个题目的人都会想到用搜索来解决这个题目。搜索也很简单，最容易想到的自然是广度搜索，直觉上这个问题和汉诺塔问题很像，也可能用类似汉诺塔那样的算法。在搜索时状态就是当前两个容量的水量 wa 和 wb ，如果 wb 不等于 n ，则执行所允许的六种操作： fill a, fill b, empty a, empty b, pour a b, pour b a 。这个题目 AC 的代码正是用的广度搜索。
现在作为一个有趣的数学问题来看，分析一下它有什么性质。这个问题是有名的泊松分酒问题。在网上有一篇文章对此类问题作了深入分析，这篇文章是：
http://blog.sina.com.cn/s/blog_41482c9f0100cts1.html
但那些问题与这个题目的情境略微不同。对于这个题目，自己有以下几个问题非常想弄明白：
1. fill 和 empty 操作是填满或者清空容器， pour 操作是把一个容器的水倒入另一个直到另一个满或这个容器空。所以，很显然，任何时候，两个容器或者一个为空，或者一个为满。
2. 这个问题在什么情况下必定有解，在什么情况下必定无解。 n > cb 时必定无解，有没有一个值 n0 使得 n < n0 时也必定无解？
3. 如果能够量出 k 单位的水，是否也一定能够量出 mk 单位的水，其中 m 是正整数并且 mk <= cb 。
4. 直觉上这个题目和两个容量 ca, cb 的最大公约数有关，欧几里德算法在这里是否有用。 ( 并且上面给出的文章链接也介绍了二元一次不定方程的方法，二元一次不定方程的结果就是这两个数的最大公约数的倍数 )
数学功底太浅，只能想到这些问题并且都没办法证明。暂时把问题记在这里，待学习一段时间再回头来看。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/184746.html原文链接：https://javaforall.net
