首页 > 编程语言 >编程基础(1)- 问题 (一) | 12 个小球称重找出其中 1 个坏球

编程基础(1)- 问题 (一) | 12 个小球称重找出其中 1 个坏球

时间:2022-09-30 13:35:38浏览次数:56  
标签:11 12 天平 坏球 可能性 个球 称重

 

1. 问题

    有 12 个 外观完全一样的小球,其中有 1 个求的重量和其它 11 个球不一样(或称为坏球),但是不知道是轻还是重。现在你有一架天平,只能称 3 次。你怎么找出这 12 个球中重量不同的那 1 个球,并指出这个球是轻还是重?

2. 分析

    破解问题前提:

        (1) 解决问题的基础是充分理解问题;
        (2) 要在可能性的边界之内做事,才会有成效;
        (3) 消除不确定性的根本在于获得信息;
        (4) 要学会科学的试错方法。

    1) 读懂问题

        这个问题中隐含三点重要的信息:

            (1) 这个问题不是说有 11 个好球和 1 个坏球,而是 12 个球每个球都有可能是好球或者坏球,在最终确定答案之前,每个球都可能有问题。

            (2) 这个问题的本质其实是 24 选 1。

                24,就是指12个球,每个球2种可能性,一共24种可能性。分别是:第1个球轻,或者第2个球轻,……,直到第12个球轻,这是前12种;同样的,还有另外12种,第1个球重,或者第2个球重,……,直到第12个球重。我们将这些可能性简写成1轻,2轻,……,12轻;1重,2重,……,12重。

                最终我们要找到哪个球是坏球,它是轻是重,这个问题就变成了:有 24 种可能性,我们如何排除掉其中的 23种,最终留下 1 种。

            (3) 关键信息是关于天平,有人想到天平,就觉得它只能告诉我们哪边轻哪边重。但实际上用天平称重,每一次可能会产生三种结果:左边轻,左边重,或者两边相等。要注意两边相等也是一条信息。

                一次天平称量能够产生的信息量就是一个三进制数位,英文里叫1吹特(trit),可以对应于二进制的1比特(bit)。我们这里分别用 “<”、“>” 和 “=” 这三个符号来表示这三种结果。

        把这三层意思读出来,才算是读懂了这道题给出的条件,读懂了题目,解题就不难了。

    2) 确定边界和消除不确定性

        这道 12 球问题的边界在哪里?

        要消除不确定性,所需要的东西就是信息。这个问题实际上是 24 选 1;又知道了每一次用天平称量,最多能得到 1 吹特的信息,称三次最多就能得到3位三进制的信息。

        3 位三进制,对应的就是 3x3x3=27 种可能性,题目要求我们分辨的是 24 种可能性,27 > 24,所以这道题是可能有解的。这就是确认了在边界内做事。

        接下来要留意,如果某一步之后超出了边界,那后面的路就不可能走通了。这一点是解题的关键,也是指导我们往下解题的准则。在我们的解题方案中,每称一次必须获得一个三进制的信息,否则这个问题是解决不了的。

        这里可以看一个经典的错误做法:很多同学第一次称球是把 1-6 放在天平左边,7-12 放在右边。但这样做结果只可能是左边重或者右边重,不可能出现两边平衡的情况,因为有一个坏球存在,那么我们只能得到一个二进制信息。不论左边重还是右边重,可能性都是从 24 种变成了 12 种。如果 1-6 这边轻,那么可能性就是 1轻、2轻、……、6轻,或者7重、8重、 ……、12重,一共12种可能性。反过来也是一样。

        而此时只剩下 2 次称量机会,最多只能得到 3x3=9 种可能性,9 < 12 种,这就是越过了边界,是不可能成功的。

 

