※ 引述《Akerker (阿克克(*〞︶〝)/)》之铭言： : 推 hirabbitt:11、17、20、22、23、24 这串数字怎麽来的 试误? 07/25 17:24 这有个非常有系统的试误法。 想像每一罐都拿出大约一亿颗豆子，一看重量马上就知道几罐有问题， 因为一亿实在太多了。例如有两罐有问题，那大概就是两亿。接着如果每罐 拿出的数量差一点点，我们只要看跟两亿差多少逆推哪两罐坏掉就好。简单 来说，我们假设可以拿出足够多的豆子，先判断有几罐坏掉。 就先假设拿出最多颗豆子的罐子拿了 X 颗吧，我们先算出一个 X 够大 时的可行方案，再逆推在那个方案下 X 至少要多少才能「先判断坏几罐」。 所有罐子拿出来的豆子就以 X - a_i 表示。由大到小排列，第一罐就是 0 因为拿了 X - 0 颗豆子。1 代表拿了 X - 1 颗。以下从只有一罐开始列出 所有的重量组合。坏 N 罐後面有个数字 Y 代表数量 N*X - Y 可能会发生。 这罐要码有坏或是没坏，所以数量是 0 或 X - 0, 也就是 坏 0 罐： 0 (代表 0 = 0 * X - 0) 坏 1 罐： 0 (代表 X - 0 = 1 * X - 0) 第二罐加上去後不能让同一列之中有重复的数字，发现到数字 1 (代表 X - 1) 符合。也就是坏一罐时可能是 X - 0 或 X - 1, 坏两罐时 2X - 1. 坏 0 罐： 0 坏 1 罐： 0 1 坏 2 罐： 1 在前两罐不变的情况下，第三罐可以取的最小值是 2 坏 0 罐： 0 坏 1 罐： 0 1 2 坏 2 罐： 1 2 3 坏 3 罐： 3 再来是 4. 如果取 3 的话坏 2 罐时有两个 3. 坏 0 罐： 0 坏 1 罐： 0 1 2 4 坏 2 罐： 1 2 3 4 5 6 坏 3 罐： 3 5 6 7 坏 4 罐： 7 再来是 7 和 13 坏 0 罐： 0 坏 1 罐： 0 1 2 4 7 13 坏 2 罐： 1 2 3 4 5 6 7 8 9 11 13 14 15 17 20 坏 3 罐： 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 坏 4 罐： 7 10 12 13 14 16 18 19 20 21 22 23 24 25 26 坏 5 罐： 14 23 25 26 27 坏 6 罐： 27 现在来逆推这种方案下 X 至少要多大才不会让数字相撞。这边一个简单的 偷懒作法就是让数字的范围不会相撞就好啦。例如坏 3 罐最多有 3*X - 3 颗， 坏 4 罐最少有 4*X - 26 颗，只要让 X 比 26-3 大就好。基本上就是看头尾 取差： 坏 0 罐： 0 坏 1 罐： 0 1 2 4 7 13 坏 2 罐： 1 2 3 4 5 6 7 8 9 11 13 14 15 17 20 坏 3 罐： 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 坏 4 罐： 7 10 12 13 14 16 18 19 20 21 22 23 24 25 26 坏 5 罐： 14 23 25 26 27 坏 6 罐： 27 要比 13-0, 20-0, 24-1, 26-3, 27-7, 27-14 都还多... X 取 24 就可以 让所有数字范围分开啦。这六罐就是： 24-0=24, 24-1=23, 24-2=22, 24-4=20, 24-7=17, 24-13=11 （我没有写程式帮我算，难免过程有错，请大家不吝指正） 如果有 100 罐豆子，也不要写程式了，请看 OEIS A005255 和 A005318. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.39 ※ 编辑: Favonia 来自: 140.112.30.39 (07/27 21:56) lol 是不是我哪里没有写清楚... 我可以改。 ※ 编辑: Favonia 来自: 140.112.30.39 (07/28 21:07) ※ 编辑: Favonia 来自: 140.112.30.39 (07/29 20:41)