老题重提 12个铁球

17264 · 发表于 2012-12-10 11:56:55

本帖最后由 77104251 于 2012-12-15 10:50 编辑

据说一开始是微软的面试题？天枰秤铁球什么的我只是觉得太多孩子照本宣科照搬答案而不会真正解这题所以重新来一次

12个铁球一个质量不一样有一天平称三次把那个质量不一样的球找出来

大家可曾记得这题和8个铁球是在同一页上的，为什么呢？
因为题面都读不懂何来解题

————————————————cutting line——————————————————

虽然无人问津但也不代表本人可以偷懒
那么我就把自己的解法放出来

1.总数不足3的倍数时去上一轮的Z中取（也就是正常的铁球）
2.先从上轮X中的铁球选取此轮X的铁球到上限，再从上轮的Y中的铁球中选取此轮Z的铁球到上限，剩余的铁球将Z和Y填满
3.每次称量都始终保持天平左右和多出来的个数比为1:1:1(4-4 4，3-3 3，2-2 2)。设质量大的一边为X，另一边为Y，多余为Z。即X:Y:Z=1:1:1
4.移除所有正常铁球
5.如此反复
此乃所有3的倍数的铁球的分法上不封顶使用天平次数为log(3/2)(n/12)+3  n为球数次数小数向上取整

以15个铁球为例将方法演示一遍：
一
-1.由于15为3的倍数所以跳过1.
-2.因为此轮为第一轮所以跳过2.
-3.将铁球分为5-5 5，放上天平，得到X1>Y2 以及Z1。Z1=z1+z2+z3+z4+z5 由此z1 z2 z3 z4 z5为正常铁球。（问题铁球在Z1里的情况？5个铁球分3次分不出有鬼吧）
   X1=x1+x2+x3+x4+X5 ， Y1=y1+y2+y3+y4+y5
二
-1.剩余X1+Y1=10，10个铁球不足3的倍数，所以将z1和z2拿进来凑满12个铁球。
-2.此轮只有12个铁球，所以此轮X2:Y2:Z2=4:4:4.
   X2为x1+x2+x3+x4 （上轮X中的铁球选取此轮X的铁球到上限）
   Z2为y1+y2+y3+y4 （从上轮的Y中的铁球中选取此轮Z的铁球到上限）
  so Y2为x5+y5+z1+z2
-3.将铁球分为4-4 4，放上天平，仍然得到X2>Y2 以及Z2。Z2=y1+y2+y3+y4 由此y1 y2 y3 y4为正常铁球。（问题铁球在Z2里的情况？4个铁球分2次分不出也有鬼吧）
-4.移除x5 z1 z2
三
-1.剩余X2+Y2=5，10个铁球不足3的倍数，所以将z1拿进来凑满6个铁球。
-2.此轮只有6个铁球，所以此轮X3:Y3:Z3=2:2:2.
   X3为x1+x2（上轮X中的铁球选取此轮X的铁球到上限）
   Z3为y5+z1 （从上轮的Y中的铁球中选取此轮Z的铁球到上限）（所有Y被排除剩下就是X自家的事了）
  so Y3为x3+x4
-3.将铁球分为2-2 2，放上天平，仍然得到X3>Y3 以及Z3。Z3=y5+z1 由此y5为正常铁球。（问题铁球在Z3里的情况？同上）
-4.排除x3 x4
四
-1.剩余X3+Y3=2，2个铁球不足3的倍数，所以将z1拿进来凑满3个铁球。
-2.此轮只有3个铁球，所以此轮X4:Y4:Z4=1:1:1
   X4为x1（上轮X中的铁球选取此轮X的铁球到上限）
   Z4为x2 （从上轮的Y中的铁球中选取此轮Z的铁球到上限）
  so Y4为z1
-3.将铁球分为1-1 1，放上天平，仍然得到X4>Y4 以及Z4。Z4=x2 由此x2为正常铁球
-4.排除z1

