据说此题是微软的面试题。具体题目为: 有十二球,其中有一个球与别的重量不同,或轻或重。给你一架没有砝码的天平,只能称三次,问如何找出那个与众不同得球。 我不是吹嘘自己做出了这道题,也不是想让大家说我火星,尽管这道题已经流传了很长时间了,也有人给出了解法,但是没有人从理论上分析一下。 我看过网上的解法,简直发晕,太复杂,于是着手建模,想论证一下这道题目的解法。另外再扩充到n个球中找到一个与众不同的球,最少要称几次。 首先我怀疑这道题目的正确性,我觉得这道题出的不是特别严谨。其实题目应该是改成可以找出与众不同的球并且知道球的轻重。这样改那么题目就比较严谨了,至于为什么这么说,下面给出来证明: 假设一共有12个球,那么此时有24种可能性,我们把球从1编号到12,那么这24种可能性为:1号球轻,1号球重,2号球轻,2号球重……以此类推,并且这24种可能性是相互排斥的,就是说只能有一种成立,别的不成立。假设不用天平称,那么我们随便选一个正确的概率为1/24。我们需要做得,就是使用天平把最后的那种可能性确定下来,就是出现一种百分之百成立的结果,把不可能的结果排除。 于是,为什么要加上最后要知道轻重,就是因为希望到最后只剩下一种可能性,即某个球是轻的,要么是重的。如果仅仅只是找出与众不同的球,那么可能出现你可以找出那个球,但是不知道它的轻重,这样出现还剩2种可能性就结束的情况。如果加上必须判断轻重,那么无论如何我们都要让最后只剩下一种可能性。 其次。天平是一个模型,他有三种状态,左边高,右边高,平衡——这对应了一种作用,就是能把可能性筛选,也就是说,当称了一次时,会出现3种状态,而每种状态对应几种可能性,也就是把24种可能性分开了,这样每称一次,分一次,到最后,只要保证每条分支都能到达1,也就是只剩下一种可能性。于是,这可以看成木桶效应,就是找出分支最长的一条,那么这条分支所使用天平的次数就是最少需要的。 因为可能性(也就是最后结果)的总和是确定的,是24种(球数目的两倍)。所以每一层的可能性之和是24。于是这个题目的模型就简化为了:把24分成三个数之和,再把每个再分成3个数之和……一直分下去,知道三个分支均为一为止。并且要求分的次数(层数)最少。 很显然,为了要达到层数最少的目的,每次分成的3份的数目应尽可能相等,于是对24处理,可以得到如下的分法,保证了层数最少: 24 |
(1,1,1) (1,1,1)(1,1,0)(1,1,1) (1,1,1)(1,1,0)
(1,1,1) (1,1,1)(1,1,0) 24---(8,8,8),第二次把每个8再分为(3,3,2)。然后第三次就能把3分为(1,1,1),把2分为(1,0,1)。其中0是指天平不存在那种状态了。比如只剩下一个球不知道轻重,那么再拿一个正常球和它称,就不会出现平衡的状态,此时用0表示平衡状态。 我们假设最左边的分支表示天平左边高,中间的表示平衡,右边的表示天平右边高。那么现在的问题是,到底有没有方法实现如上的分支情况,也就是说,是不是可以保证每次的天平称时都能如分支那样分开各种可能性?答案是肯定的,下面证明这种分法的现实性。 首先,我们假设球有3种状态,一种是被排除的球,也就是正常球,这种球会是在天平平衡的时候产生(两边平衡,肯定天平上的都是正常球)。第二种是双重球,也就是不知道它是轻的还是重的,就好像有双重身份一样,这种球是没有称过的球。第三种是单重球,也就是如果它是要找的,那么要么是轻的,要么是重的。这种球是天平不平衡的时候产生的,因为如果球在左边,那么它如果是特殊球,就必然是轻的(左边高),反之亦然。也就是说单重球身上只带有一种可能性。 下面重点说说双重球和单重球,首先,这两种球是互斥的。要么只存在单重球,要么只存在双重球。很简单,如果有单重球,那么那么特殊球必然在它们中间,这样双重球就都变成了正常球了。因为单重球是这样产生的,天平不平衡,那么特殊球肯定存在于天平之上,并且在哪一边,就决定了它的轻重。因为重的球不可能产生在天平轻的一端,反之也是一样。 好了,这下问题就简单了,这样,除第一次外,必定每一次的称重都是两种组合:双重球和正常球,单重球和正常球。第一次是全部双重球,无正常球。 这样,只要这两种组合满足在天平上称时,可以把各种可能性均分,那么就证明了上述的数字分解的分支可以实现。 先来看双重球和正常球的,设有d个双重球。因为每个球都有两种可能性,那么总共的可能性有2d种。那么如果d是3的倍数,就可以直接在天平左右各放d/3个球。这样,天平三种情况下:1 平衡,那么剩下的d/3个球中有特殊球,可能性剩下2/3 d种。2,左边高,那么没在天平上的都是正常球。而天平上左边的球,只有可能是轻的,所以有d/3种可能,同理,右边的d/3个只有可能是重的。这样可能性也剩下2/3 d。3,右边高,同理。于是,满足前面所说的,可以按分支进行。 如果d不能整除3,可能会余一或余二。这样,因为天平上的球必然是偶数个,而每个球的可能性是2,那么天平上的球的可能性将是4的倍数,这样,就会出现状况使得天平分出的3个分支之间的差大于1。比如8个双重球,只能选择天平上放6个或者4个,这样可能性会分成6,4,6或者4,8,4。显然不能允许这样的情况发生。这时因为正常球的个数是大于等于1的,我们可以在天平上放奇数个双重球,再用一个正常球去平衡,这样,我们就能保证可能性的3分支之间的差为1。比如8个球,可以在天平上放5个球加一个正常球,这样可能性的3分支为:5,6,5. 显然,第一种情况只有双重球和正常球的问题解决了。 再来看单重球和正常球: 这种情况比较复杂,因为单重球有两种,一种是轻单重球,一种是重单重球。 我们用数学归纳法来证明(不知道的去翻翻高中课本)。假设两种单重球个数之间的差是小于等于1的。然后我们可以做到这样的事情,拿出单重球总数的三分之一放到一边去,并且保证这三分之一的单重球中两种单重球的数目差小于等于1。 然后在天平两边各放三分之一,重点来了!此时我们要保证左边的轻单重球数目加上右边的重单重球的数目与右边的轻单重球数目加上左边的重单重球的数目相等或只相差1。并且保证左边的轻单重球数目与右边的轻单重球数目相差小于等于1。显然,这样的事情是可以做到的,只要把两边的轻重单重球相间的排列就行。因为总的单重球中的两种球的差是小于等于1的。 然后,看三种情况:1,天平平衡,那么未放到天平上的三分之一的球中有特殊球,由于单重球只带一种可能性,于是此分支的可能性就是原来的三分之一。2,如果左边高,那么天平左边的所有重单重球就不可能是特殊球,因为重单重球如果是特殊球,那么肯定会让天平的一端变沉而不是变轻。同理,天平右边的轻单重球也不可能是特殊球了。这样,在这种情况下,剩下的可能性就是左边轻单重球的个数加上右边重单重球的个数。3,右边高,同样的。 可见,无论三种结果中的哪一种,我们都能保证剩下的单重球中的两种球的差是小于等于1的。而且可能性也如我们所愿的分成了相等的3份。这样问题就解决了。 举个例子,假设有9个单重球,其中有5个轻单重球,4个重单重球。按分支的话应该是(3,3,3)。于是我们按照上面的原则,拿出2个轻单重球1个重单重球不称。在天平两端分别放2个轻单重球1个重单重球和2个重单重球1个轻单重球。这样,就能保证每一个分支都满足有3种可能性以及轻重单重球的数目差小于等于1。 可见,我们解决了单重球情况下如何满足分支的问题。只要单重球轻重的数目差小于等于1,就能满足前面的数目分支。那么,现在还有一个问题,就是当出现单重球的时候,是否其中轻重单重球的数目差是小于等于1的。 前面已经讲了,单重球与双重球是互斥的。单重球的出现是伴随着双重球的消失的。于是,我们在前面说过如何在只有双重球和正常球的情况下去称,其中说明了,如果双重球个数不是3的倍数,可以加入一个正常球去平衡。显而易见,如果没有加入正常球,那么天平两边产生的轻重单重球的个数是相等的;如果加入了平常球,那么两边产生的轻重单重球数目最多相差1。 这样,综上所述,除了第一次称,其他所有的情况下都能通过天平将可能性均分成3部分,也就是能满足我们数字分解的情况。 因为第一次要使用天平的时候没有正常球,所以无法去平衡。因此会出现前面说的,当球的个数不是3的倍数时,会发生分开的3组可能性之间的数目差会为2。这样可能性最多的那条分支将最终决定称的次数。 举例来说,本来称三次,按数字分支可以知道,最多能从27种可能性中找出一种。那么在不知道轻重的情况下,应该最多能从13个球(26种可能性)中找出特殊球并且知道轻重。但是,由于刚开始没有平常球去平衡,所以我们只能在天平两边各放4个球,这样26就被数字分解为(8,10,8)。这样,可能性为10的那条分支最少要再进行3次才能使每条分支到达1,这样总的次数就为4次。因此,3次最多只能分出12个球中的那个特殊球。 这样,任意给定n个球,不知道轻重。我们都可以知道到底最少需要几次才能找出特殊球并且知道轻重,并且可以给出称球的方法,而且还能进一步知道一共有几种方法。这样,微软的这道题就得到了最彻底的解答。 下面给出一个公式,来计算n个球到底最少需要几次。 由于第一次的特殊,所以分两种情况,当n为3的倍数,那么只要找到一个最小的3的m次方大于2n就行,m就是需要的次数。比如39个球,那么就有2n=78种可能性,最小的大于78的3的m次方的数为81,m=4。所以39个球最少要称四次。 当n不是3的倍数,那么要找到最长的分支,显然这个分支上的可能性应该是[n/3]+2,其中[]代表取整。然后我们要按此数找到m,那么最终需要的次数就是m+1. 好了,看完这些,大家就能亲自按上述的方法,找出微软12个球的解法,再不必看网上写的那些能把人看晕的答案了,呵呵。
楼主发言:1次 发图:0张 | 更多
/publicforum/content/free/1/1407173.shtml 另外欢迎大家去这个帖子,关于物理的。
我当初进现在公司的笔试题里就有这个!!
记得这道题目3次是不一定能确定球是重了还是轻了 有时只能确定球重是不正常的 当然也满足题目找出非正常的条件了
哦,我知道我NC了...楼主勇气可嘉,佩服.
楼主论证的不错,就是罗嗦了点 ps:这道题的理论分析很早就有了
似乎没必要考虑清或重
楼主的文章第一遍没看明白,还得再看一次。
对于十二球问题,我也有过研究,当时同学给我这个题目,说不能网上搜。我也想自己一个人看能不能找到解法,没想做好后给同学一看,跟他看到的答案不一样,以为我做的不对,可是经验证还是正确的。之后在网上搜这个问题的解法,找到跟我的不一样的另两个解法。也就是说我找到一种非常规的解法,也许早就有人把我的这个解法做出来但留在网上的却少见(至少我没搜到)。后来网上还看到一篇从理论上证明有解的文章:
“假设这十二个球原来都是好的,有一个人悄悄地拿起其中的一个做了手脚,也许是把它弄重了也许弄轻了。然后交给第二个人。这个时候,可以认为这十二个球调制了一个信息在里面,这个信息有多少种呢?有十二乘二等于二十四种可能。 ”
“再说天平。一个天平称一下,有三种可能,也发出了一个信息,即数量为三的信息。我们知道数量为二的一个信息,信息量称为一比特。那么,数量为三的一个信息用什么单位呢?我瞎编一个信息单位,叫一吹特好了。 ”
“这样一来,一个天平如果称三次,最多可发出三吹特的信息,三吹特的信息有多少种呢?就是3的3次方,共二十七种,要大于十二个球坏一个的信息量二十四种。这样,我就建立了信心,称三次是能够获得答案的,不仅是能够知道坏球是哪一个,而且知道是怎么个坏法,是轻,还是重。”
根据这个我总结一下,应该有27-24=3 三种答案, 而网上的两种和我自己找到的一种刚好就三种解法。(待续)
(续上) 第一种:(我想出的方法)
每四球为一组ABC三组,第一步比较A与B,如果A=B,则坏球在C组,接着比较C1、C2和C3、B1(标准球),(1)C1C2=C3B1时,坏球在C4上,称C4与B1,C4&B1则C4为重球;(2)C1C2&C3B1时重球在C1或C2上,称C1与B1,C1&B1则C1为重球,C1=B1则C2为重球;(3)C1C2&C3B1时轻球在C1或C2上,称C1与B1,C1&B1则C1为轻球,C1=B1则C2为轻球 (与(2)类似对称)。 如果第一步中一边重一边轻,设重的一组为A组。即A&B,C组为标准球
第二步就是比较A1B1C1与B2A2A3,有三种情况: (1)A1B1C1&B2A2A3则可能A1是重球或B2为轻球,下一步就称A1跟C1,A1=C1时B2为轻球,A1&C1时A1为重球,没有A1&C1的情况 (2)A1B1C1&B2A2A3则可能A2、A3是重球或B1为轻球,下一步重就称A2和A3,A2&A3时A2为重球;A2=A3时B1为轻球 (3)A1B1C1=B2A2A3,则可能重球是A4或轻球是B3、B4,下一步称B3和B4,B3&B4时,B4为轻球,B3=B4时A4为重球, 下面两种只讨论A&B时另两种方法,因为A=B时只有一种方法 第二种方法:
第一步可以确定A&B
第二步,比较A1A2B1与A3A4B2, 有三种可能:
(1)A1A2B1&A3A4B2则可能A1、A2是重球或B2是轻球,再称A1和A2,如果A1&A2,则A1为重球.A1=A2则B2为轻球.
(2)A1A2B1=A3A4B2则可能B3、B4是轻球,再称B3和B4,如果B3&B4,则B4为轻球.如果B3&B4,则B3为轻球;
(3)A1A2B1&A3A4B2则可能A3、A4是重球或B1是轻球,再称A3和A4,如果A3&A4,则A3为重球.A3=A4则B1为轻球.(跟(1)情况对称相似) 第三种方法: 第一步可以确定A&B 第二步,比较A1B2B3B4与B1C1C2C3, 有三种可能: (1) A1B2B3B4 & B1C1C2C3 时,则可能A1是重球或B1是轻球,再称A1和C1,如果A1&C1,则A1为重球.A1=C1则B1为轻球. (2) A1B2B3B4 = B1C1C2C3 时,则可能A2、A3、A4是重球,再称A2和A3,如果A2&A3,则A2为重球.A2=A3则A4为重球. (3) A1B2B3B4 & B1C1C2C3 时,则可能B2、B3、B4是轻球,再称B2和B3,如果B2&B3,则B3为轻球.B2=B3则B4为轻球.(跟(2)情况对称相似) 验证以上方法有一Flash动画: http://www.flash8.net/flash/32835.shtml
知道是轻还是重那一个初中生也能解的出来了。 楼主居然还这么洋洋得意
是有点啰嗦了。郁闷。 这道题用不着讲那么深。高中知识就能解决(初中也差不多),别动不动扯上编程啊信息论。 我的论证是严密的,过程也是简单的。就是写的啰嗦了点,其实大家耐心看也挺好明白的。
好贴怎么没人顶?
我在百度里面以“天涯 易读 迅雷”搜不到我想找的网站,而用google,同样的关键词,搜索结果完全是我预期的。大家不信试一试。 都说在中文领域google不如百度,现在发现百度在中文领域也不行啊。
2)C1C2&C3B1时重球在C1或C2上,称C1与B1,C1&B1则C1为重球,C1=B1则C2为重球; -------------------------- 也有可能C1C2是标准球 C3是个轻球呢 (3)C1C2&C3B1时轻球在C1或C2上,称C1与B1,C1&B1则C1为轻球,C1=B1则C2为轻球 (与(2)类似对称) ------------------------- 也有可能C1C2是标准球 C3是重球哦
如果知道轻重的话,假设比其他的轻 先将12个球分为两份,分别放到天平的两边,就可以判断那个轻的属于哪6个了,然后再把这6个平均分成两份,放到天平两端,就能判断那个轻的球在哪三个中了,再在这三个中随便找出两个,分别放到天平的两端,如果一样,则第三个就是轻的球,如果不一样重,那么也可以判断了
我给出的是n个球中找出一个不知道轻重的球的一般解法,而且证明了。 还给出了n个球最少用几次的公式。 大家能否耐心看完?
好了,看完这些,大家就能亲自按上述的方法,找出微软12个球的解法,再不必看网上写的那些能把人看晕的答案了,呵呵。 使劲甩甩头,闭目眼神三分钟,然后狠狠掐自己一把,我确信,我没晕
不就是面试题嘛,直接就按题回答就好了,扯那么远做什么呢? 面试的时间很短,你扯个jb那么远,等你扯出来,估计微软也倒了.
13个要用4次,前面有证明为什么不行。
根据理论 由于天平有3个状态, 也就是 3次称量 有3^3=27 种可能. 不知道轻重则要刷掉一般,可以辨别出13个里有一个不不同(知道轻重的)清.
楼主,你奶粉喝多啦?这么一弱智问题,你还当个宝似的…
头晕路过,三撑走人
喝三鹿长大的主
特别晕
无语了。这题弱智? 你丫能看懂不?哪来的脑残?知道什么是数学归纳法不? 最近杂谈怎么都是脑残出没?
作者:学物理跟玩似的 回复日期: 16:30:26
13个要用4次,前面有证明为什么不行。 ------------------------ 要不要把怎么称的写出来啊. 都不知道你的数学是什么水平.
如此简单的问题
楼主写了那么长... 晕,,
三次搞定!
作者:whrlanlin 回复日期: 16:22:35
(续上) 第一种:(我想出的方法) 每四球为一组ABC三组,第一步比较A与B,如果A=B,则坏球在C组,接着比较C1、C2和C3、B1(标准球),(1)C1C2=C3B1时,坏球在C4上,称C4与B1,C4&B1则C4为重球;(2)C1C2&C3B1时重球在C1或C2上,称C1与B1,C1&B1则C1为重球,C1=B1则C2为重球;(3)C1C2&C3B1时轻球在C1或C2上,称C1与B1,C1&B1则C1为轻球,C1=B1则C2为轻球 (与(2)类似对称)。 这个方法根本就不对,C1C2&C3B1,有c1c2为重,c3为轻两种情况。 把12个球平均分为3份就不对,分成 5+5+2,再2+2+1才能判断出来。
其实这道题是有漏洞的,他没有告诉人们那个不同的球是重还是轻! 这是个很关键的一点。 举例说一下,12球,首先拿出10个放在天平上,每边是五个! 假设不一样的球,就在这十个里面,也就是说天平不平了,那你又如何判断不一样的小球在轻的一面里,还是在重的一面里呢! 所以说,这道题至少要告诉玩家不一样得球到底是轻了还是重了!
正确做法是 5---5,余2 2---2,余1 1---1,余0 但前提是要知道不一样的小球到底是重了,还是轻了!
楼主论证的很严密,又推广了一下,很牛!跟贴的不读完贴子就回,你们自己试下可以么?都说不知道是轻还是重了
第一种:(我想出的方法) 每四球为一组ABC三组,第一步比较A与B,如果A=B,则坏球在C组,接着比较C1、C2和C3、B1(标准球),(1)C1C2=C3B1时,坏球在C4上,称C4与B1,C4&B1则C4为重球;(2)C1C2&C3B1时重球在C1或C2上,称C1与B1,C1&B1则C1为重球,C1=B1则C2为重球;(3)C1C2&C3B1时轻球在C1或C2上,称C1与B1,C1&B1则C1为轻球,C1=B1则C2为轻球 (与(2)类似对称)。 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (2)C1C2&C3B1时重球在C1或C2上 这个不对吧,为什么不能是 C3轻呢。
知道轻重的话还用做吗? 这题就是因为不知道轻重所以才有意思。特别是后边出现单重球时候的交叉称法。 单重球,双重球,读chong,不是读zhong。
lz的思路是正确的,我当时也是这样想出来的 不过答案最后的确是有一种情况,只能知道坏球,不知道他轻重
楼主,这道题很简单啊,根本不用那么复杂! 6个小球,只知其中一个与另外5个质量不同。最多三次天平称量,就可以出结果。 假设球分123456号,取1,2号放入天平。 a:如果1,2两个球质量不同,则1,2号其中必有一个是特殊质量小球,所以,再拿1号小球中的一个与3456其中任意一个小球再次称量,如果质量相同,则2号小球是那个特殊小球,如果质量不同,则1号小球为特殊小球。 b:如果1,2两个球质量相同,则剩下的34组合与56组合的质量就应该与12号组合相同,不同的那一组肯定有一个球就是要找出的那个特殊小球。所以,取34号组合与12号组合称量。
如34与12号组合称量质量相同,则取1号(1234任意都行)小球与5号小球称量,相同,则6号为特殊球,不同,则5号为特殊球。(这种情况同样适用于12号组合先与56号组合称量的情况)
如34与12号组合称量质量不同,则34号期中必有特殊小球。取1号与3号称量,相同,则特殊小球为4号。不同,则特殊小球为3号。(这种情况同样适用于12号组任何一个与34号租中任何一个小球称量的情况)。 三招必出特殊质量小球!
题目问的是怎么称
而不是称几次
每一次4对4 剩4个 第二次2对2个 第三次1对1
我看了半天, 有些人的毛病根本不是会不会解题 而是连题目都看不清,且大言不惭 楼主,同情你
正确解法如下: 首先,分为三组,称其中2组; 这样,会产生2种结果: A:产生较重一组(z),较轻一组(q)和4个标准球(b); B: 产生8个标准球b, 还有一个问题组(q); 对于A, 第二次称重只有一类方法可确保第三次得出结果(轻重互换), G1(z1, b, b)和G2(q1, z2, z3), 而余下G3(q2, q3, q4, z4); 将会产生如下三种情况: A1: G1 & G2, 则第三次只需要将z1与b比较,若相等,则q1为问题球(轻了),否则z1为问题球(重了); A2: G1 & G2, 则第三次只需要z2与z3比较,较重的那个为问题球(重了) A3:G1 == G2, 则第三次比较方式为g1(q2, z4)与g2(q3, b)比较,若g1 == g2,则q4为问题球(轻了),若g1&g2, 则z4为问题球(重了),否则q3为问题球(轻了); 对于B, 第二次称重只有一种分组方法, G1(p1, b)和G2(p2, p3),而余下p4 同样产生2个结果: B1:G1 == G2, 则p4为问题球,第三次称重为p4和b比较得出p4是轻了还是重了 B2: G1 != G2,则第三次称重为p2和p3比较,其产生的结果只有如下解读:
若p2 == p3, 则p1为问题球,如第二次时G1 & G2, p1是重了,否则是轻了;
若p2 != p3, 则问题球一定不是p2就是p3,怎么判断哪个是呢?取决于G2和G1的比较,如果G2&G1,则问题球一定是重了的球,那么毫无疑问p2和p3中较重的那个就是问题球,否则就一定是个轻了的球,而且是p2和p3中较轻的那个。
如上,得解,且能最后知道这个问题球是轻了还是重了。
标准解如下(怀疑是唯一解): 首先,均分为三组,称其中2组,产生2种结果: A:产生较重一组(z),较轻一组(q)和4个标准球(b); B: 产生8个标准球(b), 还有一个问题组(q); 对于A, 第二次称重只有一类方法(2种组合)可确保第三次得出结果, G1(z1, b, b)和G2(q1, z2, z3), 而余下G3(q2, q3, q4, z4); {注:另一种组合为G1(p1, b, b)和G2(z1, p2, p3), 而余下G3(z2, z3, z4, p4),但本质一样,只不过操作完全相反罢了} 将会产生如下三种情况: A1: G1 & G2, 则第三次只需要将z1与b比较,若相等,则q1为问题球(轻了),否则z1为问题球(重了); A2: G1 & G2, 则第三次只需要z2与z3比较,较重的那个为问题球(重了) A3:G1 == G2, 则第三次比较方式为g1(q2, z4)与g2(q3, b)比较,若g1 == g2,则q4为问题球(轻了),若g1&g2, 则z4为问题球(重了),否则q3为问题球(轻了); 对于B, 第二次称重只有一种分组方法, G1(p1, b)和G2(p2, p3),而余下p4 同样产生2个结果: B1:G1 == G2, 则p4为问题球,第三次称重为p4和b比较得出p4是轻了还是重了 B2: G1 != G2,则第三次称重为p2和p3比较,其产生的结果只有如下解读: 若p2 == p3, 则p1为问题球,如第二次时G1 & G2, p1是重了,否则是轻了; 若p2 != p3, 则问题球一定不是p2就是p3,怎么判断哪个是呢?取决于G2和G1的比较,如果G2&G1,则问题球一定是重了的球,那么毫无疑问p2和p3中较重的那个就是问题球,否则就一定是个轻了的球,而且是p2和p3中较轻的那个。 如上,得解,且能最后知道这个问题球是轻了还是重了。
看来楼上的才是正解,我以前把这个问题想简单了。
高份低能的大学生们,先讽刺挖苦鄙视一下你们,让我这个初中生来告诉你们答案 1,12个球五个一组分三组,两组5个一组2个。把5个的两组先称,如果平衡就再称那剩下的2个,就分出来了。 2,把重的那5个球分三组,两组2个一组1个。把2个的两组用天平称,如果一样重那剩下的1个就是12个球中最种的了 3,把重的两个球放到天平上去称,结果就出来了 鄙视鄙视,严重的鄙视现在的白痴大学生,研究生和博士生,都是往脑子里被灌了大粪的,让俺这个初中生找到无比的智商优越感
实践中,这样的方法事最快的: 每边放6个球,一边一个地拿走,天平从倾斜变成平衡时,得到1个目标球和一个普通球。将2个球中的一个球和其余某个普通球比较,如果天平平衡,另一个球是目标球,否则该球是目标球。
作者:钱龙金典 回复日期: 21:01:59
高份低能的大学生们,先讽刺挖苦鄙视一下你们,让我这个初中生来告诉你们答案 1,12个球五个一组分三组,两组5个一组2个。把5个的两组先称,如果平衡就再称那剩下的2个,就分出来了。 2,把重的那5个球分三组,两组2个一组1个。把2个的两组用天平称,如果一样重那剩下的1个就是12个球中最种的了 3,把重的两个球放到天平上去称,结果就出来了 鄙视鄙视,严重的鄙视现在的白痴大学生,研究生和博士生,都是往脑子里被灌了大粪的,让俺这个初中生找到无比的智商优越感 *********************************** 初中生好!你怎么知道那个球一定比其它球重?如果比其它球轻呢?也就是说,每组5个,你怎么知道目标在轻的还是重的组里呢?
3步必出,不管球是轻是重 第一步,球分三堆,每堆4个 1(1.1,1.2,1.3,1.4)
2(2.1,2.2,2.3,2.4) 3(3.1,3.2,3.3,3.4) 比较1和2两堆 这时候有3种可能,1&2,1=2,1&2,其中1不等于2的时候下列步骤一样,对比情况也一样 第二步:当1和2不等的时候,假设1&2 1.1+1.2+3.1+3.2对比2里的四个球,如果相同,则1.3和1.4必有坏球,第三步对比1.3和3.1则可以得出坏球是1.3还是1.4了; 如果不同,第三步对比1.1和3.1就可以得出1.1还是1.2哪个是坏球了。 第二步当1=2时候,对比3.1+3.2+1.1+1.2和2里面的4个球 如果两者不等,则对比3.1和2.1就可以得出3.1坏了还是3.2坏了 如果两者相等,则对比3.3和2.1就可以得出3.3坏了还是3.4坏了
作者:钱龙金典 回复日期: 21:01:59
高份低能的大学生们,先讽刺挖苦鄙视一下你们,让我这个初中生来告诉你们答案 1,12个球五个一组分三组,两组5个一组2个。把5个的两组先称,如果平衡就再称那剩下的2个,就分出来了。 2,把重的那5个球分三组,两组2个一组1个。把2个的两组用天平称,如果一样重那剩下的1个就是12个球中最种的了 3,把重的两个球放到天平上去称,结果就出来了 鄙视鄙视,严重的鄙视现在的白痴大学生,研究生和博士生,都是往脑子里被灌了大粪的,让俺这个初中生找到无比的智商优越感 ========================================================= 小孩子,你怎么知道那个球是重了还是轻了呢?
whrlanlin的三个解法完全错误,关键在第二步完全忽视了不知轻重这个因素,而没有充分挖掘利用在每次称重过程中所产生的每个球轻重还是标准的信息,实际上,这个轻重信息在最后结果推导过程中是起决定作用的,正是由于组合的变换,轻重信息交叉排列,使得每一个球都显示出不同来,这样才能最终得出结果。
yonglew,你的第二步同样有问题,还是忽视了不知道轻重这个因素,如此第三步就一定有不能唯一确定的情况,更多的是知道其中2个是问题球,一个轻了,一个重了,但就是不知道哪个是问题球。
切 弱智!!
第一步比较第一组和第二组 1, 若A1A2A3A4=B1B2B3B4,问题球在C组里; 第二步比较A1A2A3与C1C2C3 若A1A2A3=C1C2C3,则问题球为C4,比较C4与其他任意一球的差别, 若A1A2A3&C1C2C3,则问题球在C1C2C3其中且为轻;C1&C2,C2为问题球,C1&C2,C1为问题球,C1=C2,则C3为问题球; 若A1A2A3&C1C2C3;判断方法和上面一样,问题球为重球。 2, 若A1A2A3A4&B1B2B3B4则第二步比较A1A2B1B2,A3B3C1C2
若A1A2B1B2=A3B3C1C2,则A4为重或B4为轻,A4&A1则问题球为A4,A4=A1则问题球为B4; 若A1A2B1B2&A3B3C1C2,则B1B2为轻球或A3为重球,第三步比较B1B2,哪个轻哪个就是问题球,若一样重,则A3为问题球且为重球; 若A1A2B1B2&A3B3C1C2,则A1A2中有一个重球或B3为轻;第三步比较A1A2,重的为问题球,一样重则B3为问题轻球。
重要的不是找出12个球的解法,而是要证明为什么最少用3次。 另外如果是n个球,那么最少应该用几次?有多少种称的方法? 其实我写的啰嗦,但绝对是严密的,只不过这年头人们都太浮躁了,连个解法都没耐心看完啊。
为什么是3次我不知道,但是我3次肯定能称出来,不管第一次出现什么情况我都可以.
看不下去...............你们慢慢讨论 水一个闪
只能说看见这么多人有兴趣研究这些问题,很高兴
昨晚为此失眠,看来今天还要失眠,我希望看到一个简单又严密的解决方案
我想应该有一种很简单的方案的……因为微软就是总是想办法把事情弄简单,这题的答案应该复合微软的要求才行
3次可以判断13个球啊!微软真有点软啊
此题除了分三组每组四个称之外应该没有其他办法了,当A=B时,感觉独一个的方法是最好理解的. A&B时,应比较(A1,C,C,C)和(B1,A2,A3,A4)最容易理解. 若天平不变,说明坏球没动,必在A1,B1之中. 若天平平了,说明坏球已拿下,必在B2,B3,B4之中. 若天平反转,说明坏球位置已动但还在天平上,必在A2,A3,A4之中.
f(n)=g(n-1)+f(n-1); g(n)=3*g(n-1)=3^(n-2)*g(2)
(n&2); g(1)=3; g(2)=8; f(1)=1; f(2)=4;(Actually, f(2)=3。) f(n)=g(n-1)+f(n-1)
=3^(n-3)*g(2)+f(n-1)
=3^(n-3)*g(2)+3^(n-4)*g(2)+f(n-2)
=3^(n-3)*g(2)+3^(n-4)*g(2)+...+3^0*g(2)+f(2)
=((3^(n-2)-1)/(3-1))*g(2)+f(2)
=((3^(n-2)-1)/(3-1))*8+4
=4*3^(n-2)
f(n)=4*3^(n-2)
12个珠至今都没想出个好办法,
根本就不难,证明很简单,只不过写的比较数学。 这玩意基本半天就想通了。就是一个纯数学问题嘛。
不错。分析很好
这题不是测数学知识的吧 无论轻重,轻重的结果其实是一样的 假设重量不同的为轻 12个球,对半放天平,取翘起的,再对半,取翘起的,剩3个球了, 取两球再放天平,等重,则剩下一个为轻的小球,若还是翘起,则翘起那端为轻的小球,结果出来了 =========要是说计算,有数学家,微软要的是脑子
楼主,我鄙视你
假设为轻?我倒,看清题在说话,受不了了。 知道是轻是重还用证明个P啊
这题目都成月经贴了,还是有大量人题目没看清就大言不惭
//12个球分3组 A组(A1 A2 A3 A4) B组(B1 B2 B3 B4)
C组(C1 C2 C3 C4)
if(A - B == 0) {
if(C1 - C2 == 0)
if(C3 - C4 ==0)
return C4;
return C3;
}
if(C1 - C3 == 0)
return C2;
return C1;
} } else if(A - B & 0) {
if( (A1+C2+c3+c4) - (B1+A2+A3+A4) == 0 )
if(B2 - B3 == 0)
return B4;
else if(B2 - B3 & 0)
return B3;
return B2;
}
else if( (A1+C2+c3+c4) - (B1+A2+A3+A4) & 0 )
if( (A1+B1) - (C1+C2) == 0 )
return A1;
return B1;
else if( (A1+C2+c3+c4) - (B1+A2+A3+A4) & 0 )
if(A2 - A3 == 0)
return A4;
else iF(A2 - A3 &0)
return A2;
return A3;
} } else if(A - B & 0) {
return 那你就把标A的和标B的球换换,再按上面方法测; } else {
return 题目很正确,楼主就是一自以为看过几本书、有文凭就是有文化的晕蛋自恋脑残; }
有意义吗?这么解。无意义。 先称六个
哪用这么麻烦
作者:penghae 回复日期: 20:36:45
标准解如下(怀疑是唯一解): 首先,均分为三组,称其中2组,产生2种结果: A:产生较重一组(z),较轻一组(q)和4个标准球(b); B: 产生8个标准球(b), 还有一个问题组(q); 对于A, 第二次称重只有一类方法(2种组合)可确保第三次得出结果, G1(z1, b, b)和G2(q1, z2, z3), 而余下G3(q2, q3, q4, z4); {注:另一种组合为G1(p1, b, b)和G2(z1, p2, p3), 而余下G3(z2, z3, z4, p4),但本质一样,只不过操作完全相反罢了} 将会产生如下三种情况: A1: G1 & G2, 则第三次只需要将z1与b比较,若相等,则q1为问题球(轻了),否则z1为问题球(重了); A2: G1 & G2, 则第三次只需要z2与z3比较,较重的那个为问题球(重了) A3:G1 == G2, 则第三次比较方式为g1(q2, z4)与g2(q3, b)比较,若g1 == g2,则q4为问题球(轻了),若g1&g2, 则z4为问题球(重了),否则q3为问题球(轻了); 对于B, 第二次称重只有一种分组方法, G1(p1, b)和G2(p2, p3),而余下p4 同样产生2个结果: B1:G1 == G2, 则p4为问题球,第三次称重为p4和b比较得出p4是轻了还是重了 B2: G1 != G2,则第三次称重为p2和p3比较,其产生的结果只有如下解读: 若p2 == p3, 则p1为问题球,如第二次时G1 & G2, p1是重了,否则是轻了; 若p2 != p3, 则问题球一定不是p2就是p3,怎么判断哪个是呢?取决于G2和G1的比较,如果G2&G1,则问题球一定是重了的球,那么毫无疑问p2和p3中较重的那个就是问题球,否则就一定是个轻了的球,而且是p2和p3中较轻的那个。 如上,得解,且能最后知道这个问题球是轻了还是重了。
GOOGLE:信息熵 N = LOG(a,b) 信息总量b(所有可能性),单位(次)信息量a(一个单位的可能性) N=LOG(3,12*2) N为整数,故N=3,最少需要3个单位。 通俗点说,每个位能表示a种状态,至少要用N=LOG(a,b)个位才能表示b种状态; 那么,已知每个位能表示a种状态时,当获得了N=LOG(a,b)个位的无重复有效信息时,可确定处于b种状态中的那一种状态。
作者:旋风无影 回复日期: 17:22:30
有意义吗?这么解。无意义。 先称六个 再称4个 再称2个 三次搞定 哪用这么麻烦 ======================================================== 看清楚再说,不知道不标准的球是轻是重, 直接问你最后一步,秤2个,一个重一个轻,哪个是不标准的?
真是无聊。以为编个程能解出来12个球的就NB? 先看清楚我讨论的是什么东西。 是证明n个球最少用几次可以称出来。 是证明为什么称3次最多能从12个球里边挑出特殊球。 而且给出的是用数学归纳法的严密证明。 一帮人不要贴都不看就在这大放厥词。 当然连轻重不知道这个条件都看不清的脑残我就更懒得说了。
作者:yonglew 回复日期: 21:20:24
作者:钱龙金典 回复日期: 21:01:59 高份低能的大学生们,先讽刺挖苦鄙视一下你们,让我这个初中生来告诉你们答案 1,12个球五个一组分三组,两组5个一组2个。把5个的两组先称,如果平衡就再称那剩下的2个,就分出来了。 2,把重的那5个球分三组,两组2个一组1个。把2个的两组用天平称,如果一样重那剩下的1个就是12个球中最种的了 3,把重的两个球放到天平上去称,结果就出来了 鄙视鄙视,严重的鄙视现在的白痴大学生,研究生和博士生,都是往脑子里被灌了大粪的,让俺这个初中生找到无比的智商优越感 ========================================================= 小孩子,你怎么知道那个球是重了还是轻了呢? ==================================================================== 明显的脑子进了屎的,看清楚题目再来说话,原本一个聪明活泼的人被教育成猪了。那个对半称重量的方法也很好
楼上的脑残,我无语了……
首先我怀疑这道题目的正确性,我觉得这道题出的不是特别严谨。其实题目应该是改成可以找出与众不同的球并且知道球的轻重。这样改那么题目就比较严谨了,至于为什么这么说,下面给出来证明: ============================================== 我手贱的再解释一下这句话。n个球里边有一个球重量跟别的不同,请找出这个球。我这句话的意思是不仅要找出这个球,还要根据称量的结果来判断出球的轻重。 脑残们看明白点。
【天涯杂谈】唯一官方★500人超级QQ群★正式开启,用激情畅聊的环境,恭候天涯杂谈各路精英大驾!!!! 群号~~~★★★【】★★★~~~~轻点鼠标,话题每天第一时间更新。天涯杂谈从此离你更近,让你更激情。
首先我怀疑这道题目的正确性,我觉得这道题出的不是特别严谨。其实题目应该是改成可以找出与众不同的球并且知道球的轻重。这样改那么题目就比较严谨了,至于为什么这么说,下面给出来证明: ============================================= 看了这句话就知道你脑残
看那个弱智归纳法
便知道了你脑残的程度
GOOGLE:信息熵 N = LOG(a,b) 信息总量b(所有可能性),单位(次)信息量a(一个单位的可能性) N=LOG(3,12*2) N为整数,故N=3,最少需要3个单位。 通俗点说,每个位能表示a种状态,至少要用N=LOG(a,b)个位才能表示b种状态; 那么,已知每个位能表示a种状态时,当获得了N=LOG(a,b)个位的无重复有效信息时,可确定处于b种状态中的那一种状态。 -------------------- 满足N = LOG(a,b)是一定的,但信息熵只是一个必要条件,不是一个充分必要条件。
第一步比较第一组和第二组 1, 若A1A2A3A4=B1B2B3B4,问题球在C组里; 第二步比较A1A2A3与C1C2C3 若A1A2A3=C1C2C3,则问题球为C4,比较C4与其他任意一球的差别, 若A1A2A3&C1C2C3,则问题球在C1C2C3其中且为轻;C1&C2,C2为问题球,C1&C2,C1为问题球,C1=C2,则C3为问题球; 若A1A2A3&C1C2C3;判断方法和上面一样,问题球为重球。 2, 若A1A2A3A4&B1B2B3B4则第二步比较A1A2B1B2,A3B3C1C2 若A1A2B1B2=A3B3C1C2,则A4为重或B4为轻,A4&A1则问题球为A4,A4=A1则问题球为B4; 若A1A2B1B2&A3B3C1C2,则B1B2为轻球或A3为重球,第三步比较B1B2,哪个轻哪个就是问题球,若一样重,则A3为问题球且为重球; 若A1A2B1B2&A3B3C1C2,则A1A2中有一个重球或B3为轻;第三步比较A1A2,重的为问题球,一样重则B3为问题轻球。
脑残实在太多了, 玛丽玛丽红,脑残退散~~~~
6 9 9 10 算24点,你会吗?我孩子出的
有十二球,其中有一个球与别的重量不同,或轻或重。给你一架没有砝码的天平,只能称三次,问如何找出那个与众不同得球。 将球对半称就行了。 第一次6-6 第二次3-3 第三次1-1 这样就知道那个球得量不同的。 用得着那么夸张吗????
作者:fenhl 回复日期: 19:17:40
我看了半天, 有些人的毛病根本不是会不会解题 而是连题目都看不清,且大言不惭 楼主,同情你 ---------------------------------------------------- 深有同感!!! 作者:钱龙金典 回复日期: 21:01:59 高份低能的大学生们,先讽刺挖苦鄙视一下你们,让我这个初中生来告诉你们答案 1,12个球五个一组分三组,两组5个一组2个。把5个的两组先称,如果平衡就再称那剩下的2个,就分出来了。 2,把重的那5个球分三组,两组2个一组1个。把2个的两组用天平称,如果一样重那剩下的1个就是12个球中最种的了 3,把重的两个球放到天平上去称,结果就出来了 鄙视鄙视,严重的鄙视现在的白痴大学生,研究生和博士生,都是往脑子里被灌了大粪的,让俺这个初中生找到无比的智商优越感 ------------------------------------------------------ 脑白金喝多了!!! 作者:自在的乐 回复日期: 19:44:17
6 9 9 10 算24点,你会吗?我孩子出的 --------------------------------------------------------- 9/6*10+9=24
没错吧
呵呵。刚才说错了。 应该是这样的 第一次3-3 第二次6-6 第三次1-1
一条毫无意义的破题,引来那么一群垃圾 你们这些废物吹牛可以,叫你们去微软搞算法,还不如让一群猪去
我的方法是 1.首先球分为4组,编码为 ABC DEF abc def共12个变量 2.第一称:ABC和DEF首先上称,获得数据,记录结果,这个结果有两个可能的情形: case 1和case 2 3.然后推论abc和def的关系 4.第二称: case 1 ABC=DEF,则把ab和de两边上称,形成ABCab和DEFde的组合。
case 2 ABC不等于DEF,则把AB和DE分别下称,形成ABabc和DEdef的组合。 5.记录ABCab和DEF,或者C和F的数据结果, 6. 结合第一称的数据,进行推论AB ab DE 和 de 7.第三称,把cf替换ad,或者AD替换CF上称, 则必然导出了BbEe谁是那个与众不同者,如是其他选择,则早在上面的称量和推导中已经有了结果。 说了大致过程,没说清楚,等整理一下再说。
作者:自在的乐 回复日期: 23:33:35
我的方法是 1.首先球分为4组,编码为 ABC DEF abc def共12个变量 2.第一称:ABC和DEF首先上称 ____________________ 这样的第一步绝不可能成功
这题不是测数学知识的吧 无论轻重,轻重的结果其实是一样的 假设重量不同的为轻 12个球,对半放天平,取翘起的,再对半,取翘起的,剩3个球了, 取两球再放天平,等重,则剩下一个为轻的小球,若还是翘起,则翘起那端为轻的小球,结果出来了 ========================================= 你是猪麽~~~你直接就取翘起的~~下意识的已经把问题小球定义为轻球了~~人家都说了不知道问题小球是轻还是重(相对于正常小球来说)
作者:penghae 回复日期: 20:36:45 标准解如下(怀疑是唯一解): 首先,均分为三组,称其中2组,产生2种结果: A:产生较重一组(z),较轻一组(q)和4个标准球(b); B: 产生8个标准球(b), 还有一个问题组(q); 对于A, 第二次称重只有一类方法(2种组合)可确保第三次得出结果, G1(z1, b, b)和G2(q1, z2, z3), 而余下G3(q2, q3, q4, z4); {注:另一种组合为G1(p1, b, b)和G2(z1, p2, p3), 而余下G3(z2, z3, z4, p4),但本质一样,只不过操作完全相反罢了} 将会产生如下三种情况: A1: G1 & G2, 则第三次只需要将z1与b比较,若相等,则q1为问题球(轻了),否则z1为问题球(重了); A2: G1 & G2, 则第三次只需要z2与z3比较,较重的那个为问题球(重了) A3:G1 == G2, 则第三次比较方式为g1(q2, z4)与g2(q3, b)比较,若g1 == g2,则q4为问题球(轻了),若g1&g2, 则z4为问题球(重了),否则q3为问题球(轻了); 对于B, 第二次称重只有一种分组方法, G1(p1, b)和G2(p2, p3),而余下p4 同样产生2个结果: B1:G1 == G2, 则p4为问题球,第三次称重为p4和b比较得出p4是轻了还是重了 B2: G1 != G2,则第三次称重为p2和p3比较,其产生的结果只有如下解读: 若p2 == p3, 则p1为问题球,如第二次时G1 & G2, p1是重了,否则是轻了; 若p2 != p3, 则问题球一定不是p2就是p3,怎么判断哪个是呢?取决于G2和G1的比较,如果G2&G1,则问题球一定是重了的球,那么毫无疑问p2和p3中较重的那个就是问题球,否则就一定是个轻了的球,而且是p2和p3中较轻的那个。 ========================= 这方法也不对: 首先假设你分的3组[1,2,3]中有问题的小球在第3组,任选其中的两组做第一次比较,假如你刚好选了[1,2]组,天平平衡了,那么马上得出问题小球在第3组;假如你刚好选了[1,3]组呢,那么天平不平衡,你怎么知道问题小球在哪一组?是不是还得在用剩下的一组跟[1,3]组的其中一组比较才知道?这样就称了两次,那么剩下的一次称的机会你怎么能得出结果?组的其中一组比较才知道?这样就称了两次,那么剩下的一次称的机会你怎么能得出结果?
我6年前就已经得出理论公式了,比你这个方法简单得太多了。
作者:钱龙金典 回复日期: 17:34:33
作者:yonglew 回复日期: 21:20:24 作者:钱龙金典 回复日期: 21:01:59 高份低能的大学生们,先讽刺挖苦鄙视一下你们,让我这个初中生来告诉你们答案 1,12个球五个一组分三组,两组5个一组2个。把5个的两组先称,如果平衡就再称那剩下的2个,就分出来了。 2,把重的那5个球分三组,两组2个一组1个。把2个的两组用天平称,如果一样重那剩下的1个就是12个球中最种的了 3,把重的两个球放到天平上去称,结果就出来了 鄙视鄙视,严重的鄙视现在的白痴大学生,研究生和博士生,都是往脑子里被灌了大粪的,让俺这个初中生找到无比的智商优越感 =========================================================== 从没看过这种,说几遍题目都不明白的人.....还好意思辩解 谁告诉你问题球一定是比其他重的....如果球是个轻球.你第2步到第3步秤来秤去都是一样重..还分个P.
一群傻鸟 让我这个小学毕业 给你解解 十二个球分成三组 也就是A-1球 A-2球 A-3球 A-4球
B-1球 B-2球 B-3球 B-4球
C-1球 C-2球 C-3球 C-4球
第一次先称a组和b组 第一次称c组和d组 这样就可以找出重量不一样的组,假设球是在C组里 第一次没有称道 第二次次我们只要称
C-1球 C-2球两个球-- 对--
C-3球 C-4球两个球 就可以知道有问题的小球在那个组里了 第三次只需称C-4球和先前一个正常的球就可以了 如果一样重的话肯定就是C-3球了 不一样重的话就是C-3球 天涯啊这么多高手
第三次假设在 C-3球 C-4球小组里 只需称C-4球和先前一个正常的球就可以了 如果一样重的话肯定就是C-3球了 不一样重的话就是C-3球 天涯啊这么多高手
第三次假设有问题的球在C-3球 C-4球小组里
只需称C-4球和先前一个正常的球就可以了 如果一样重的话肯定就是C-3球了 不一样重的话就是C-4球 上次打错字了
我真的受不了某些傻鸟了。 拜托把题目看清楚,再来嚷嚷行不。 要是知道轻重了,是人都会。
一群傻鸟 让我这个小学毕业 给你解解 十二个球分成三组 也就是A-1球 A-2球 A-3球 A-4球 B-1球 B-2球 B-3球 B-4球 C-1球 C-2球 C-3球 C-4球 第一次先称a组和b组 第一次称c组和d组 这样就可以找出重量不一样的组,假设球是在C组里 第一次没有称道 第二次次我们只要称 C-1球 C-2球两个球-- 对-- C-3球 C-4球两个球 就可以知道有问题的小球在那个组里了 第三次假设有问题的球在C-3球 C-4球小组里 只需称C-4球和先前一个正常的球就可以了 如果一样重的话肯定就是C-3球了 不一样重的话就是C-4球 天涯啊这么多高手
下面给出一个公式,来计算n个球到底最少需要几次。 由于第一次的特殊,所以分两种情况,当n为3的倍数,那么只要找到一个最小的3的m次方大于2n就行,m就是需要的次数。比如39个球,那么就有2n=78种可能性,最小的大于78的3的m次方的数为81,m=4。所以39个球最少要称四次。 当n不是3的倍数,那么要找到最长的分支,显然这个分支上的可能性应该是[n/3]+2,其中[]代表取整。然后我们要按此数找到m,那么最终需要的次数就是m+1. 好了,看完这些,大家就能亲自按上述的方法,找出微软12个球的解法,再不必看网上写的那些能把人看晕的答案了,呵呵。 ———————————————————————— lz不是学数学的吧? n个球到底最少需要几次? 大学概率论中的一个习题而已,结论特别简单,取2为底的对数,看看首数就知道
很老的东西了,这是个公式的,能计算出最少几次。 当然楼上很多没看清题目的朋友最好看清了,是不知道坏球是重还是轻。不要贸然装大
使用“←”“→”快捷翻页
<span class="count" title="
<span class="count" title="
<span class="count" title="
请遵守言论规则,不得违反国家法律法规回复(Ctrl+Enter)