首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【编程之美】金刚坐飞机问题

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

作者头像
程序员互动联盟
发布2018-03-15 15:24:23
7720
发布2018-03-15 15:24:23
举报
金刚坐飞机问题

问题:

现在有一班飞机将要起飞,乘客们正准备按机票号码(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也是一种艺术,它能展现出自己的美。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2015-12-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员互动联盟 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档