统计软件题目 7
作业形式:
个人作业，请写上各人的学号，姓名;
开始和结束作业时间:
群里通知，elearning 上也会有。
作业提交形式:
电子版
1. R 代码，文件名为“学号_姓名_题目 7.R”，注意格式清晰，代码可读性好。源程序注释中标注
学号、姓名。
2. pdf 文件，文件名为“学号_姓名_题目 7.pdf”，根据各小问回答问题。
作业内容:阅读《炮灰模型——女生选择追求者模型》到“微软钻石题”一文(见第 2-6 页附录)， 验证文中的理论。
以下内容分为两部分，第一部分为作业题，第二部分为上述参考文献。
一、作业题目:
1. 写一个函数，要求: ◆ 输入:
⚫ 男生个数 N，缺省值(default)为 100 ◆ 功能与假设:
⚫ 对于给定的 N，假定男生编号从 1 到 N，排名越大越优秀
⚫ 所有的男生随机排序，即他们表白的先后顺序是等概率的
⚫ 对于任一整数M，1≤M≤N-1，按照下文参考文献中所述规则，被前面M个男生表白时均拒绝，在
剩下的人中，一旦表白的男生比前面所有的都要优秀(即编号更大)，就选择接受 ◆ 输出:
⚫ 输出为一个(𝑁 − 1) × 2的矩阵，第一列为 M 的所有可能取值(1,2,…,N-1)，第二列为在当前排 序下，用该规则(“炮灰”数 M)选中的男生在所有男生中的排名 (注:此处需注意“编号”(即“排名”)和“表白顺序”(即“序号”)的不同)
2. 设 N=100，将上述函数循环执行 10000 次，记录每次的结果(注:除了模型输出的矩阵外，还要加上是第 几次循环的编号)。
3. 统计对于不同的 M，最后选中最优男生(即排名为 N)的比例，并画出条形图(即每一条 bar 的长度代表不 同取值的 M 所选中最优男生的比例)
二、参考文献:
由《炮灰模型——女生选择追求者模型》到“微软钻石题” 2016-05-13 算法与数据结构 算法与数据结构
TheAlgorithm 算法与数据结构知识、资源分享来自:MATLAB_新浪博客 内容来自网络，2012 年之前的文章，原作者不详 链接:http://blog.sina.com.cn/s/blog_79ecf69801013q41.html
前段时间在 ADSP 课上，作为课间小插曲，老师提出了一个微软的钻石面试题，题目的描述是如下:
一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一 次，只能拿一次钻石，问怎样才能拿到最大的一颗?
课堂上有人给出了一种策略:前五层的钻石都不拿，而只是记录下最大的那一颗，在后面的五层里，只要遇见比所 记录大的就拿。若没有大的，就拿最后一颗。还有人根据钻石的大小事服从正态分布进而进行参数估计，从而得出 预期的最大的层数。其本质是根据已有的资料预计后面的大小从而做出选择。适逢上周有空，看到关于男生追求女 生的一个数学模型《炮灰模型——女生选择追求者模型》，细想后发现此问题与微软这道面试题挺像的，可以将其模 型和结论扩展到此问题上，并且结果也挺有意义的。首先从“炮灰模型”说起。
网上广泛转载的《炮灰模型——女生选择追求者模型》据说是 Tsinghua University 的一个学生 GengQuan 写的， 后有网友的润色和加工和开拓。其所提问题个人觉得与数学家Merrill M. Flood在1949年“未婚妻问题”类似。 而这个问题的精妙之处在于，在微积分界叱咤风云的自然底数 e，竟也出人意料地出现在了这个看似与它毫不相关 的问题中。还是从我们熟悉的某类节目说起。
背景介绍
在每期由两个光头主持的很火爆的某节目上，面对一位位男嘉宾，24 位单身女生要做出不止一次“艰难的决定”: 到底要不要继续亮灯?把灯灭掉意味着放弃了这一次机会，继续亮灯则有可能结束节目之旅，放弃了未来更多的选 择。
每一个女生都渴望找到自己心中的白马王子，找到自己一生的幸福。但是面对追求者们，女生应该是选择还是拒绝， 怎样才能以最大的可能找到自己的 Mr.Right 呢?如果遇到了一个优秀的男生，应该接受还是拒绝呢?如果接受了 他，万一下一个更好的话那可就亏大了;可如果为此而拒绝掉一个又一个好男人，也会面对着“过了这个村就没这 个店”的风险。说不定白马王子们都已经擦肩而过，到最后就只剩下。。。，当初的拒绝明显得不偿失。
由于没人能知道真正的缘分何时到来，没人能知道下一个来表白的男生会是什么样子，接受表白的时机早晚实在很 难决定。而运用数学中概率论的知识对女生选择追求者的这一过程进行数学建模，得到女生的选择的最优策略以作 参考。
模型假设(Geng 和 Flood)
假设一个女生愿意在一段时间中和一位男生开始一段感情，并且在这段时间中有 N 个男生追求这位女生。说明:这 里的 N 不是事先确定的，每个女生根据自身条件，并结合以往的经历和经验，猜测确定这个数字 N。比如其它各方 面都相同的两个女生，一般来说，PP 气质佳的女生就要比不 PP 的女生 N 值相对要大一些。在适合这个女生的意义 上，假设追求者有好有坏，任何两个男生都是可以比较的，而且没有相等的情况。这样我们对这 N 个男生从 1 到 N 进行编号，其中数字越大表示越适合这个女生。这样在这段时间中，女生的 Mr.Right 就是男生 N 了。现在问题变 成面对这 N 个追求者应该以怎样的策略才能使得在第一次选择接受的男生就是 N 的可能性最大，注意到这 N 个男生
是以不同的先后顺序来追求这位女生的。
为了将实际复杂的问题进行简化，我们做出下面几条合理的假设:
1、 N 个男生以不同的随机顺序向女生依次表白，即在任一时刻不存在两个或两个以上的男生向这位女生表白的情 况的发生，而且任何一种顺序都是完全等概率的。
2、 面对表白后的男生，女生只能做两种:接受和拒绝，不存在暧昧或者其它选择。
3、 任一时刻，女生最多只能和一位男生谈恋爱，不存在脚踏多船的情况。
4、 已经被拒绝的男生不会再次追求这位女生。 基于上述假设，我们想要找到这样一种策略，使得女生以最大的概率在第一次选择接受的那个男生就是 N=Mr.Right。
模型建立
先考虑最简单的一种策略，如果一旦有男生向女生表白，女生就选择接受。这种策略下显然女生以 1/N 的概率找到 自己的 Mr.Right。当 N 比较大的时候，这个概率就很小了，显然这种策略不是最优的。
基于上面这些假设和模型，聪明的 MM 会想到一个好办法:先和前面几个男生玩玩，试试水深;大致摸清了男生们 的底细后，再开始认真考虑，对于最先表白的 M 个人，无论女生感觉如何都选择拒绝;以后遇到男生向女生表白的 情况，只要这个男生的编号比前面 M 个男生的编号都大，即这个男生比前面 M 个男生更适合女生，那么女生选择接 受，否则选择拒绝。从数学模型上说，就是先拒掉前面 M 个人，不管这些人有多好;然后从第 M+1 个人开始，一旦 看到比之前所有人都要好的人，就毫不犹豫地选择他。不难看出，M 的取值很讲究，太小了达不到试的效果，太大 了又会导致真正可选的余地不多了。这就变成了一个纯数学问题:在男生总数 N 已知的情况下，当 M 等于何值时， 按上述策略选中最佳男生的概率最大?
下面以 N=3 为例说明:
三个男生追求女生，共有六种排列方式: 123，132，213，231，312，321
如果女生采用上述最简单的策略，那么只有最后两种排列方式选择到 Mr.Right，概率为 2/3!=1/3。
如果女生采用上面我们提出的策略，这里我们取 M=1，即无论第一个人是否优秀，女生都选择拒绝。然后对于之后 的追求者，只要他比第一个男生更适合女生就选择接受，否则拒绝。 基于这种策略，“132”、“213”、“231”这三种 排列顺序下女生都会在第一次做出接受的选择时遇到“3”，这样我们就把这种概率增大到 3/3!=1/2。
现在我们的问题就归结为，对于一般的 N，什么样的 M 才会使这种概率达到最大值呢?(在这种模型中，前面 M 个 男生就被称为“炮灰”，无论他们有多么优秀都要被拒绝)
根据上面的模型假设，我们先找到对于给定的 M 和 N，女生选择到 Mr.Right 的概率的表达式。
把 1 到 N 个数字进行排列共有 N!种可能。对于某个固定的 M，如果最适合的人出现在了第 P 个位置(M