`
kmplayer
  • 浏览: 508867 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

称球问题

 
阅读更多
[节选]http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/
1,问题:
12个小球,其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。

2,分析:
(1)坏球可能是12个球中的任意一个,这就是12种可能性;而其中每种可能性下坏球可能轻也可能重。于是“坏球是哪个球,是轻是重”这个问题的答案就有12×2=24种可能性。
(2)现在我们用天平来称球,就等同于对这24种可能性发问,由于天平的输出结果有三种“平衡、左倾、右倾”,这就相当于我们的问题有三个答案,即可以将所有的可能性切成三份。
注:天平的输出有三种结果,相当于一次又log3的信息量。
(3)我们应当尽量让这三个分支概率均等,即平均切分所有的可能性为三等份。如此一来的话一次称量就可以将答案的可能性缩减为原来的1/3,三次就能缩减为1/27。而总共才有24种可能性,所以理论上是完全可以3次称出来的。
3,举例:
为了更清楚的看待这个问题,我们不妨假设有6个球,来考虑一下3、3称和2、2称的区别:
(1)在未称之前,一共有12种可能性:1轻、1重、2轻、2重、…、6轻、6重。现在将1、2、3号放在左边,4、5、6放在右边3、3称了之后,不失一般性假设天平左倾,那么小球的可能性就变成了原来的一半(6种):1重、2重、3重、4轻、5轻、6轻。即这种称法能排除一半可能性。
(2)现在再来看2、2称法,即1、2放左边,3、4放右边,剩下的5、6不称,放一边。
下面是问题的本质
假设结果是天平平衡,那么可能性剩下——4种:5重、5轻、6 重、6轻。
假设天平左倾,可能性也剩下4种:1重、2重、3轻、4轻。(5和6肯定被排除了)
右倾和左倾的情况类似。
总之,这种称法,不管天平结果如何,情况都被我们缩小到了原来的三分之一!
我们充分利用了“天平的结果状态可能有三种”这个条件来三等分所有可能性,而不是二等分。

4,问题的解决方案:
MacKay在他的书《Information Theory: Inference and Learning Algorithms》里面4.1节专门讲了这个称球问题,还画了一张不错的图

注:图中“1+”是指“1号小球为重”这一可能性。一开始一共有24种可能性。4、4称了之后不管哪种情况(分支),剩下来的可能性总是4种。这是一个完美的三分。然后对每个分支构造第二次称法,这里你只要稍加演算就可以发现,分支1上的第二次称法,即“1、2、6对3、4、5”这种称法,天平输出三种结果的可能性是均等的(严格来说是几乎均等)。这就是为什么这个称法能够在最坏的情况下也能表现最好的原因,没有哪个分支是它的弱点,它必然能将情况缩小到原来的1/3。
分享到:
评论

相关推荐

    称球问题分析

    ### 称球问题分析 #### 一、问题背景与目标 称球问题是一个经典的逻辑推理题目,主要涉及如何通过最少次数的称重来找出不同重量的球。在本篇文章中,我们将围绕“12个球”这个特定场景进行深入探讨。 #### 二、...

    称球问题的分析及算法设计1

    《称球问题的分析及算法设计》 称球问题是一个典型的智力挑战,旨在考察逻辑推理和算法设计能力。本文深入探讨了如何通过三次称量找出12个球中的唯一一个重量异常(轻或重)的球。问题的核心在于利用天平的平衡原理...

    称球问题1

    这个问题是经典的称球问题,属于逻辑推理和优化算法的范畴,常见于智力竞赛或面试题。目的是在有限的称量次数内找出一个不同重量的球(假设较重或较轻),并确定其重量状态。在这个特定的问题中,我们有12个外表相同...

    称球问题一般解法.docx

    称球问题是一个经典的逻辑与数学问题,涉及到信息理论和递归策略。问题的核心是通过有限次的天平称量,从一堆球中找出唯一的异常球(可能是轻的或重的),并确定其重量状态。这个问题有多种变形,但基本思路是通过...

    两类_称球问题_的统一非序列解1

    【两类“称球问题”的统一非序列解】指的是在解决称球问题的两种不同版本时,采用非序列方法的一种通用算法。称球问题通常是指在一组看起来相同的球中,找出一个重量不同的球(轻球或重球),并确定其重量是比其他球...

    “称球问题”的算法的研究1

    【“称球问题”的算法研究】 “称球问题”是一个经典的数学和计算机科学问题,它涉及到在一组外表相同但重量不同的球中,如何通过最少的次数利用无砝码的天平找出唯一的“异类球”。这个问题具有广泛的实际应用,...

    两类“称球问题”的统一非序列解1

    【称球问题】,也被称为【伪币问题】,是一个经典的数学问题,最早由Dyson在1946年提出。这个问题的核心是通过一系列天平称量来确定一组球中哪个是不同的(轻或重),并且找出它的具体重量。在不同版本的问题中,...

    称球问题的解决方法_司德谭1

    称球问题是一个经典的逻辑与算法问题,其目标是在有限次称量中找出唯一一个重量不同的球,这个球要么比其他球轻,要么比其他球重。在这个问题中,我们使用一个没有砝码的天平来比较球的重量。关键在于巧妙地分组和...

    称球问题的一个启发式规则_杨云1

    【称球问题】是一个经典的智力游戏,涉及到使用一个无法编码的天平来找出一组外观相同但质量不同的球。目标是在尽可能少的称量次数中确定哪个球是次品(轻或重),并判断其相对于其他球的重量。该问题通常涉及m个球...

    2. 快速排序里的学问:再看看称球问题1

    然而,这里的"快速排序里的学问:再看看称球问题1"并不是在讨论快速排序算法,而是用快速排序的思想来解决一个经典的智力问题——称球问题。 称球问题是一个逻辑推理问题,给定12个外观相同的球,其中一个是坏球,...

    称13球问题

    13球非独立的称三次,找到次品球(外形与正品相同,偏轻偏重不知),并知道是偏轻还是偏重。DevCpp4.9上运行通过。

    称球问题(包含一个细致的手稿分析和c++代码仿真.zip

    "称球问题"是一个经典的算法问题,通常出现在计算机科学和数学的范畴中,涉及到逻辑推理和最优化策略。这个问题的基本设定是:你有一堆外观完全相同的球,其中有一个球的重量与其他的不同,可能是轻了或者重了。你...

    称球问题的解法

    各种称球问题的分析,还有给出结论,能让你在O(1)时间内解决称球问题!

    六年级奥数专题讲解称球问题.pdf

    六年级奥数专题讲解称球问题.pdf

    天平称球中的信息论.doc

    《天平称球中的信息论》探讨了利用信息论的方法解决经典的天平称球问题,这是一个涉及信息获取和处理的智力挑战。在这个问题中,我们有一组m个球,其中只有一个球是次品,可能是较重或较轻,目标是通过n次天平称量找...

    【原创】12球问题

    12球问题,又称为12个球找问题球问题,是一个经典的逻辑推理题。问题通常描述如下:在12个外观完全相同的球中,有一个是质量有问题的球,可能是比其他球重也可能是轻,现在只允许使用一个天平(无砝码)进行若干次...

    十二个球称一个重

    在IT领域,尤其是在编程与算法设计中,“十二个球称一个重”是一个经典的逻辑问题,旨在测试和提升解决者在数组处理、循环控制、条件判断等方面的能力。此问题的背景通常设定为:有12个外观完全相同的球,其中11个...

    ball_天秤称球----12个球中1个异常_

    标题“ball_天秤称球----12个球中1个异常_”涉及的问题是经典的逻辑与算法问题,通常在编程挑战或者智力游戏中出现。这个问题的目的是在一个包含12个球的集合中找出唯一的一个异常球,这个异常球可能是比其他球重或...

    小升初奥数“310”个必备知识点总结.doc

    一、称球问题 称球问题是奥数中的一个重要专题,旨在训练学生的逻辑思维和推理能力。这类问题通常涉及到如何通过最少次数的称量找出与众不同的球。例如: 1. **例1**:4堆4个球,1堆次品(11克),其余正品(10克...

    创意思维训练第十二讲称球.ppt

    【创意思维训练第十二讲——称球】的讲解主要涉及如何运用逻辑思维和创意思维来解决实际问题,特别是通过一个具体的实例——找出12个球中的唯一一个与众不同的球,只允许使用无刻度天平进行三次称量。这个问题展现了...

Global site tag (gtag.js) - Google Analytics