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

【算法与数据结构】金刚坐飞机问题

阅读更多

文章背景


编程之美 4.1 “金刚坐飞机问题”的问题2,难度比问题1大很多。

编程之美的官方解法,包括原理分析、概率公式、推导过程等,感觉阐述不够详细,没有完全读懂。

搜索一下 “金刚坐飞机”,参考了几个很不错的分析,得到一个自己觉得比较完整的答案。

 

仔细审题

 

首先,仔细审题,有两个细节需要搞清楚:

 

  1. 飞机上总共有多少座位?N?N+1?还是更多?从问题1的官方解答看,飞机上座位总数为N。
  2. “...乘客们正准备按机票编号(1,2,3...N)依次排队登机。突然来了一只大猩猩(对,他叫金刚)。他也有飞机票,但是...”,金刚的机票编号是否属于闭区间[1,N]?换句话说,所有乘客(包括金刚)的总数是N还是N+1?既然座位总数为N,金刚也有飞机票,飞机也不可能超载,因此,所有乘客(包括金刚)的总数为N。金刚的机票编号也属于闭区间[1,N]。
 

 

推敲官方答案

 

然后,看一下编程之美的官方答案:第i个乘客坐在自己位置上的概率为 
 。
既然飞机座位总数为N,根据官方答案,第1个乘客的概率为。实际上,第1个乘客的概率应该为。计算过程如下:
根据全概率公式,第1个乘客坐在自己座位上的概率:


 
如何解释这个问题呢?从问题2的官方解答过程“如果n=1或n>i,那么第i个乘客坐在自己位置上的概率为1....”可以推测,官方认为金刚的机票编号为1。官方答案中的i应该不包括1。

 

重新描述问题

 

到这里,我重新描述一下问题:
飞机上有N个座位,座位编号依次为1,2,..N。恰好有N个乘客排队登机,第1个乘客的座位编号是1,第2个乘客的座位编号是2,...,第N个乘客的座位编号是N。每个乘客都应该坐在编号正确的座位上。但是,第1个乘客是不讲道理的金刚,他第一个进入飞机,随便(随机)挑了一个座位坐下。其他乘客敢怒不敢言,只好依次找座位坐下。如果自己的座位没有被占,则坐自己的作为,否则,也像金刚那样随便挑一个座位。现在,求第i个乘客(第1个乘客还是金刚)坐到自己座位的概率是多少?
我算出的答案为:


 
与官方答案是一致的,但是本文会给出更加详细的计算过程。

 

概率计算过程

 
下面描述计算过程。
令P(i)表示,第i个乘客坐到座位i的概率。
金刚的座位明明是空的,他还要随便占位;其他乘客只有在自己座位被占的情况下,才随便坐。因此,金刚与其他乘客的行为并不相同,需要分开计算。
 

先计算金刚的概率

 
显然,P(1)就是金刚坐在1号座位的概率。金刚是第一个随便挑座位的,因此概率为

 

再计算其他乘客的概率

核心工具是全概率公式

 
第2~N个乘客的概率不容易看出,我们根据全概率公式来计算,条件为金刚坐在编号为j的座位上:
,其中:
  • P(K=j)表示,金刚坐在座位j的概率
  • P(i|K=j)表示,在金刚坐在座位j上的情况下,第i个乘客坐在座位i的概率
显然,金刚坐在位置j的概率均等,都是
条件概率P(i|K=j)的计算不太直观,我们先简单分析一下:
  1. 如果j=1,也就是说金刚居然坐在了自己的座位上,第i个乘客(其实是所有其他乘客)必然能够坐到自己座位,因此P(K=j) = 1。
  2. 如果j=i,也就是说金刚居然坐在了第i个乘客的座位上,第i个乘客肯定不能坐到自己座位,因此P(K=j) = 0。
  3. 如果j>i,也就是说,金刚坐了(第i个乘客)后面的座位,不影响前面乘客找座位,第i个乘客(其实是第2~j-1个乘客)必然能够坐到自己座位,因此P(K=j) = 1。
  4. 如果1<j<i,也就是说,金刚抢了(第i个乘客)前面的座位,肯定会影响第i个乘客(其实是第j~N个乘客)的座位。
因此,可以初步计算:

这时,只需要计算最后一个条件概率
 

难点是计算条件概率

可以依次计算P(i|K=i-1),P(i|K=i-2),...,P(i|K=2),发现他们的值都为,神奇吧!
最终结果:

 

自顶向下计算条件概率

 

