这个题目很久以前在大学的BBS上发表过解法,现在找不到了,重新写一遍也不费劲。
下面是怎么称14个球(设为A1-A14)。
前提是有多一个标准球A0。
A0-A4 vs A5-A9
如果相等,则坏球在A10-A14这5个球中。
5球(重新记做A1-A5外加一个A0为标准球)的称法如下:
A0,A1 vs A2,A3
如果相等,则坏球是A4或A5,取其中一个与A0再称一次即可判断(这个不用说了,人人都知道怎么称)。
如果不等,假设A0,A1 > A2,A3(<的话,下面的判断都反一反即可),则再称一次:
A2 vs A3
如果相等,则坏球是A1,否则A1就是好球,坏球在A2、A3中,根据上一次称量结果可以判断出,坏球比标准球轻,所以A2 vs A3的结果,轻的那个就是坏球。
如果第一次称量不等,则坏球在A1-A9这9个球中,并且你知道一个不等关系,我们假设是A0-A4 > A5-A9(<的话,下面的判断都反一反即可)。
然后测A1,A2,A5 vs A3,A4,A6
如果相等,则坏球在A7,A8,A9中,并且可以推导出其中轻的那个是坏球,再称一次肯定能找出坏的那个。
如果A1,A2,A5 > A3,A4,A6
则坏球在A1,A2,A6中,并且可以推导出A1,A2 > A0,A6
反之坏球在A5,A3,A4中,并且可以推导出A5,A0 < A3,A4
不难看出这两种情况实际是等价的,只需比较两个同处一侧的球就可以判断哪个是坏球了。
如果没有标准球A0的话,那第一次称量就不能5对5了,只能4对4,所以最多只能称13个球。第一次相等的情况跟前面完全一样,如果不等,就是那8个球有问题,比前面的9个还少一个,所以你肯定可以称出来。那么为什么常见的题目都是12球呢?估计最初流传时很少有人真正从理论(信息论)上理解这个题,所以答案都是凑出来的,自然很难做到最优化。
但是如果掌握了理论,这个称球问题就可以推广,比如4次最多可以称量27+14=41个。前提也是你多一个标准球,这样第一次称量就是14 vs 13+1,如果相等,坏球就在剩下的14个里,就转化为了前面描述的14球称量问题。如果不等,则坏球在27个里,通过合理调配,你肯定可以把它们区别成3组分别9个,通过一次称量判断出坏球到底是在哪9个球中。因为一次称量有3种状态,可以把一堆球分成3组。以下每次都是3组1分,所以27=3的3次方就是表示3次称量就可以区分出来了。
不难看出,如果5次的话,可以最多称量27*3+41=122个,以下可以逐级类推,有兴趣的同志可以求出它的公式。
最后是一个思考题,既然可以3个一组分,为什么3次称量只能称14个而不是27个呢?
分享到:
相关推荐
鼠标操作原创…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………...
1.1.6 单链表的插入操作…………………………………………………………3 1.1.7 单链表的删除操作…………………………………………………………3 1.1.8 循环链表…………………………………………………………...
1.2.3已知环境下的自主导航技术………………………………………………3 1.2.4未知环境下的自主导航技术………………………………………………8 1.3地图创建……………………………………………………………………...
asp课件…………………………asp课件…………………………asp课件…………………………asp课件…………………………asp课件…………………………asp课件…………………………asp课件…………………………asp课件……...
我们用ξ=k表示前k-1次均取到黑球,而第k次取到白球,因此Pkqpkkk()(,,)=−−1127571 2 3 ……。 可见ξ服从几何分布。所以Epξ=7/5,Dpξ=(2/7)/(5/7)2=12/25。 例2. 某射击运动员每次射击击中目标的概率为p(0...
电子制作电路,收集网上的文章,整理过的。……………………………………………………
国产软件_密码恢复%…………………………………………………………………………………………………………………………………………………………………………………………………………………………
瀑布雨效果……………………
引 言 …………………………………………………………………………………………6 一、 管理信息系统(MIS)简介 …………………………………………………………6 1. 管理信息系统的概念 ……………………………………...
3-5 PC 之 FTP 軟體操作及設定……………………………………………………3-4 3-6 DATA SERVER 操作簡介…………………………………………………… 3-5 3-7 DATA SERVER [L-GET],[L-PUT],[L-DEL] 及萬用字元“*”...
习 题 ………………………………………………………………………………………… (16) 第2 章 互联网接入方案 ………………………………………………………………………… (17) 2 .1 拨号上网...
3需求分析……………………………………………12 3.1功能需求分析………………………………………………12 3.2非功能需求分析………………………………………………14 3.3经济可行性分析…………………………...
串口调试助手………………
JavaScript日历插件代码………………………………………………………………………………
看吧………… 我们都看着的
windows不可结束进程,当…………太卡时,可看看这个 windows不可结束进程,当…………太卡时,可看看这个 windows不可结束进程,当…………太卡时,可看看这个
小结 ………………………………………………………………………………………… 163 第 C= 与 Web服 努器的交互 … … ¨ ¨ … … … … … … … ¨ … … … … … … … … … 164 61 建立服务器 …¨…¨……...
第一章、绪论…………………………………………………………………………3第二章、自动打铃器的硬件实现……………………………………………………4 第三章、自动打铃器的软件实现…………………………………………...