楼主: geslon

geslon系列难题之二：电子秤称小球问题 [复制链接]

sthforever

入魔

积分: 4
帖子: 3
精华: 0
UID: 30208
性别: 保密

1^#

发表于 2008-5-12 20:07:00 |显示全部楼层

我想了一个通用的解法，不知有没有问题。
 
假设有N个球，其中有一个球质量与其他不同。设不同的球质量为q，而其他的球质量为p。
 
为方便，将N写成二进制数的位数记为n。将这N个球从0到N-1编号，并把每个编号写成n位二进制数，高位不足补零。假设质量不同的球的编号为k，那么对这些球进行n次称量，若能通过每次测量的结果，分别确定k的二进制数的每位的数值，就能确定k的值。为方便，把k的二进制数的第i 位上的数值记做Ki。
 
每次取x个球进行称量，有两种情况，即这x个球中包含k号球，或这x个球中不包含k号球。若不包含k号球则记为0，反之记为1。这样在n次测量后，把结果依次排列，就可以得到一个n位二进制数。现在的目标是，找到一种分组的方法，使得结果的这个n位二进制数就是k。
 
这种分组方法如下：第i 次称量所选取的球，为其二进制数编号的第i 位上的数值为1的球。换句话说，对于第i 号球来说，i 写作二进制数后哪些位为1，则第i 号球就将被编入哪些组中。按此方法选取后，如果能根据称量结果，判断出第i 组球中是否含有k号球，并当其含有k号球时记为1，不含k号球时记为0，则可以根据称量结果得到的0和1的序列排列得到k。
 
这样分组后，除了最后一组，其他组的球数都相同。当这些球数相同的组被称量后，因为含k号球或不含k号球，只可能有两种结果，假设为a和b。但是因为不知道p和q的大小关系，无法得知a和b哪个对应含有k号球的质量，也就不知道Ki为1还是0。但是，如果第i 组和第j 组的称量结果相同，则说明Ki=Kj，反之则Ki<>Kj。
 
在刚才的分组基础上，做以下调整：
 
当第一次和第二次称量完成后，根据K1和K2，可以确定一定数量的球必然不是k号球。即，如果K1=K2，则所有编号的二进制数的第1位和第2位上数值不同的球，必然不是k号球；如果K1<>K2，则，所有编号的二进制数的第1位和第2位上数值相同的球，必然不是k号球。根据这种方法，当第二次测量完成后，至少可以找到N/2个球，其必不是k号球，即质量为p。把这些球记为Pi  （i<=N/2）。
 
在第三组球中加入P1，在第四组球中加入P1，P2，P3 .. ，使得第二组球，第三组球，和第四组球所包含的球的个数不同。其他组分组方式不变。
 
现在要做的是，根据第二组，第三组和第四组的称量结果，确定出p和q的值。
 
设第2，3，4组球，质量分别为W2,W3,W4，球的个数分别为n2,n3,n4。平均每个球的质量分别为T2=W2/n2，T3=W3/n3，T4=W4/n4。
 
------------------------------------
现在要证明，如果有n个球，其中最多有一个球的质量为q，其余质量为p；有m（n<>m）个球，其中最多有一个球的质量为q，其余质量为p，则当且仅当，n个球和m个球的平均质量都为p时，它们的平均质量相同。
 
证明：
 
反证法，分情况讨论：
1. 假设n个球中有一个球质量为q，m个球中有一个球质量为q，若令这n个球的平均质量与m个球的平均质量相等，则有：
  ((n-1)*p+q)/n = ((m-1)*p+q)/m    ->    (m-n)*(q-p)=0  
即
  m=n 或 p=q
与假设矛盾。
 
2. 假设n个球中有一个球质量为q，m个球质量均为p，若令它们的平均质量相等，则有：
  ((n-1)*p+q)/n = p    ->    p=q
与假设矛盾。
 
3. 假设n个球质量均为p，m个球中有一个质量为q，与上面情况对称。
 
综上所述，若m个球与n个球的平均质量相同，则它们的平均质量都为p。
------------------------------------
 
所以对于T2,T3,T4，如果其中有两个相等，例如T2=T3，则必有p=T2=T3。然后很容易算出q。
 
若T2,T3,T4均不相等，则令T5=(W3-W2)/(n3-n2)，T6=(W4-W3)/(n4-n3)，（若当初分组时n4-n3=n3-n2，则令T6=(W4-W2)/(n4-n2)，这里不做详细分析了..）
 
这时有两种情况，
 
1. 
T2,T3,T4都不等于p，即第2，3，4组都含有k号球
 
此时显然可见，T5=T6
 
2.
T2,T3,T4中，有且只有一个为p，例如T2=p
 
此时则T5和T6必有一个为p。
 
所以，
当T5=T6时，则p=T5；当T5<>T6时，必有一个与T2,T3,T4中的一个相等，相等的这个为p。
 
（这两种情况的推论没有详细证明...不知道有没有错... 有时间再补上）
 
 
综上所述，根据T2,T3,T4的值，必然可以求得p，根据p的值，就可以知道n次测量中哪些组中包含k号球，把这些组记为1，把其他组记为0，用其表示的n位二进制数即为质量不同的球的编号k。
 
 

[ 本帖最后由 sthforever 于 2008-5-12 20:22 编辑 ]

使用道具举报

返回列表

		自动登录	找回密码
密码			注册