那么,1<j<i时,P(i|K=j)到底是怎么计算的呢?下面详细推导一下j=i-1和j=i-2这两种情况,其他情况可以顺推。

如果金刚坐在了座位i-1上,第i-1个乘客可以选择座位1、i、i+1~N。每种选择的概率均等,为1/(N-i+2):

 

  1. 如果第i-1个乘客选择座位1,则第i个乘客必然能坐到自己座位,概率为1
  2. 如果第i-1个乘客选择座位i,则第i个乘客必然不能坐到自己座位,概率为0
  3. 如果第i-1个乘客选择座位i+1~N,则第i个座位必然能坐到自己座位,概率为1
根据全概率公式,有
如果金刚坐在了座位i-2上,第i-2个乘客可以选择座位1、i-1、i~N。每种选择的概率均等,为1/(N-i+3):

 

  1. 如果第i-2个乘客选择座位1,则第i个乘客必然能坐到自己座位,概率为1
  2. 如果第i-2个乘客选择座位i-1,则第i-1个乘客的选择将影响第i个乘客的概率。此种情况恰好可以递归到P(i|K=i-1),只要假设第i-2个乘客就是金刚,它坐在了座位i-1上
  3. 如果第i-2个乘客选择座位i,则第i个乘客必然不能坐到自己座位,概率为0
  4. 如果第i-2个乘客选择座位i+1~N,则第i个座位必然能坐到自己座位,概率为1
根据全概率公式,有

 

如果继续计算下去,其实可以发现规律,
  

挖掘递归现象

 

其实,从上述推导的过程中,我们已经发现递归的迹象,是否可以再深入挖掘一下递归公式,进而避免繁琐的推导呢?

如果金刚坐在了座位j上,那么第j个乘客将会在座位1、j+1~N中随即选择一个座位。此时,乘客数量变成N-j+1,座位的数量也是N-j+1,第j个乘客恰好是剩余乘客的第1个,他变成了新的金刚。我们把他的座位编号从j换成1,这个变换不会影响问题的答案。下面我们来证明这个变换的安全性。

这个变换肯定会影响第j个乘客的概率,但是我们要计算的 并不包括第j个乘客,所以不用考虑这个影响。对于第2~i-1个乘客而言,如果第j个乘客无论是坐在1还是j,他们都可以坐在自己的座位上,对他们来说没有区别,对他们的概率也没有任何影响。因此,这个变换是安全的。

 

从问题的形式上看,变换之后的问题,与原问题等价,只是问题规模从N减小到N-j+1,且每位乘客的编号减小(j-1),座位编号也减小(j-1)。下面详细描述新问题:

飞机上有N-j+1个座位,座位编号依次为1,2,..N-j+1。恰好有N个乘客排队登机,第1个乘客的座位编号是1,第2个乘客的座位编号是2,...,第N-j+1个乘客的座位编号是N-j+1。每个乘客都应该坐在编号正确的座位上。但是,第1个乘客是不讲道理的金刚,他第一个进入飞机,随便(随机)挑了一个座位坐下。其他乘客敢怒不敢言,只好依次找座位坐下。如果自己的座位没有被占,则坐自己的作为,否则,也像金刚那样随便挑一个座位。现在,求第i个乘客(第1个乘客还是金刚)坐到自己座位的概率是多少?

 

利用递归形式计算条件概率

 

这里引入了一个新的变量n,表示乘客的总数。我们令F(i,n)表示在乘客总数为n的情况下,第i个乘客坐到自己座位的概率。显然,P(i) = F(i,N)。

下面,我们开始计算F(i,n),首先将P(i,N)计算结果中的N替换成n,然后利用子问题的递归形式。




 
 因此,我们有



 
 

结合金刚的概率,我们得到完整答案:

 

 

参考文献率

 
编程之美4.1节,P263~266
【编程之美】金刚坐飞机问题 - python27 - 博客园 http://www.cnblogs.com/python27/archive/2012/04/08/2438009.html
编程之美笔记——金刚坐飞机 - Parnasse的专栏 - 博客频道 - CSDN.NET http://blog.csdn.net/FlyingIceCS/article/details/6007735
  • 大小: 7 KB
  • 大小: 5.5 KB
  • 大小: 739 Bytes
  • 大小: 737 Bytes
  • 大小: 6.1 KB
  • 大小: 5.2 KB
  • 大小: 1.2 KB
  • 大小: 8.4 KB
  • 大小: 17.3 KB
  • 大小: 838 Bytes
  • 大小: 913 Bytes
  • 大小: 1.4 KB
  • 大小: 7.9 KB
  • 大小: 3.9 KB
  • 大小: 3 KB
  • 大小: 1.2 KB
  • 大小: 1.9 KB
  • 大小: 919 Bytes
  • 大小: 1.6 KB
  • 大小: 20.5 KB
