大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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 的最大公约数有关,欧几里德算法在这里是否有用。 ( 并且上面给出的文章链接也介绍了二元一次不定方程的方法,二元一次不定方程的结果就是这两个数的最大公约数的倍数 )
数学功底太浅,只能想到这些问题并且都没办法证明。暂时把问题记在这里,待学习一段时间再回头来看。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/184746.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...