iCAx开思网

标题: 好象大家都喜欢做题，那么来一个微软的招聘题！ [打印本页]

作者: xiadavid72 时间: 2003-5-19 13:24
标题: 好象大家都喜欢做题，那么来一个微软的招聘题！
微软公司的一道经典招聘题目

12个小球，其中11个一模一样，而有1个外表一样，但质量不一样（不知道是比其他的球重还是轻）。现在有一个没有刻度的天平，请最多用这个天平称三次，把这个不同的球找出来。

难点在于：您不知道那个不一样的球是比别的球重还是轻！

作者: metry 时间: 2003-5-19 14:51
打错了，在想象

作者: shjljg 时间: 2003-5-19 17:36
我们公司有人做出来了。哈哈。

作者: cgl888 时间: 2003-5-19 17:59
因為有刻度　所以用如下的方式　先稱6個　再稱3個　最後稱2個　就可以了

作者: xiadavid72 时间: 2003-5-19 18:16

cgl888 wrote:
因為有刻度　所以用如下的方式　先稱6個　再稱3個　最後稱2個　就可以了

???题目是没有刻度的嘛！

作者: mas12355 时间: 2003-5-19 20:14
先分四个一组，三组

称两组，如一样重，那就简单了

如不一样重，。。。。。

作者: 泥巴 时间: 2003-5-19 21:48
很早很早以前的问题了。。。。

作者: sanxingboy 时间: 2003-5-20 17:12
先分四个一组，三组

称两组，如一样重，那就简单了 1:1 ,1:1

如不一样重(排除其它四个),把八个小球编号,从天平两边同时取下两个小球,有两种情况产生,但结果都一样,又可以排出四个,假设剩下的小球编号是
1、2  ／3、4
对调称最后一次（即1、3  ／  2、4）根据天平的不平衡方向就可以确定到底是那一个球了

作者: chendz 时间: 2003-5-20 19:58
如果：

第一次○1○2○5○6<○3○4○7○8

第二次○1○2<○3○4

对调称○1○3<○2○4

根据○1<○4不能确定到底是那一个球。

正确答案过两天再发。

作者: 1314 时间: 2003-5-20 21:23

xiadavid72 wrote:

  
???题目是没有刻度的嘛！

有沒有刻度一樣,先分兩堆,除去重的6個,再分兩堆,除去重的3個,這時天平還可以用一次,隨便稱兩個,如果兩個一樣重的話沒稱的一個就是不一樣的了,

作者: 欧阳清风 时间: 2003-5-20 23:25
楼上的是错误的
如果那个唯一的球是重于其它球的
你这个方法就不行了，象你所说的第一次将重的6个除去
第二次称的话就平衡了，呵呵，你剩下的就只有一次机会了，而球却还有6个，，，，可怕吧

作者: 欧阳清风 时间: 2003-5-20 23:58
这个问题的称的时候可能性非常多
所以要列出各种可能性我现在将各种可能性与结果列表如下
我的答案已经出来了，这种答案不是一下子就说得清
听我慢慢说来
球有12个，目的并不是知道轻重，而是将它分出来就可以
好的
每个球都要先编号
1-12
要分成三组，每个组4个球
第一组1-4
第二组5-8
第三组9-12
先将第一组同第二组称重量
它的结果可能性有：（1）平衡了，那不同重量的球肯定是在9-12号在产生，将9-11号这三个球同标准重量的随便三个球一称，可能性有。。。（a）一样重，那结果肯定是12号球质量不一样了（只用了二次称）。。。。(b)轻于标准重量的球，那再将9与10称，谁轻谁就是，一样轻的话，就是11号球了（用了三次称）。。。（c）重于标准球，再将9与10称那谁重谁就是，一样重就是11号球
（2）第一组重于第二组（左边重于右边），那肯定那个非标重球在1-8号中产生，但不知它是轻是重，接下去所要作的是，将1，2，3号球从天平上移下来，同时将5，6，7号球从右边移到左边，再将9，10，11号球移到天平的右边，，这时如果。。。（a）第一组依然重于第二组，那就只能在4号球或者8号球中产生，要么是4号重，要么是8号轻，可以马上同标准球对比一下就知道答案了（称了三次）。。。。（b）第一组同第二组一样重了，那结果显然就是在1，2，3，号球中产生，而且这个球比一般的球要重，可以随便将1，2称一下，详细结果我就不描述了，参见{{{{（1）（c）}}}}（三次）。。。。。（c）经过移动后，第二组重于第一组了，结果肯定是在5，6，7号球中产生，而且是属于轻的球，可以随便将5，6号称一下，可能性参见{{{{（1）（c）}}}}
（3）第一组轻于第二组（左边轻于右边），作法一模一样，我就不详细描述了，参见（2）中的可能性
好啦
至此所有的可能性都包括了！！