3. 解题

    怎么运用科学试错方法?         
    
    现在我们有了理论的指导,知道了每次称量都必须要获得一个三进制的信息。

    1) 第一步

        我们将 12 个球分为三组,1-4,5-8 和 9-12 各一组,然后把前两组放到天平两侧上去称量。这样我们就有可能得到 <、= 或者 > 三种情况,这三种情况不论是哪一种,在各自的结果下都只剩下 8 种可能性要排除。逻辑图如下:


        我们可以把这三种情况下各自的 8 种可能性列举出来:

            (1) 如果是左边轻,就剩下 1轻~4轻,5重~8重这 8 种可能性;
            (2) 如果平衡,就剩下 9轻~12轻,9重~12重这 8 种可能性;
            (3) 如果是左边重,就剩下 1重~4重,5轻~8轻这 8 种可能性;

        这一步走对了,接下来就会减少很多不必要的试错。

    2) 第二步

        我们分别来处理这三种可能性。

        (1) 天平平衡,即 “=” 的情况

            先说简单的一种,“=” 的情况,也就是天平两边相等,那我们就知道了,1-8球都是好球,坏球一定在9-12号这四个球当中,每个球有轻重两种可能性,一共就是8种。
        
            我们就要继续把8种可能性缩小。如果不知道我们前面的理论,很有可能出现的一种错误做法就是把9-12四个球平分成两组来称,但这样称的结果一定是一边高一边低,又是只有二进制的信息,显然是错误的道路。

            正确的做法是什么呢?
        
            把8种可能的情况列举出来:有9轻~12轻,9重~12重。然后利用“三进制”信息能将可能的情况除以3的特点,将8种情况分为三组,分别是3种、3种、2种。

            另外我们这时还有一个可以利用的信息,就是经过第一次称量我们已经知道了1-8号球都是好的。因此第二次称重时,可以利用这些好球,把1-3三个好球放在天平的一边,把可能是坏球的9-11放在天平的另一边去称。

            称的结果有三种:9-11轻,9-11重和平衡。

            如果平衡,就说明9-11都是好球,坏球就是12,但还有12轻和12重2种可能性,拿12和任意一个好球再称一次就能得出答案了。

            如果不平衡,是9-11轻或者9-11重,各自就再对应3种可能性。比如9-11轻,剩下的可能性就是9轻、10轻、11轻,把9和10再称一下,如果平衡,就是11轻;如果不平衡,哪边轻哪边就是坏球。9-11重也是同理。

        (2) 天平平衡,即 “>” 或 "<" 的情况

            我们以左边这一组轻来说明,如果是左边重,方法也是对称的。

            如果左边轻意味着什么?意味着有8种可能性:要么是坏球在1-4这边,坏球是一个轻球,对应1轻-4轻4种情况;要么是坏球在5-8那边,是一个重球,对应5重-8重4种情况。一共8种。

            接下来这一步很关键,我们必须通过称一次,把8种可能性变成3-3-2三组。如果达不到这个目的就是盲目试错。这一步具体的做法有好几种,道理上大同小异,我讲其中的一种。下面这段分析我推荐你对着文稿中的逻辑图来听。

            怎样把1轻-4轻、5重-8重这8种情况分成3、3、2呢?

            一个办法是,将1、2这两个可能的轻球,加上确定是好球的9放在天平的左边,把3、4两个可能的轻球,加上可能的重球5放在天平的右边进行称量。

            这次称量之后,有A,B,C三种情况,我们对照逻辑图来看:

                情况A:1、2、9这边轻,说明可能的情况是1轻、2轻和5重,这三种情况可以再称一次就确认最终答案。
                
                情况B:1、2、9和3、4、5平衡了,说明可能的情况是6重、7重、8重,接下来也是再称一次就可以得到答案。

                情况C:1、2、9这边重,说明1、2都不是轻球,同时天平右边的5也一定不是重球,只能是天平右边的3和4当中有一个是轻球,导致了1、2、9会比3、4、5重。那么再称一次,找到究竟是3轻还是4轻,就得到了最终答案。

            总之,只要在第二次称的时候,能够把8种可能性再分成3+3+2种可能性,接下来再称一次问题就肯定解决了。因为最多也无非是3种可能性,称1次必然会得到结果。

    在这个过程中,恪守一个原则,就是每称一次,就把可能的情况除以了 3,否则下一步就会完成不了任务。而这个原则,是靠前面的确定边界和用信息消除不确定性的方法得到的。凭借一个合理、合逻辑的思路往前走,这就是科学试错的方法。

