b*********8
发帖数: 985 | 1 把15升改成9升
有两个杯子， 一个是17升，一个是13升， 都没有刻度，
用这两个得出准确的9升水， 最少要多少步？ | b*********8
发帖数: 985 | 2 这道题，原来是骗人的。此题华山一条道，同样的步骤往下走就一定能走到，没有任何
分支和花俏。第一段6步，从第二段起7步一个循环。4段后循环结束。要是问你如何得
到9升水，你得走到最后一步。这的确是幼儿园，甚至大猩猩也能做出来的，因为所有
的都是机械动作。它只要知道大杯装满倒小杯，倒满小杯后小杯倒掉，然后大杯剩下的
倒 小杯，然后大杯装满再往小杯倒至满。你需要的数在每个循环开头检测一下。1~16
升在循环中都会各出现一次只是顺序不一样而已。这道题是“遍历”题。 | n******t
发帖数: 4406 | 3 其實最少最多沒實際意義，他這個東西只有一個寄存器。
【在 b*********8 的大作中提到】
: 把15升改成9升
: 有两个杯子， 一个是17升，一个是13升， 都没有刻度，
: 用这两个得出准确的9升水， 最少要多少步？
| l*******m
发帖数: 1096 | 4 这道题有意思是改变两个杯子的容积，还能找到解吗？比如一个10, 另一个6, 似乎最
小的粒度只要2. 如果一个10, 另一个5, 粒度是5. 原题两个质数，粒度是1. 基本就是
最大公约数。最大公约数是可以写成recursion，但这个题还不一样，可以看成操作有
限制的算法。
16
【在 b*********8 的大作中提到】
: 这道题，原来是骗人的。此题华山一条道，同样的步骤往下走就一定能走到，没有任何
: 分支和花俏。第一段6步，从第二段起7步一个循环。4段后循环结束。要是问你如何得
: 到9升水，你得走到最后一步。这的确是幼儿园，甚至大猩猩也能做出来的，因为所有
: 的都是机械动作。它只要知道大杯装满倒小杯，倒满小杯后小杯倒掉，然后大杯剩下的
: 倒 小杯，然后大杯装满再往小杯倒至满。你需要的数在每个循环开头检测一下。1~16
: 升在循环中都会各出现一次只是顺序不一样而已。这道题是“遍历”题。
| p***o
发帖数: 1252 | 5 这都是最基本的数论问题，Bezout's identity。
算法课或者RSA老师没偷懒的话，extended Euclidean algorithm也该知道。
【在 l*******m 的大作中提到】
: 这道题有意思是改变两个杯子的容积，还能找到解吗？比如一个10, 另一个6, 似乎最
: 小的粒度只要2. 如果一个10, 另一个5, 粒度是5. 原题两个质数，粒度是1. 基本就是
: 最大公约数。最大公约数是可以写成recursion，但这个题还不一样，可以看成操作有
: 限制的算法。
:
: 16
| h**********c
发帖数: 4120 | 6 我不太清楚这个题目的是什么，
既然你来计算机系踢馆，
就是觉得很象chinese remainder theorem
然后这个线性系统的rank是1
大叔局可以开始梦特卡漏了
说者无心听者有意，都是来白话的。 | o**o
发帖数: 3964 | | b*********8
发帖数: 985 | 8 如何两步？说来听听。
【在 o**o 的大作中提到】
: 两步不行吗？不知道你们在说什么
| o**o
发帖数: 3964 | 9 13升装满全倒进17升，再打满一个13升倒4升进17升。剩下是不是9升？ 是我智障了吗
OMG
【在 b*********8 的大作中提到】
: 如何两步？说来听听。
| l**********0
发帖数: 150 | 10 写了一个通解的，栗子如下：
bottle1 size: 17, bottle2 size: 13, target: 9
fill bottle2(0,13)
pour water from bottle2 to bottle1(13,0)
fill bottle2(13,13)
pour water from bottle2 to bottle1(17,9)
bottle1 size: 17, bottle2 size: 13, target: 15
fill bottle1(17,0)
pour water from bottle1 to bottle2(4,13)
dump bottle2(4,0)
pour water from bottle1 to bottle2(0,4)
fill bottle1(17,4)
pour water from bottle1 to bottle2(8,13)
dump bottle2(8,0)
pour water from bottle1 to bottle2(0,8)
fill bottle1(17,8)
pour water from bottle1 to bottle2(12,13)
dump bottle2(12,0)
pour water from bottle1 to bottle2(0,12)
fill bottle1(17,12)
pour water from bottle1 to bottle2(16,13)
dump bottle2(16,0)
pour water from bottle1 to bottle2(3,13)
dump bottle2(3,0)
pour water from bottle1 to bottle2(0,3)
fill bottle1(17,3)
pour water from bottle1 to bottle2(7,13)
dump bottle2(7,0)
pour water from bottle1 to bottle2(0,7)
fill bottle1(17,7)
pour water from bottle1 to bottle2(11,13)
dump bottle2(11,0)
pour water from bottle1 to bottle2(0,11)
fill bottle1(17,11)
pour water from bottle1 to bottle2(15,13) | b*********8
发帖数: 985 | 11 你是对的，是我忽视掉了，所以多跑了一圈。第二步就能得到9升。其实是个对称的数
组。15升是需要最多步的。
吗
【在 o**o 的大作中提到】
: 13升装满全倒进17升，再打满一个13升倒4升进17升。剩下是不是9升？ 是我智障了吗
: OMG
| b*********8
发帖数: 985 | 12 谢谢正确答案。
15升确实是需要最多步。
【在 l**********0 的大作中提到】
: 写了一个通解的，栗子如下：
: bottle1 size: 17, bottle2 size: 13, target: 9
: fill bottle2(0,13)
: pour water from bottle2 to bottle1(13,0)
: fill bottle2(13,13)
: pour water from bottle2 to bottle1(17,9)
: bottle1 size: 17, bottle2 size: 13, target: 15
: fill bottle1(17,0)
: pour water from bottle1 to bottle2(4,13)
: dump bottle2(4,0)
| o**o
发帖数: 3964 | 13 从前人说搬砖，我以为那是自谦
这次说幼儿园，不敢想象了…… | e********2
发帖数: 495 | 14 leetcode题目，还讨论？
https://leetcode.com/problems/water-and-jug-problem/
【在 b*********8 的大作中提到】
: 把15升改成9升
: 有两个杯子， 一个是17升，一个是13升， 都没有刻度，
: 用这两个得出准确的9升水， 最少要多少步？
| b*********8
发帖数: 985 | 15 不是学计算机的，见笑了。
【在 e********2 的大作中提到】
: leetcode题目，还讨论？
: https://leetcode.com/problems/water-and-jug-problem/
|
|