作者: neuw 时间: 2003-5-21 08:32
不错，有道理！！！

作者: jxcad 时间: 2003-5-21 08:38
六个一边，称一次；互换其中的三个再称一次；现在就可以知道是那三个球的重量与其它三个球的重量不一样；最后称重量与其它组不同的三个球中的两个，就能知道是那个球重量不一样了。

作者: jasonpoon 时间: 2003-5-21 13:50

欧阳清风 wrote:
这个问题的称的时候可能性非常多
  所以要列出各种可能性我现在将各种可能性与结果列表如下
  我的答案已经出来了，这种答案不是一下子就说得清
  听我慢慢说来
  球有12个，目的并不是知道轻重，而是将它分出来就可以
  好的
  每个球都要先编号
  1-12
  要分成三组，每个组4个球
  第一组1-4
  第二组5-8
  第三组9-12
  先将第一组同第二组称重量
  它的结果可能性有：（1）平衡了，那不同重量的球肯定是在9-12号在产生，将9-11号这三个球同标准重量的随便三个球一称，可能性有。。。（a）一样重，那结果肯定是12号球质量不一样了（只用了二次称）。。。。(b)轻于标准重量的球，那再将9与10称，谁轻谁就是，一样轻的话，就是11号球了（用了三次称）。。。（c）重于标准球，再将9与10称那谁重谁就是，一样重就是11号球
  （2）第一组重于第二组（左边重于右边），那肯定那个非标重球在1-8号中产生，但不知它是轻是重，接下去所要作的是，将1，2，3号球从天平上移下来，同时将5，6，7号球从右边移到左边，再将9，10，11号球移到天平的右边，，这时如果。。。（a）第一组依然重于第二组，那就只能在4号球或者8号球中产生，要么是4号重，要么是8号轻，可以马上同标准球对比一下就知道答案了（称了三次）。。。。（b）第一组同第二组一样重了，那结果显然就是在1，2，3，号球中产生，而且这个球比一般的球要重，可以随便将1，2称一下，详细结果我就不描述了，参见{{{{（1）（c）}}}}（三次）。。。。。（c）经过移动后，第二组重于第一组了，结果肯定是在5，6，7号球中产生，而且是属于轻的球，可以随便将5，6号称一下，可能性参见{{{{（1）（c）}}}}
  （3）第一组轻于第二组（左边轻于右边），作法一模一样，我就不详细描述了，参见（2）中的可能性
  好啦
  至此所有的可能性都包括了！！

基本正确,这个题我在十年前就做过了,当时在念大学,好多人做不出的.

作者: jasonpoon 时间: 2003-5-21 13:54
::y::y::y::y

建议微机原理或有关编程语言课程分数不到90分者, 不必做此题!

作者: chrismon 时间: 2003-5-21 14:31
题目的要求就是既知道哪个球还要知道是轻是重。

作者: sxliuyu 时间: 2003-5-21 15:42
这是我上小学时的智力测验题

作者: 欧阳清风 时间: 2003-5-21 21:22
我这个就是可以既可以知道球的是哪个也可以知道到底球是轻是重
不信你仔细看一下

作者: chendz 时间: 2003-5-21 22:06
简单吗？

定义：【12球称量的9种情况标识】
第一次称量第一种情况【1.*.*】◎1◎2◎3◎4<◎5◎6◎7◎8
第一次称量第二种情况【2.*.*】◎1◎2◎3◎4=◎5◎6◎7◎8
第一次称量第三种情况【3.*.*】◎1◎2◎3◎4>◎5◎6◎7◎8
第二次称量第一种情况【*.1.*】◎4◎5◎6◎7<◎8◎9◎10◎11
第二次称量第二种情况【*.2.*】◎4◎5◎6◎7=◎8◎9◎10◎11
第二次称量第三种情况【*.3.*】◎4◎5◎6◎7>◎8◎9◎10◎11
第三次称量第一种情况【*.*.1】◎1◎4◎7◎10<◎3◎6◎9◎12
第三次称量第二种情况【*.*.2】◎1◎4◎7◎10=◎3◎6◎9◎12
第三次称量第三种情况【*.*.3】◎1◎4◎7◎10>◎3◎6◎9◎12

