gxqcn 发表于 2013-12-5 16:00:37

一道称药片的微策略智力题

有1到10,10个盒子,每个盒子里面装了500个药片,药片的规格有9g或者10g的,每个盒子装的药片规格都是一样的。
给你一个秤(能够秤出质量),如何能够只秤一次,就找到1到10盒子里的药片规格?(知道哪些盒子装的是9g的,哪些装的是10g的?)

注:这是浏览CSDN看到的,感觉比较有趣,大家一道讨论下(原帖:http://bbs.csdn.net/topics/390629023,请先别急着点击)。

knate 发表于 2013-12-5 17:03:01

由于每种药规格只有两个规格,而且两者误差为1,因此直接可以看成0,1两种,
原题可以看成
∑▒〖a_i X_i 〗=M ,a_i=0,1
唯一性非负整数表示问题.
最简单的一个解,应该是,该求和是一个按权展开式,权最小的为2,因此最大值大致在512,原则上超出500,但是思路应该是对的.

如果是该称是天平的话,看成是
∑▒〖a_i X_i 〗=M ,a_i=0,1,-1,这个三进制展开的话,那么3^(10 / 2) < 500,应该是合适的.

如果只能放一边
∑▒〖a_i X_i 〗=M ,a_i=0,1,2,这个三进制展开的话,那么2 * 3^(10 / 2) < 500,似乎应该也是合适的.


补充内容 (2013-12-6 11:27):
0,1,2这个三进制似乎有问题

补充内容 (2013-12-6 12:08):
-1,0,1,这个三进制有时可以取消天平限制,这题 一般的称也是可以的..    不可以修改贴,郁闷

补充内容 (2013-12-6 12:14):
可以无视我的了,,,,,,,我发现反例了.

蓉依山爸 发表于 2013-12-6 14:38:44

这题简单:

1号瓶拿2的0次方(1)粒药,2号瓶拿2的1次方(2)粒药,3号瓶拿2的2次方(4)粒药,4号瓶拿2的3次方(8)粒药……10号瓶拿2的9次方(512)粒药

称重后,看超出90g多少?再把超出部分的重量转化为2进制,就知道是哪些瓶子里面的药,是10g一片了。最后,剩下的瓶子,装的都是9g一片的药

wayne 发表于 2013-12-6 15:24:25

能把药片物理性的掐成一半吗,:lol

===
也许掐不太准确, 用小刀 穿过 药片的中心,轻轻的摁着,切一刀吧。

wayne 发表于 2013-12-6 15:40:57

前面我们的思路 都是 把二的幂 当作 每个盒子所取的药片的个数 的权重。

可不可以是其他的数字,比如500以内的 某10个素数?

我觉得是大有可能的,无非就是解一个 不定方程的 正整数解。

wayne 发表于 2013-12-6 15:51:51

每种药片要么是9g,要么是10g,总共排列数是 2^10 = 1024.
1024 好小啊。 写一个程序,brute force!
随机的选择 10个比较靠近的大整数,分别计算所有排列对应的可能重量。 如果重量值 都不重复,那么就是可行的方案

gxqcn 发表于 2013-12-6 15:52:37

实际上,可以把药片的质量看作:0克 or 1克,
并不会对结果产生影响,但可以简化思路。

如果有更多不同的质量数,则按如下过程简化:
1、各数除以它们的最大公约数;
2、各数减去它们之间的最小值。

wayne 发表于 2013-12-7 09:37:37

gxqcn 发表于 2013-12-6 15:52
实际上,可以把药片的质量看作:0克 or 1克,
并不会对结果产生影响,但可以简化思路。



有这两个原则的话,二进制的表达应该就是最紧凑的组合了,于是,500以内就没有答案了。

wayne 发表于 2013-12-7 09:43:25

gxqcn 发表于 2013-12-6 15:52
实际上,可以把药片的质量看作:0克 or 1克,
并不会对结果产生影响,但可以简化思路。



看成0g,1g 就不能根据 各数减去它们之间的最小值 来简化了
所以该题 答案还是open的

gxqcn 发表于 2013-12-7 12:00:53

说一下我之前给出简化两原则的思路:

假设我们已经给出了一种可行方案,分别取各盒药片若干粒放置天平左盘,右盘放置一定的砝码使之平衡。
我们可以仅根据砝码读数,以及我们选择的加权系数,判定出唯一的单粒质量组合序列。

好了,我们假想现在的每粒药片实际上均可k等分,那么我们仅取各自的k分之一,则对应的砝码读数也缩减为先前的1/k,
我们依然可以仅根据砝码读数,以及我们选择的加权系数,判定出先前的唯一的单粒质量组合序列。

接下来,咱们再对每粒药片减少b克,右边的砝码对应地减少(b*药片称量总数)而使天平再次平衡,
我们仍然可以仅根据砝码读数,以及我们选择的加权系数,判定出先前的唯一的单粒质量组合序列。

因为我们上述过程都是相当于对一个线性不定方程作线性变换,不会影响方程的解。
但是简化后,有利于简化思路(对于人脑来说可减轻点计算和记忆负担;对于电脑来说也许效果甚微)。
页: [1] 2
查看完整版本: 一道称药片的微策略智力题