【编程之美】金刚坐飞机问题

金刚坐飞机问题

问题:

现在有一班飞机将要起飞,乘客们正准备按机票号码(1, 2, 3, …N)依次排队登机。突然来了一只大猩猩(对,他叫金刚)。他也有飞机票,但是他插队第一个登上了飞机,然后随意地选了一个座位坐下了1。根据社会的和谐程度,其他的乘客有两种反应:

1. 乘客们都义愤填膺,“既然金刚同志不遵守规定,为什么我要遵守?”他们也随意地找位置坐下,并且坚决不让座给其他乘客。

2. 乘客们虽然感到愤怒,但还是以“和谐”为重,如果自己的位置没有被占领,就赶紧坐下,如果自己的位置已经被别人(或者金刚同志)占了,就随机地选择另一个位置坐下,并开始闭目养神,不再挪动位置。

那么,在这两种情况下,第 i 个乘客(除去金刚同志之外)坐到自己原机票位置的概率分别是多少?

1

class

第一题:

因为每位乘客(包括金刚)都是随机的,问题等同于抽奖问题,先到先抽,即第 i 个乘客抽到自己的座位的概率为1/N。

2

class

第二题:

因为每位乘客(包括金刚)都是随机的,问题等同于抽奖问题,先到先抽,即第 i 个乘客抽到自己的座位的概率为1/N。对对对得得得地对地导弹 顶顶顶顶

用 F(i, n) 表示当座位总数为n时,第 i 个乘客坐到自己原位置的概率。根据全概率公式,得

其中 P(K=j) 表示金刚坐在位置j上,P(i | K=j) 是条件概率,表示当金刚坐在位置 j 上时,第 i 个乘客坐到自己原位置的概率。显然 P(K=j)=1/n,现在来分析 P(i | K=j)。

1、金刚若挑自己的座位或选的座位在第i个座位后(即 i < j),则第 i 个乘客肯定能坐到原来的座位。此时 P(i │ K=j) = 1;

2、金刚若挑选的座位在第 i 个座位前,(即 i > j),则第j个乘客除非坐到金刚的座位,不然就会抢其他人的座位,因为他的行为和金刚相似,可以将他当做金刚处理。去除前 j 个座位,剩下的座位和乘客再按原大小排序重新从1开始编号,则先前的第 i 个乘客,其座位号变为 i-j,新的总座位数变为 n-j。所以得 P(i │ K=j) = F(i-j, n-j)。

由上分析得:

再取 n+1 和 i+1 代入上式并与原式相减得:

code也是一种艺术,它能展现出自己的美。

原文发布于微信公众号 - 程序员互动联盟(coder_online)

原文发表时间:2015-12-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏华章科技

中科院的井盖火了!很多人表示压根看不懂,你来试试吧

导读:中国科学院物理所的不少井盖近日换了“新装”,每个卡通图案对应着一个物理学公式,科学与艺术在24个井盖上碰撞出有趣的火花。

10920
来自专栏ml

HDUOJ-----2066一个人的旅行

一个人的旅行 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

28550
来自专栏Vamei实验室

为什么说“概率”带来一场现代革命?

作者:Vamei 出处:http://www.cnblogs.com/vamei 严禁转载。

12730
来自专栏生信技能树

R语言系列:探索R自带数据包

向量 euro #欧元汇率,长度为11,每个元素都有命名 landmasses #48个陆地的面积,每个都有命名 precip #长度为70的...

12920
来自专栏灯塔大数据

每个分析师都会遇到的7个面试谜题

现在,想在分析行业里分得一杯羹是非常不容易的事情。约三成的分析公司(特别是顶尖公司)会要求应聘者解决谜题,并借此评估他们的能力。从中他们能够观察出你是否逻辑清...

29490
来自专栏新智元

马克龙当选法国总统,群集智能 Swarm AI 预测再获全胜

【新智元导读】马克龙在第二轮投票中击败勒庞,成为第 25 任法国总统。在预测的竞技场上,基于对社交网络和传统媒体讨论、民意调查、经济和人口统计等数据分析的 AI...

40070
来自专栏量子位

别的AI还在打游戏,这个AI已经当上“超级马里奥”游戏策划了|GECCO最佳论文

AI打游戏已经不是什么新鲜事了,“沉迷”Dota 2、星际争霸、LOL的AI一个接一个的出现。

10500
来自专栏进击的程序猿

cs224d-第二课-word2vec

首先我想说下为什么会去学习cs224d,原先我一直是做工程的,做了大概3年,产品做了好多,但是大多不幸夭折了,上线没多久就下线,最后实在是经受不住心灵的折磨,转...

18510
来自专栏Vamei实验室

为什么说“概率”带来一场现代革命?

作者:Vamei 出处:http://www.cnblogs.com/vamei 严禁转载。

14030
来自专栏挖数

论程序员怎么拥有咪蒙的文笔

作为半个程序员的我,是怎么训练我的文笔的呢?今天,我就跟陈独秀一起,分享一些提升文笔的小技巧

14440

扫码关注云+社区

领取腾讯云代金券