结论：【只有1个不知轻重的球的24种解】
【1.*.*】【*.1.*】【*.*.1】→【◎4轻】
【1.*.*】【*.1.*】【*.*.2】→【◎8重】
【1.*.*】【*.2.*】【*.*.1】→【◎1轻】
【1.*.*】【*.2.*】【*.*.2】→【◎2轻】
【1.*.*】【*.2.*】【*.*.3】→【◎3轻】
【1.*.*】【*.3.*】【*.*.1】→【◎6重】
【1.*.*】【*.3.*】【*.*.2】→【◎5重】
【1.*.*】【*.3.*】【*.*.3】→【◎7重】
【2.*.*】【*.1.*】【*.*.1】→【◎9重】
【2.*.*】【*.1.*】【*.*.2】→【◎11重】
【2.*.*】【*.1.*】【*.*.3】→【◎10重】
【2.*.*】【*.2.*】【*.*.1】→【◎12重】
【2.*.*】【*.2.*】【*.*.3】→【◎12轻】
【2.*.*】【*.3.*】【*.*.1】→【◎10轻】
【2.*.*】【*.3.*】【*.*.2】→【◎11轻】
【2.*.*】【*.3.*】【*.*.3】→【◎9轻】
【3.*.*】【*.1.*】【*.*.1】→【◎7轻】
【3.*.*】【*.1.*】【*.*.2】→【◎5轻】
【3.*.*】【*.1.*】【*.*.3】→【◎6轻】
【3.*.*】【*.2.*】【*.*.1】→【◎3重】
【3.*.*】【*.2.*】【*.*.2】→【◎2重】
【3.*.*】【*.2.*】【*.*.3】→【◎1重】
【3.*.*】【*.3.*】【*.*.2】→【◎8轻】
【3.*.*】【*.3.*】【*.*.3】→【◎4重】

作者: 欧阳清风 时间: 2003-5-21 23:01
楼上的怎么一点也不理解我的解法
我再强调一下，我那个解法
将所有的可能性已经全部包括了
你再好好理解一下
或者你自己重作模型一样地作一下
只能遗憾地说你对我的作法还是非常非常地模糊

作者: chendz 时间: 2003-5-22 11:19
重新整理，简单描述：

定义：【12球称量的9种情况标识】
第一种称量情况之一（左边轻）：【1.*.*】◎1◎2◎3◎4<◎5◎6◎7◎8
第一种称量情况之二（两边平）：【2.*.*】◎1◎2◎3◎4=◎5◎6◎7◎8
第一种称量情况之三（左边重）：【3.*.*】◎1◎2◎3◎4>◎5◎6◎7◎8
第二种称量情况之一（左边轻）：【*.1.*】◎4◎5◎6◎7<◎8◎9◎10◎11
第二种称量情况之二（两边平）：【*.2.*】◎4◎5◎6◎7=◎8◎9◎10◎11
第二种称量情况之三（左边重）：【*.3.*】◎4◎5◎6◎7>◎8◎9◎10◎11
第三种称量情况之一（左边轻）：【*.*.1】◎1◎4◎7◎10<◎3◎6◎9◎12
第三种称量情况之二（两边平）：【*.*.2】◎1◎4◎7◎10=◎3◎6◎9◎12
第三种称量情况之三（左边重）：【*.*.3】◎1◎4◎7◎10>◎3◎6◎9◎12

结论：【只有1个不知轻重的球的24种解，与称量次序无关的三次组合程式】
【1.*.*】【*.1.*】【*.*.1】→【◎4轻】
【1.*.*】【*.1.*】【*.*.2】→【◎8重】
【1.*.*】【*.2.*】【*.*.1】→【◎1轻】
【1.*.*】【*.2.*】【*.*.2】→【◎2轻】
【1.*.*】【*.2.*】【*.*.3】→【◎3轻】
【1.*.*】【*.3.*】【*.*.1】→【◎6重】
【1.*.*】【*.3.*】【*.*.2】→【◎5重】
【1.*.*】【*.3.*】【*.*.3】→【◎7重】
【2.*.*】【*.1.*】【*.*.1】→【◎9重】
【2.*.*】【*.1.*】【*.*.2】→【◎11重】
【2.*.*】【*.1.*】【*.*.3】→【◎10重】
【2.*.*】【*.2.*】【*.*.1】→【◎12重】
【2.*.*】【*.2.*】【*.*.3】→【◎12轻】
【2.*.*】【*.3.*】【*.*.1】→【◎10轻】
【2.*.*】【*.3.*】【*.*.2】→【◎11轻】
【2.*.*】【*.3.*】【*.*.3】→【◎9轻】
【3.*.*】【*.1.*】【*.*.1】→【◎7轻】
【3.*.*】【*.1.*】【*.*.2】→【◎5轻】
【3.*.*】【*.1.*】【*.*.3】→【◎6轻】
【3.*.*】【*.2.*】【*.*.1】→【◎3重】
【3.*.*】【*.2.*】【*.*.2】→【◎2重】
【3.*.*】【*.2.*】【*.*.3】→【◎1重】
【3.*.*】【*.3.*】【*.*.2】→【◎8轻】
【3.*.*】【*.3.*】【*.*.3】→【◎4重】