0
1
分享到:
评论
2 楼 jarfield 2013-02-19  
skysbird 写道
多谢兄弟的讲解,总算看明白了。

不过兄弟推倒公式最后一步有个笔误。

应该是
n*F(i,n) = n-i+1+(i-2)*F(i,n)


兄弟看的真仔细,已经修改,多谢!
1 楼 skysbird 2013-02-17  
多谢兄弟的讲解,总算看明白了。

不过兄弟推倒公式最后一步有个笔误。

应该是
n*F(i,n) = n-i+1+(i-2)*F(i,n)

相关推荐

    经典算法,当然是经典了

    另一个标签“金刚坐飞机”可能是指优先级队列问题,或者更具体地说,是“大亨上飞机”问题。这个问题模拟了飞机座位分配的场景,乘客有不同等级的优先级,我们需要确保高优先级的乘客先上飞机。这涉及到优先级队列...

    微软近几年的面试题目汇总

    例如,“金刚坐飞机问题.pdf”可能会是一个关于操作系统原理或并发控制的问题,通过这些问题,微软希望能够评估应聘者对计算机基础知识的掌握程度,以及是否具备扎实的理论基础。 当然,所有的面试题目最终都是为了...

    微软亚洲研究院经典面试题

    8. **金刚坐飞机问题.pdf**:这可能是一个组合优化问题,如旅行商问题(TSP)的变种,可能需要用到贪心算法、回溯搜索或近似算法来求解。 9. **1的数目.pdf**:这是一道位操作的题目,涉及到二进制表示和位运算,如...

    微软面试心得经典 降低分数

    其次,"金刚坐飞机问题"可能涉及到逻辑思维和问题解决能力。这可能是一个关于有限资源分配的问题,例如,如果飞机上只有一定数量的座位,而乘客有不同的重量和优先级,如何合理安排使得飞机的载重达到最优。解决这类...

    scratch少儿编程逻辑思维游戏源码-城堡战争.zip

    scratch少儿编程逻辑思维游戏源码-城堡战争.zip

    【Go语言编程】大厂Go工程师面试题集锦:涵盖并发、网络、数据库及算法设计要点

    内容概要:本文档汇集了来自字节跳动、腾讯、金山WPS、跟谁学和百度等大厂的Go工程师面试题,涵盖广泛的技术领域。主要包括Go语言特性(如goroutine调度、channel机制)、操作系统(进程间通信、线程调度)、计算机网络(TCP/IP协议栈、HTTP协议)、数据结构与算法(排序算法、LRU缓存)、数据库(MySQL索引优化、Redis内部机制)、分布式系统(负载均衡、服务发现)等方面的知识点。通过这些问题,不仅考察应聘者的理论基础,还测试其实际项目经验和技术深度。 适合人群:有一定Go语言编程经验和计算机基础知识的开发者,特别是准备应聘互联网大厂的中级及以上水平的后端工程师或全栈工程师。 使用场景及目标:①帮助求职者全面复习Go语言及其相关领域的核心概念;②为面试官提供有价值的参考题目,确保候选人具备解决复杂问题的能力;③指导工程师深入理解并掌握企业级应用开发所需的关键技能。 阅读建议:由于题目覆盖面广且难度较高,建议读者结合自身情况选择重点复习方向,同时配合实际编码练习加深理解。对于每个知识点,不仅要记住答案,更要理解背后的原理,这样才能在面试中灵活应对各种变体问题。

    scratch少儿编程逻辑思维游戏源码-堡垒之夜(吃鸡游戏).zip

    scratch少儿编程逻辑思维游戏源码-堡垒之夜(吃鸡游戏).zip

    少儿编程scratch项目源代码文件案例素材-派.zip

    少儿编程scratch项目源代码文件案例素材-派.zip

    scratch少儿编程逻辑思维游戏源码-Scratch 冒险.zip

    scratch少儿编程逻辑思维游戏源码-Scratch 冒险.zip

    2025 飞特舵机, Arduino版本

    2025 飞特舵机, Arduino版本

    scratch少儿编程逻辑思维游戏源码-躲避.zip

    scratch少儿编程逻辑思维游戏源码-躲避.zip

    PFC5.0纤维混凝土三点弯曲模拟:参数化建模与实验分析

    内容概要:本文详细介绍了利用PFC5.0进行纤维混凝土三点弯曲模拟的方法。首先,作者展示了如何通过定义纤维的体积含量、长度、半径和刚度等关键参数来构建纤维网络。接着,描述了三点弯曲加载的具体实现方式,包括加载速率控制和终止条件设定。最后,提供了后处理方法,如绘制并导出力-位移曲线图,以便于分析材料破坏机制。文中还给出了若干实用建议,如纤维半径的选择范围、加载速率的初始值以及不同类型纤维的接触模型选择。 适合人群:从事材料科学尤其是混凝土材料研究的专业人士,以及对离散元法和数值模拟感兴趣的科研工作者。 使用场景及目标:适用于希望深入了解纤维混凝土力学性能的研究人员,旨在帮助他们掌握PFC5.0软件的操作技巧,优化模拟参数设置,提高实验效率。 其他说明:文中提供的代码片段可以直接应用于实际项目中,同时附带了一些实践经验分享,有助于初学者快速入门并避免常见错误。

    少儿编程scratch项目源代码文件案例素材-生存V1(有BAG).zip

    少儿编程scratch项目源代码文件案例素材-生存V1(有BAG).zip

    少儿编程scratch项目源代码文件案例素材-披萨机器人.zip

    少儿编程scratch项目源代码文件案例素材-披萨机器人.zip

    少儿编程scratch项目源代码文件案例素材-气球滑雪板.zip

    少儿编程scratch项目源代码文件案例素材-气球滑雪板.zip

    少儿编程scratch项目源代码文件案例素材-使命召唤(苏联插旗).zip

    少儿编程scratch项目源代码文件案例素材-使命召唤(苏联插旗).zip

    可跨平台移植的模拟IIC实战项目STM32F407-TestIIC

    1. GPIO模拟I2C 实战项目,根据正点原子 STM32F407ZGT6 进行更改; 2. 可适配STM32、GD32、HC32等MCU;

    scratch少儿编程逻辑思维游戏源码-百米冲刺.zip

    scratch少儿编程逻辑思维游戏源码-百米冲刺.zip

    【蓝桥杯竞赛】历年试题精选与备考资源汇总:编程算法及硬件单片机试题解析与练习指导

    内容概要:本文档汇总了蓝桥杯历年试题及练习资源,涵盖编程类试题精选、硬件与单片机试题、练习资源与题库以及备考建议。编程类试题精选包括基础算法题(如数组求和、质因数分解)、经典算法案例(如最大子序列和、兰顿蚂蚁模拟)和数据结构应用(如字符全排列)。硬件与单片机试题主要涉及客观题考点,如BUCK电路和电源设计。练习资源与题库部分介绍了真题平台(如Dotcpp、CSDN专题)和专项训练包(如Python题库、Java百题集、C++真题解析)。备考建议分为分阶段练习(新手阶段、进阶提升)和模拟实战(如使用Dotcpp估分系统进行限时训练),强调按年份和组别分类练习,强化代码实现与调试能力。; 适合人群:准备参加蓝桥杯竞赛的学生及编程爱好者。; 使用场景及目标:①针对不同编程语言和难度级别的题目进行专项训练;②通过历年真题和模拟实战提高解题速度和准确性;③掌握算法设计、数据结构应用及硬件基础知识。; 阅读建议:此文档提供了丰富的试题和练习资源,建议根据自身水平选择合适的题目进行练习,并结合真题平台的估分系统和社区开源代码进行对比优化,逐步提升编程能力和竞赛水平。

    30kW储能PCS原理图设计:量产设计的关键要素与优化策略

    内容概要:本文详细介绍了30kW储能PCS(电力转换系统)原理图的设计要点及其量产化过程中需要注意的技术细节。首先阐述了储能PCS的基本概念和重要性,接着深入探讨了主拓扑结构的选择,特别是双级式结构的优势以及关键组件如IGBT的驱动时序配置。随后讨论了控制算法的智能化改进,包括加入前馈补偿以提高系统的稳定性。此外,还强调了EMC设计、PCB布局、元件选择等方面的注意事项,并分享了一些实际生产中遇到的问题及解决方案。最后提到了自动化测试方法和散热管理策略,确保产品在各种环境下的可靠运行。 适合人群:从事储能系统设计、电力电子产品研发的工程师和技术人员。 使用场景及目标:帮助读者掌握30kW储能PCS从原理图设计到量产实施的全流程关键技术,提升产品的性能和可靠性,避免常见错误。 其他说明:文中提供了具体的代码片段和实践经验,有助于理解和应用相关理论。

Global site tag (gtag.js) - Google Analytics