1 2 3 456 7 8 9 10 ... 11 下一页

楼主: geslon

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

geslon

白魔

Rank: 1

积分: 72
帖子: 48
精华: 1
UID: 23922
性别: 保密

发表于 2008-4-20 23:27:51 |显示全部楼层

<CITE>对于本人出的这道题，好多网友都回答得很棒，谢谢。不过一直没有看到符合我的完整回答的答案。</CITE>
<CITE></CITE> 
<CITE>特别感谢whitetiger在37楼的详细解答和深入思考。你的答案，虽不中，亦不远矣~~</CITE>
<CITE></CITE> 
<CITE>比如，在情况1）里，你觉得不可能是7或者8号球有问题么？可你根本没有考虑它们俩。</CITE>

使用道具举报

whitetiger

红魔

Rank: 4

积分: 1609
帖子: 266
精华: 0
UID: 5208
性别: 男

发表于 2008-4-21 09:51:39 |显示全部楼层

原帖由 geslon 于 2008-4-20 23:27 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=116645&ptid=6973" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A>
<DIV class=t_msgfont id=postmessage_116645>
<CITE>对于本人出的这道题，好多网友都回答得很棒，谢谢。不过一直没有看到符合我的完整回答的答案。</CITE>
<CITE></CITE> 
<CITE>特别感谢whitetiger在37楼的详细解答和深入思考。你的答案，虽不中，亦不远矣~~</CITE>
<CITE></CITE> 
<CITE>比如，在情况1）里，你觉得不可能是7或者8号球有问题么？可你根本没有考虑它们俩。</CITE></DIV>

是I），不是1）。
确实没提，因为我写的时候漏掉了，现在已经改正了。
 
主要把精力集中在前面那些命题的考虑上了，对于具体问题的解决只是操作层面的问题，通过前面命题的描述应该能解决。

使用道具举报

lichunfu

入魔

积分: 1
帖子: 1
精华: 0
UID: 29463
性别: 保密

发表于 2008-4-22 11:45:44 |显示全部楼层

呵呵

下面给出 15 个小球的一种思路，画图太麻烦，用文字简单表述：     设正常球的重量为 x ，异常球的重量为 y 。     把 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 个球分为 5 组：             (1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14) (15)       第一次称：(1 2 3 4) (5 6 7 8) 重量为 a （a=8x 或 a=7x+y），     第二次称：(5 6 7 8) (9 10 11 12) 重量为 b （b=7x+y 或 b=8x ），     如果 a = b ，则异常球在 (5 6 7 8) (13 14) (15) 中；     否则，异常球在 (1 2 3 4) (9 10 11 12) 中。      1、如果 a = b ，则异常球在 (5 6 7 8) (13 14) (15) 中：               第三次称：(5 6 13 14) 重量为 c （c=3x+y 或 c=4x ），           如果 c = a / 2 ，则 (15) 为异常球，第四次直接称 (15) 的重量。             否则第四次称 (1 5 7 13) 重量为 d （d=3x+y 或 d=4x ），                列出关于 x 、y 的两个方程（a 、c 为常数的那两个），解之，             代入（d=3x+y 或 d=4x ）检验，便可得出满足（d=3x+y 或 d=4x ）之一             的 x 、y 值。从而确定异常球在 (13 14)、(5 6) 或 (7 8) 中。          2、如果 a 与 b 不等，则异常球在   (1 2 3 4) (9 10 11 12) 中：         第三次称：(3 4 9 10) 重量为 d （d=3x+y 或 d=4x ），         列出关于 x 、y 的两个方程（a、b 为常数的那两个），解之，         代入（d=3x+y 或 d=4x ）检验，便可得出满足（d=3x+y 或 d=4x ）之一         的 x 、y 值。从而确定异常球在 (3 4) (9 10) 或 (1 2) (11 12) 中，         假设异常球在 (m n) 中，第四次称 (m n) 中的某一个球的重量。

使用道具举报

魔方小厦

入魔

积分: 1
帖子: 1
精华: 0
UID: 29470
性别: 保密

发表于 2008-4-23 18:35:33 |显示全部楼层

电子称是天平的吗???

使用道具举报

whitetiger

红魔

Rank: 4

积分: 1609
帖子: 266
精华: 0
UID: 5208
性别: 男

发表于 2008-4-24 08:14:29 |显示全部楼层

原帖由 魔方小厦 于 2008-4-23 18:35 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=118231&ptid=6973" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 电子称是天平的吗???

当然不是天平。
电子秤，是指能称出重量（数值）的秤。

使用道具举报

flwb

蓝魔

Rank: 2

积分: 519
帖子: 467
精华: 0
UID: 22856
性别: 男

发表于 2008-5-10 11:54:05 |显示全部楼层

[ 本帖最后由 flwb 于 2008-5-10 12:01 编辑 ]

使用道具举报

sthforever

入魔

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

发表于 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 编辑 ]

使用道具举报

kexin_xiao

银魔

小欣然的爸爸

Rank: 7 Rank: 7 Rank: 7

积分: 37843
帖子: 34374
精华: 15
UID: 16477
性别: 保密

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

学习中,等待最全的答案,楼主什么时候能公布啊

天津1群11471969，2群5834223
3群62462688，4群62462702
5群70735234，6群33712046
7群12240584，8群29198783
9群62974165，欢迎加入！

使用道具举报

whitetiger

红魔

Rank: 4

积分: 1609
帖子: 266
精华: 0
UID: 5208
性别: 男

发表于 2008-5-13 12:22:05 |显示全部楼层

原帖由 sthforever 于 2008-5-12 20:07 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=132452&ptid=6973" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 我想了一个通用的解法，不知有没有问题。   假设有N个球，其中有一个球质量与其他不同。设不同的球质量为q，而其他的球质量为p。   为方便，将N写成二进制数的位数记为n。将这N个球从0到N-1编号，并把 ...

是18#的改进。
 
该方法应该确实可行，也是完全可以证明的。（尽管他说没完整的证明。）

使用道具举报