作者: curves 时间: 2003-5-22 11:26
4个一组。3次OK

作者: 欧阳清风 时间: 2003-5-22 11:27
不会吧？？？楼上的朋友还不理解？？？
那我随便要指定哪个球轻或者重
那个方法中可能性是属于哪种打个比方3号球重
是属于（1,2,3,4）>(5,6,7,8){{{{{第一次称}}}}}
           (4,5,6,7)=(8,9,10,11){{{{{第二次称}}}}}
     结果肯定得出结论是在1，2，3号球中产生，而且是属于重的
现在就可以随便拿1，2，3中其中两个称一下，谁重谁就是，一样重，就是剩下的那个

其实是随便哪个重或者随便哪个轻都可以用那个方案称出来，没有称不出来的情况，因为已经全包括了，

哎真的不理解你是怎么想的？？？/

作者: chendz 时间: 2003-5-22 11:46
更简明，确定的解：

作者: mobjyd 时间: 2003-5-24 06:29

欧阳清风 wrote:
这个问题的称的时候可能性非常多
  所以要列出各种可能性我现在将各种可能性与结果列表如下
  我的答案已经出来了，这种答案不是一下子就说得清
  听我慢慢说来
  球有12个，目的并不是知道轻重，而是将它分出来就可以
  好的
  每个球都要先编号
  1-12
  要分成三组，每个组4个球
  第一组1-4
  第二组5-8
  第三组9-12
  先将第一组同第二组称重量
  它的结果可能性有：（1）平衡了，那不同重量的球肯定是在9-12号在产生，将9-11号这三个球同标准重量的随便三个球一称，可能性有。。。（a）一样重，那结果肯定是12号球质量不一样了（只用了二次称）。。。。(b)轻于标准重量的球，那再将9与10称，谁轻谁就是，一样轻的话，就是11号球了（用了三次称）。。。（c）重于标准球，再将9与10称那谁重谁就是，一样重就是11号球
  （2）第一组重于第二组（左边重于右边），那肯定那个非标重球在1-8号中产生，但不知它是轻是重，接下去所要作的是，将1，2，3号球从天平上移下来，同时将5，6，7号球从右边移到左边，再将9，10，11号球移到天平的右边，，这时如果。。。（a）第一组依然重于第二组，那就只能在4号球或者8号球中产生，要么是4号重，要么是8号轻，可以马上同标准球对比一下就知道答案了（称了三次）。。。。（b）第一组同第二组一样重了，那结果显然就是在1，2，3，号球中产生，而且这个球比一般的球要重，可以随便将1，2称一下，详细结果我就不描述了，参见{{{{（1）（c）}}}}（三次）。。。。。（c）经过移动后，第二组重于第一组了，结果肯定是在5，6，7号球中产生，而且是属于轻的球，可以随便将5，6号称一下，可能性参见{{{{（1）（c）}}}}
  （3）第一组轻于第二组（左边轻于右边），作法一模一样，我就不详细描述了，参见（2）中的可能性
  好啦
  至此所有的可能性都包括了！！

      前两天看到此帖，想了很久，没能找到答案，今天早上，就在要醒来的那一秒钟之内，突然茅塞顿开！马上起床整理谁知有人捷足先登！！::?::?
      哎！！就差一点！！:}):}):})

作者: mobjyd 时间: 2003-5-24 06:44

chendz wrote:
更简明，确定的解：

::y::y::y::y

数学概念很清晰嘛！！::k::k::k::k

作者: quijote 时间: 2003-6-7 12:40
称法不只一种哦  根据不同的启发式（heurisitc）  有保守估计和博弈式两种

  但两种方法均有可能最终也不知道球的轻重的

作者: jinguodong 时间: 2003-6-8 17:44
先把12个球分成2组，设为A组和B组，放在天平上秤第一次，可以知道质量不对的球在那一组中，假设在A组中，从A组中取出两个球，把4个球分为两组，有两个可能性：
1。如果剩下的两组质量一样，那么可知质量不对的球在取出的两个球中，在天平上秤第3次，可以发现
2。如果剩下的两组质量不一样，可知质量不对的在那一组中，再秤一次就可以了

特此感谢王明耀，靳国栋编写

作者: wenny_wong 时间: 2003-6-10 11:36
欧阳很厉害！

作者: chendz 时间: 2003-6-13 21:34
其实还有一些与称量次序无关的具体的三次称量方案。如：
    ◎1.2.3.4<=>◎5.6.7.8
    ◎1.2.5.6<=>◎3.9.10.11
    ◎1.5.7.9<=>◎6.8.10.12
等。

欢迎光临 iCAx开思网 (https://www.icax.org/)