我试着利用eieio做法中的想法来做一般化的情形吧 若n颗要秤k次才能找出伪币且分出轻重 我们看第一次选的 这第一次秤的必然是两边一样多个 (否则得到的轻重没有意义) 设两边各r个 那麽 当这一次不等重时 可能范围缩小到2r种 这一次等重时 可能范围缩小到2n-4r种 而全部既然秤k次才能得到答案 2r和2n-4r都必须要≦3^(k-1) 为了要能平均分配 2r和2n-4r必须尽量接近 最好的情形是2r=2n-4r 这时r=n/3 也就是当n被3整除时可以得r=n/3 这时由2r≦3^(k-1) => 2n/3≦3^(k-1) => 2n≦3^k => n≦(3^k)/2 当n不被3整除时 分两种case: (1) n除以3余1：令m=(n-1)/3 此时n个硬币分成m m m+1三堆 称前两堆 那麽情形数就是2m 2m 2m+2 所以必须要有2m+2≦3^(k-1) => 2(n-1)/3+2≦3^(k-1) => 2(n-1)/3≦3^(k-1)-2 => 2(n-1)≦3^k - 6 => n-1≦(3^k)/2 - 3 => n≦(3^k)/2 - 2 (2) n除以3余2: 令m=(n-2)/3 这情形中分成m m+1 m+1三堆 称後两堆 和(1)一样的情形 可以求得 n≦(3^k)/2 - 1 於是称k次要解得出来的个数就是上面三个情形的综合 进一步考虑 因为3^k总是奇数 所以其实上面的(3^k)/2可以换成(3^k - 1)/2 求得的n不变 而(3^k - 1)/2除以3总是余1 所以 上面的三个情形中符合条件的数就是换过後的右式再减1 也就是 / n≦(3^k - 1)/2 - 1, 当n除以3余0 | n≦(3^k - 1)/2 - 2, 当n除以3余2 \ n≦(3^k - 1)/2 - 3, 当n除以3余1 三个情形的联集即为所有的情形 因此 秤k次要秤得出来的个数n最多是 (3^k - 1)/2 - 1 = (3^k - 3)/2 对小的k检查一下: k=1 => n≦(3-3)/2 = 0 //这很合理 因为要能玩最少要3个硬币 //而3个硬币就必须要秤两次 k=2 => n≦(9-3)/2 = 3 //eieio举的例子 k=3 => n≦(27-3)/2 = 12 //所以原题13个就不行了 对更大k列表如下: k=4 => n≦39 k=5 => n≦120 k=6 => n≦363 k=7 => n≦1092 ... --- 如果只是要找出谁是伪币 那可以分出的硬币个数可以+1 主要是多了n除以3余1中的1个情形 拿13个3次的情形来说明好了: 当ABCD=EFGH时 剩下的IJKLM中有一个是伪币 虽然情形看起来有10种 比3^2=9多 但其实我们可以不必分出到底m是轻是重 於是情形就剩9种 (即: I伪轻 I伪重 J伪轻 J伪重 K伪轻 K伪重 L伪轻 L伪重 M伪) 这样剩下的就可以秤二次分出来了 更多次的情形是类似的 --- 以上完全没有考虑到往後分堆的策略问题 所以其实很不严谨 也许分到後面会有不可意料的事情发生也说不定 @@" 不过可以确定的是 这里求出的这个值是个上界 更多绝对分不出来这样 -- 'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 210.70.172.164