转一个面试题：有100个金币，其中有一个比较轻。给你一个天平，怎样用四次天平确认出哪个金币轻？
有100个金币，其中有一个比较轻。给你一个天平，怎样用四次天平确认出哪个金币轻？ 问题点数：20、回复次数：42Top
1 楼oo（为了名副其实，努力学习oo技术ing）回复于 2005-12-19 17:08:15 得分 0
四次只能81个Top
2 楼province_（雍昊）回复于 2005-12-19 20:31:06 得分 0
没有其它信息的话我称不出，帮顶吧。Top
3 楼rwxybh（行云）回复于 2005-12-19 21:33:09 得分 0
回复人： oo(为了名副其实，努力学习oo技术ing) ( ) 信誉：110 2005-12-19 17:08:00 得分: 0
四次只能81个
======================================
我支持这个说法，哈哈Top
4 楼improgrammer（无忌）回复于 2005-12-19 22:05:11 得分 0
分成四堆，（A，B，C，D）=（27，27，27，19）；
第一次：A--B
T1若等，则C分为（C1，C2）=（19，8），
T1--第二次：C1--D
T11若等，则用两次可从C2中分出轻币；#T11。
T12若C1<D，则用两次可以从C1中分出轻币；#T12。
T12若C1>D，则用两次可以从D中分出轻币；#T13。
#T1.
T2若A<B,则用三次可从A中分出轻币.#T2
T3若A>B,则用三次可从B中分出轻币.#T3
#
Top
5 楼iamcaicainiao（老菜，长征）回复于 2005-12-19 22:05:21 得分 0
标上号码就可以了。
最后一次，众所周知，一定是从3个里面分辨出哪个轻，很好办。称2个，哪个轻就是哪个，如果重量相等，则没被称的那个就是轻的。
按这样，倒数第二次就是，3，3，3
倒数第三次就是，9，9，9
倒数第一次是，27，27，27。
所以，楼上的楼上都说是81。。。
问题是我觉得应该还能多加几个，思考中，大家一块思考思考。
Top
6 楼improgrammer（无忌）回复于 2005-12-19 22:08:36 得分 0
SORRY.
T12,T13命题不成立.
Top
7 楼zeuswugeng（wugeng）回复于 2005-12-20 08:12:07 得分 0
诶，都白说..Top
8 楼copygirl（wa!）回复于 2005-12-20 08:57:52 得分 0
嗯，想起来了：
1、先分成33，33，33，1，称一堆33和一堆33的，如果等重，则判断剩下的那堆33；否则判断比较轻的那堆33；如果剩下的那堆33判断到最后没有轻的，说明1就是轻金币；
2、现在就是称三次从33个金币中拣出一个轻金币的问题了。再分成三堆，称任意两堆，取出11个金币判断；
3、把11个金币分成3，3，2，再称两次判断出轻金币--这就不用写了。Top
9 楼Cantonese00（（⊙_⊙））回复于 2005-12-20 09:00:23 得分 0
把11个金币分成3，3，2
------------------------
这好像有问题吧？Top
10 楼goodboy1881（积木)(谁都别拦着我在水源升星）回复于 2005-12-20 09:03:55 得分 0
3，3，2 如果 3,3等重那么 2里面有一个不好的。
如果不一样重就重新称轻的。这样就可以了。Top
11 楼Cantonese00（（⊙_⊙））回复于 2005-12-20 09:09:56 得分 0
呵呵～
我的意思是11个怎么分成了3,3,2（8个了）
^_^Top
12 楼cunsh（村少）回复于 2005-12-20 09:15:56 得分 0
左边一个. 右边一个.
运气好的话一次就出来了.Top
13 楼goodboy1881（积木)(谁都别拦着我在水源升星）回复于 2005-12-20 09:28:09 得分 0
寒了。小学加法没有学好。。。
早晨身体起来脑袋没有起来。。。
跑路。。。。Top
14 楼xuelong_zl（点雨点[我身上咋就没MM的香水味涅??#-_-]）回复于 2005-12-20 09:51:21 得分 0
这个是不可能的，除非向楼上说的运气，如果以算法形式表示，最少的次数为┌log3N┐(汗，CSDN的字体太不爽了，3是下标，也就是┌lgN/lg3┐)根据此题的要求也就是最少要5次才可以，这就是一楼OO说81的原因，根据公式4次最多可以从81个球里找。
至于公式的推导，大家可以想一想分治算法的思想，只不过我们常用的分治算法都是分为两分，而这个情况时是每次分为三份。Top
15 楼xuelong_zl（点雨点[我身上咋就没MM的香水味涅??#-_-]）回复于 2005-12-20 09:53:08 得分 0
回复人： goodboy1881(积木) ( ) 信誉：110 2005-12-20 09:28:00 得分: 0
寒了。小学加法没有学好。。。
早晨身体起来脑袋没有起来。。。
跑路。。。。
//===========
更寒了，你个数学系的家伙.........，嘿嘿Top
16 楼xuelong_zl（点雨点[我身上咋就没MM的香水味涅??#-_-]）回复于 2005-12-20 09:54:50 得分 0
回复人： Cantonese00(（加加西）) ( ) 信誉：100 2005-12-20 09:09:00 得分: 0
呵呵～
我的意思是11个怎么分成了3,3,2（8个了）
^_^
//====================
怎么分？？恩，这个简单，都不用脑子就分能分出来.......
^-^Top
17 楼goodboy1881（积木)(谁都别拦着我在水源升星）回复于 2005-12-20 09:57:54 得分 0
雨点这个时候落井下石。。。Top
18 楼koala1985（Fy）回复于 2005-12-20 10:48:51 得分 0
如果能在天平两边互换金币就好办了..Top
19 楼jwtgod（阿桔）回复于 2005-12-20 11:05:47 得分 0
33 33 34
\ / （称1次） |
11 11 11 11 11 12
\ / （称2次，或分上面的12为 4 4 4）
4 4 3
\ / （称3次）
1 1 2
|（称4次,或分上面的 3 为1 1 1）
1 1Top
20 楼jwtgod（阿桔）回复于 2005-12-20 11:12:17 得分 0
晕，怎么怎么回复后格式就乱了，大家凑合着看吧
总之，
100=33+33+34
33=11+11+11(或34=11+11+12)
11=4+4+3（或12=4+4+4）
4=1+1+2(或3=1+1+1)
2=1+1Top
21 楼Cantonese00（（⊙_⊙））回复于 2005-12-20 11:25:31 得分 0
33 33 34
\ / （称1次） |
11 11 11 11 11 12
\ / （称2次，或分上面的12为 4 4 4）
4 4 3
\ / （称3次）
1 1 2
|（称4次,或分上面的 3 为1 1 1）
1 1
----------------------------------------
你已经用完了4次，那么最后的2个你还是分不出来的。。。
如果能在天平两边互换金币就好办了..
---------------------------------------
是可以换的吧，但是也是没有办法把4个最后一次称出来（至少偶想不到）
^_^Top
22 楼Cantonese00（（⊙_⊙））回复于 2005-12-20 11:30:57 得分 0
这种经典问题应该已经有结论了的吧。。。
回复人： oo(为了名副其实，努力学习oo技术ing) ( ) 信誉：110
四次只能81个
回复人： xuelong_zl(点雨点[好想村里的MM们............]) ( ) 信誉：100
这个是不可能的，除非向楼上说的运气，如果以算法形式表示，最少的次数为┌log3N┐(汗，CSDN的字体太不爽了，3是下标，也就是┌lgN/lg3┐)根据此题的要求也就是最少要5次才可以，这就是一楼OO说81的原因，根据公式4次最多可以从81个球里找。
---------------------------------------------------------
硬想了N久，还是没他们的一下数学推理来的快的说
呵呵～ ^_^Top
23 楼jwtgod（阿桔）回复于 2005-12-20 11:51:57 得分 0
Cantonese00(（加加西）)
你已经用完了4次，那么最后的2个你还是分不出来的。。。
----------------------------------------
已经写的清楚了啊，第一次称33&33，第二次称11&11，第三次称4&4，第四次称1&1（即2）正好四次啊！你多算了一次吧Top
24 楼jwtgod（阿桔）回复于 2005-12-20 11:58:38 得分 0
可能是我没写明白，我改了一下，这样行了吧
33 33 34
\ / （称1次） |
11 11 11 11 11 12
\ / （称2次，或分上面的12为 4 4 4）
4 4 3
\ / （称3次）
1 1 2
|
1 1
\ /（称4次,或分上面的 3 为1 1 1）
完毕Top
25 楼rainharder（风）回复于 2005-12-20 12:14:43 得分 0
楼上的，最多需要5次哦Top
26 楼rainharder（风）回复于 2005-12-20 12:16:51 得分 0
第四次1&1等重，还需要一次分开2Top
27 楼jwtgod（阿桔）回复于 2005-12-20 13:01:45 得分 0
啊哈，对哦Top
28 楼zeuswugeng（wugeng）回复于 2005-12-20 14:37:26 得分 0
说了这么多，还是白说，哈哈Top
29 楼fieldwind（旷野之风）回复于 2005-12-20 15:00:53 得分 0
这个问题，我是在别的论坛上看到转过来的。个人思考之后也觉得至少要5次，实在不解4次如何能称出来。大家的结论和我的差不多，呵呵。Top
30 楼lisypro（）回复于 2005-12-20 15:16:38 得分 0
高实在是高Top
31 楼xuelong_zl（点雨点[我身上咋就没MM的香水味涅??#-_-]）回复于 2005-12-20 15:42:12 得分 0
加加西，有时间好好想想底数为什么是3吧,如果想出来，就深化了二分搜索算法的思想，有点帮助Top
32 楼Cantonese00（（⊙_⊙））回复于 2005-12-20 17:11:40 得分 0
恩，谢谢师兄。。。
这个问题我就想得到为什么是3,和二分搜索也有写过,基本了解二分法的思想。呵呵～
但是还没有像你这样联系在一起来想。。
醍醐灌顶,3Q
^_^Top
33 楼SammyLan（(基础决定你能走多远)--英语菜才是真的菜）回复于 2005-12-20 17:21:58 得分 0
N次只能辨别3^N/2-1个球 (=_=)Top
34 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-12-20 17:28:00 得分 0
N次辨识 3^N
每次把剩余的全部内容均分三份，任意两份比较，自然可以知道可选范围在哪一份当中
没有附加条件，100个4次是比较不出来的Top
35 楼neweat（啊楠）回复于 2005-12-20 20:26:31 得分 0
我认为给在面试时提问的人一拳，他就告诉你答案了～反正都是不知道
仅供参考 谢谢～Top
36 楼demon1985（我永远爱你 光光！）回复于 2005-12-20 22:11:07 得分 0
UPTop
37 楼sandrowjw（我的小猫照片给弄坏了，心都碎了）回复于 2005-12-21 09:45:37 得分 0
汗，不可能任务了Top
38 楼Empire_KK（风语）回复于 2005-12-21 10:25:15 得分 0
UP
精确比较的话
给定次数N 代比较数量S
则S <= 3^N
试证：
前提：1. 知道有一个或轻或重
2. 3个用天平一次能测出，大于3个用天平一次不能测出 （除非运气）
3. 平均3等分能最大数量排除
若S > 3^N 则
1. 三等分N此后必定有一份大于3 又前提2 得证！ （尽可能三等分 如5 -- 1 2 2）
2. 若没有尽可能三等分 称i次后 则第i+1待分的数量可能比 尽可能三等分 的第i+1次要多 由1 得证！Top
39 楼fieldwind（旷野之风）回复于 2005-12-23 17:43:08 得分 0
结贴！Top
40 楼Hoho_dinosaur（太阳下山，冰淇淋流泪；大风吹，苞米花好美）回复于 2005-12-30 11:44:13 得分 0
才发现自己的智商太低！！哈哈Top
41 楼chengzanmiao（高薪為共產當多納稅）回复于 2005-12-30 13:23:50 得分 0
丟!實在沒想法了Top
42 楼Nzm（一鸣）回复于 2006-01-05 12:34:51 得分 0
markTop