其实我应该用18个铁球做列子因为18和15个铁球都是用4次，15太没难度了？
推导方法就让我抱进棺材吧反正没人看
最后，谁有那个蛋疼闲心的话请指摘吧
没读过几年书希望愿意看的人能看懂

24142 · 发表于 2012-12-10 15:27:19

第一次（6）——（6），第二次（3）——（3），第三次去掉一个（1）——（1），哪个不一样就是哪个，一样的话就是那个去掉的

17330 · 发表于 2012-12-10 23:31:06

3---3若不等重，再将其中的一个与另一堆中的3个比重量。相等则可知那一个铁球是轻是重。然后再1----1分

22478 · 发表于 2012-12-11 15:18:52

确定题目吗？本人愚钝，若都取极端的‘不等重’，则需要至少四次。多的一次用来测试质量不同的球是重了还是轻了。

22592 · 发表于 2012-12-11 15:54:00

一:4+4+4 二:2+2 三:1+1

13100 · 发表于 2012-12-12 11:12:28

好吧结果只找到称四次找出来的方法。。。好吧好吧我是来打个酱油的。顺便问下5楼同学一个天平只有两个盘怎么会有4+4+4的称法。。（不会@。。）

22568 · 发表于 2012-12-12 11:22:57

的确是照搬老题没改吖。。要答案的话随便搜肯定有。。自己重做？无非试人品和直觉罢了。。听天由命。。

ps.没记错的话我电脑应该有。。不过既然lz说要重做。。那就等有空弄一个。。不过按我的风格。。就算码出来也未必有别人看得懂。。。。

7 · 发表于 2012-12-12 16:57:25

折腾下。
先将12个球分成3堆： ABCD  |  EFGH  |  IJKL
第一次，将ABCD 和 EFGH 先放上天枰称：

1. 两边一样重
说明有问题的球在IJKL里，随便挑两个出来 JK 和 AB 称（第二次）
      1.1 两边一样重
      说明问题球在IL里，再挑一个L和A称（第三次）
            1.1.1 两边一样重
            结论：问题球是 I
            1.1.2 L重或轻
            结论：问题球是L
      1.2 JK重或轻
      说明问题球在JK里，再挑一个J和A称（第三次）
            1.2.1 两边一样重
            结论：问题球是K
            1.2.2 J重或轻
            结论：问题球是J

2. ABCD重 EFGH轻
说明问题球在这8个球里，挑6个球出来， AB|EFG 和 IJKL|H 称（第二次）
      2.1 两边一样重
      说明问题球在C|D里，随便挑一个C和J称（第三次）
            2.1.1 两边一样重
            结论：问题球是D
            2.1.2 C重
            结论：问题球是C
      2.2 AB|EFG重
      说明问题球在ABH里（如果问题球在EFG里，第一次称说明问题球是重量轻的球，那第二次不可能重），挑AH和JK称（第三次）
            2.2.1 两边一样重
            结论：问题球是B
            2.2.2 AH轻
            结论：问题球是H
            2.2.3 AH重
            结论：问题球是A
      2.3 IJKL|H重
      说明问题球在EFG里（如果问题球在AB里，第一次称说明问题球是重量重的球，那第二次不可能轻；如果问题球是H，第一次称不可能是轻球），挑E和G称（第三次）
            2.3.1 两边一样重
            结论：问题球是F
            2.3.2 E轻
            结论：问题球是E
            2.3.3 G轻
            结论：问题球是G

3. ABCD轻 EFGH重
= =参照2……

以上可以称出问题球，但第一种会有无法确定问题球是重是轻的情况，如果要确定是轻是重：

说明有问题的球在IJKL里，随便挑三个出来 JKL 和 ABC 称（第二次）
      1.1 两边一样重
      说明问题球是 I ，挑出来和 A 称（第三次）

      1.2 JKL重
      说明问题球在JKL里，挑 J 和 K 称（第三次）
            1.2.1 两边一样重
            结论：问题球是L
            1.2.2 J重
            结论：问题球是J
            1.2.3 K重
            结论：问题球是K
      1.3 JKL轻
      = =参照1.2

[IQ风暴] 老题重提 12个铁球