4. 总结

    读懂题目、确定边界、用信息消除不确定性、科学试错,这些具体的方法共同构成了一个系统性的方法论,这就提醒了我们系统性学习的重要性。

    作为一个普通人,我们在面对未知的难题时,只有对自己运用的方法有系统性的了解,对自己的方法有清晰的理解和把握,才有可能解决这个未知的难题。如果对题目也不了解,对自己使用的方法也不了解,那就是盲目行事,即使能碰运气碰出结果,效率也非常低。


标签:11,12,天平,坏球,可能性,个球,称重
From: https://www.cnblogs.com/tkuang/p/16744607.html

相关文章

  • EN12277与ASTM F1772攀岩安全带安全标准
     如何提交信息如果亚马逊与您联系,要求您提供合规文件,请按照以下步骤提交所需信息:1.在卖家平台中,选择【绩效】选项卡,然后选择【账户状况】。2.在页面右下角的【商品合规性请......
  • EN 892:2012+A1:2016亚马逊登山绳安全要求
    攀岩绳是与攀岩安全带和锚点(例如:墙壁、岩壁或山壁)相连的一件器械。攀岩绳用于防止攀岩者坠落。攀岩绳通常由长捻纤维芯和编织彩色纤维外护套组成。产品示例亚马逊美国站安......
  • 关于Mysql [ERR] 1118 - Row size too large (> 8126)解决方法
    Mysql版本:8.0系统:win10错误描述:[ERR]1118-Rowsizetoolarge(>8126).ChangingsomecolumnstoTEXTorBLOBorusingROW_FORMAT=DYNAMICorROW_FORMAT=COMP......
  • Xmind 2022 最新版本 Xmind 2022 for mac(思维导图软件)v12.0.3永久版
    Xmind2022forMac是一款非常便捷的制作思维导图的软件,它有非常丰富的模板可以使用,制作思维导图可以帮助用户更高效的进行学习,理清相关学习内容的思路和大体框架,用户可以......
  • CF1286E
    考虑在每次加入一个字符后,求出所有合法后缀(即border)的权值和。容易想到用KMP算法解决。具体的,我们维护border的集合。加入一个字符\(c_i\)后,对集合的改变为:如果......
  • WEB自动化-12-Cypress 调试
    12调试  Cypress的测试代码和被测试程序在同一生命周期中的浏览器中,也就是意味着,可以使用浏览器的开发者工具直接参与调试。Cypress提供了几种调试方法,分别为:debugge......
  • 前端面试总结12-WebApi-存储
    简述cooki,localstorage,sessionstorage的区别(1:cookie数据存放在浏览器上,session存放在服务器上(2:cookie安全性低(3:session占用服务器性能(4:单个cookie最大存储数据不超过4k......
  • com.panie 项目开发随笔(NoF)_环境搭建(2016.12.29)
    (一)最近做的框架一直在spring+springmvc+mybatis的基础上,使用框架的好处自然是简化了自己的开发工作,定义好大的结构体系后就在里面套用方法了!可是框架的毛病......
  • 又到月底了,希望大家12月份一切都顺心
    首先声明小编本身不喜欢被灌鸡汤,但当我看到这段视频的时候,小编我真的热血沸腾,因此也把这段视频分享给大家,与大家共勉。最后小编想和大家分享《牧羊少年奇幻之旅》的一句话:只......
  • 12. HTML-- 表单:<form>标签
    1.前言当您想要通过网页来收集一些用户的信息(例如用户名、电话、邮箱地址等)时,就需要用到HTML表单。表单可以接收用户输入的信息,然后将其发送到后端应用程序,例如PHP、J......