`
jarfield
  • 浏览: 202637 次
  • 性别: 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

    总之,《算法与数据结构》这门课程涵盖了从问题分析到解决方案实现的全过程,深入探讨了数据的组织和操作,以及如何设计高效的算法。这些知识对于理解和开发计算机程序至关重要,因为正如N. Wirth所提出的,算法加上...

    算法与数据结构考研试题精析

    标题《算法与数据结构考研试题精析》和描述“算法与数据结构历年考研试题分析与答案解析。主要就是拿来练练手”表明本文将深入探讨算法与数据结构的核心知识点,并通过历年考研试题的形式加以练习和巩固。由于提供的...

    算法与数据结构习题答案+课件+参考资料 国防工业出版社 张永 李睿

     本书分为基本概念、简单数据结构(线性表、栈、队列)、复杂数据结构(树、图)和算法与数据结构应用(排序、查找、算法设计基础)四部分,详细介绍了常用数据结构和算法的基本概念及其不同的实现方法,对各种数据...

    算法与数据结构考研试题精析第3版

    《算法与数据结构考研试题精析》收集了自1992年以来国内60余所重点高校和科学院、所300多套硕士研究生入学“算法与数据结构”考试试卷的1600多道试题,并给出了参考答案和分析。《算法与数据结构考研试题精析》可以...

    算法与数据结构学习辅导及习题详解.张乃孝版.

    在计算机科学教育中,算法与数据结构占据着至关重要的地位。它们是构建软件系统的基础,对于培养学生的逻辑思维能力和解决问题的能力起着决定性的作用。张乃孝教授作为该领域的资深专家,在北京大学计算机系教学一线...

    算法与数据结构考研试题精析(第三版)

    《算法与数据结构考研试题精析(第三版)》一书,由陈守孔老师编撰,是一本专注于考研层面的算法与数据结构领域的经典教材与练习册。该书除了包含大量的算法和数据结构知识点讲解外,还提供了1800题的考研试题分析,...

    算法与数据结构

    学习算法与数据结构,不仅可以提高编程技能,还能培养解决问题的逻辑思维。在实际工作中,无论是软件开发、数据分析还是人工智能,都需要用到这些基础知识。因此,对于任何想要深入计算机领域的学习者来说,《算法...

    python数据结构与算法

    python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法python数据结构与算法...

    王晓东_算法与数据结构学习指导与习题解析

    王晓东_算法与数据结构学习指导与习题解析

    算法导论 数据结构与算法 算法与数据结构

    算法导论英文原版,数据结构与算法,算法导论英文原版,数据结构与算法

    算法与数据结构(第3版)--张乃孝 光盘内容

    算法与数据结构(第三版)的光盘内容。自己从光盘上导出来的,打开需要安装office、pdf reader和视频播放器。因为限制的上传文件大小,所以把网盘链接+提取码发上

    算法与数据结构 习题答案共十二套

    《算法与数据结构 习题答案共十二套》是一份包含多套算法与数据结构练习题及答案的资源集合,旨在帮助学习者深入理解和掌握这一关键领域的知识。这份压缩包中包含了十套算法与数据结构的常规习题以及两套模拟试题,...

    算法与数据结构——c语言版+张乃孝

    《算法与数据结构——C语言版》是计算机科学领域中一本经典的教材,由张乃孝编著。这本书深入浅出地介绍了算法和数据结构的基本概念、设计方法以及它们在实际编程中的应用。C语言作为底层且高效的语言,是学习算法和...

    上海交大算法与数据结构课件

    上海交通大学的《算法与数据结构》课程是一门深入探讨计算机科学基础的重要课程,它涵盖了编程领域中的核心概念,为学生提供了高效解决问题的工具。课件采用PPT形式,便于理解和学习,同时也允许用户进行修改和复制...

    武汉大学 C#数据结构与算法

    《武汉大学 C#数据结构与算法》是一门深入探讨计算机科学基础的课程,主要针对C#编程语言,涵盖了数据结构和算法这两个核心概念。在学习这门课程时,你将有机会掌握C#语言如何用于实现高效的数据管理和计算方法。 1...

    微软算法与数据结构面试题答案

    在IT行业中,尤其是在软件开发和数据科学领域,算法与数据结构是至关重要的基础知识。微软作为全球顶级科技公司,其面试过程中对于应聘者在算法和数据结构的理解与应用能力有着较高的要求。本资料集包含了微软面试中...

    浅谈算法与数据结构的关系.pdf

    在计算机专业教学和实际开发中,算法与数据结构的关系是一个关键问题。传统的观点认为,解决一个问题应该先确定适合的数据结构,然后设计相应的算法。然而,这种方法可能导致对算法的考虑不足,从而无法找到最高效的...

    Delphi 算法与数据结构 第四部分

    Delphi经典书籍:Delphi 算法与数据结构 第四部分

    021_《Delphi算法与数据结构》(附书源码)

    《Delphi算法与数据结构》是一本专注于使用Delphi编程语言深入探讨算法和数据结构的教程。这本书由热心网友邦整理并提供了配套的源代码,旨在帮助读者在实践中理解和掌握这些核心计算机科学概念。 首先,我们要理解...

    算法与数据结构_严蔚敏版

    算法与数据结构严蔚敏版,经典阐述算法以及数据结构

Global site tag (gtag.js) - Google Analytics