直通BAT--数据结构与算法十一(概率)_八个队三个强队中概率

作者：盐析白兔 | 2024-03-13 01:20:23

踩

八个队三个强队中概率

概率常考题型：

概率与期望的计算
利用古典概率进行计算：组合数学
随机数发生器：利用一个随机数发生器构造另一个随机数发生器

1.球队分组问题

8只球队，有3个强队，5只弱队，随机把它们分成4组比赛，每组两个队，问两支强队在一起的概率是多大？

分析：

8只球队分成两两一队：首先随机选一个人，他从剩余的7个中选择一个组队有7中情况；再随机选一个人，他从剩余的5个中选择一个组队有5种情况；再随机选一个人，他从剩余的3个中选择一个组队有3种情况；最后两个组成一队。则共有7*5*3=105种情况。
没有2只强队在一个队：在5只弱队中选3只，与强度进行比赛有C（5，3）种情况；3只强队与3只弱队配对共有A（3，3）种情况；剩下的2只组队；共有C（5，2）*A（3，3）=60；
两支强队在一起的概率：（105-60）/105=3/7。

2.蚂蚁相遇问题

3只蚂蚁从正三角形的三个顶点沿着边移动，速度相同，问它们碰头的概率多大？

分析：

3只蚂蚁中，每只蚂蚁的方向有2种，即共有8中情况。
不相遇的情况：3只蚂蚁方向均逆时针或顺时针，共2种情况。
相遇的概率：（8-2）/8=3/4。

3.男女比例问题

某地区重男轻女，一个家庭如果生出一个女孩则一直生，直到生出男孩就停止生育。假如一次只生一个孩子，问时间足够长后，男女比例是多少？

分析：

假设总共有n个家庭，其中有n/2为男孩，则男孩有n/2个；
剩下的n/2个女孩家庭，其中有n/4为男孩，n/4为女孩；
剩下的n/4个女孩家庭，其中有n/8为男孩，n/8为女孩；
。。。。。。
最后孩子总数为n/2+n/4*2+n/8*3+......+n/2^n*n=n*(Σ(i/(2^i))=2*n；
其中每家均有一个男孩，男孩个数为n;
则最后的比例为1：1。

4.随机函数

给定一个等概率随机产生1-5的随机函数，除此之外，不能使用任何额外的随机机制，请实现等概率随机产生1-7的随机函数。

分析：

1.已经有等概率产生1、2、3、4、5的随机函数
2.根据步骤1，得到的结果减1，将得到f()->0、1、2、3、4
3.f()*5->0、5、10、15、20
4.f()*5+f()->0、1、2、3......23、24
5.如果步骤4产生的数大于20，则重复继续能给你步骤4，直到产生的结果在0-20之间
6.步骤5将等概率随机产生0-20，所以步骤5的结果%7之后等概率产生0-6
7.步骤6的结果加1，等概率产生1-7

5.随机01

给定一个以p概率产生0，以1-p概率产生1的随机函数RandomP::f()，p是固定的值，但你并不知道是多少。除此之外也不能使用任何额外的随机机制，请用RandomP::f()实现等概率随机产生0和1的随机函数。

分析：

两次连续执行随机函数，产生结果可能为00、01、10、11；
如果是00、11则放弃；
如果是01则返回0，如果是10则返回1；
01与10产生的概率相等。

6.机器吐球问题

有一个机器按自然数序列的方式吐出球，1号球，2号球，3号球等等。你有一个袋子，袋子里最多只能装下K个球，并且除袋子以外，你没有更多的空间，一个球一旦扔掉，就再也不可拿回。

设计一种选择方式，使得当机器吐出第N号球的时候，你袋子中的球数是K个，同时可以保证从1号球到N号球中的每一个，被选进袋子的概率都是K/N。

举一个更具体的例子，有一个只能装下10个球的袋子，当吐出100个球时，袋子里有10 球，并且1~100号中的每一个球被选中的概率都是10/100。然后继续吐球，当吐出1000个球时，袋子里有 10 个球，并且1~1000号中的每一个球被选中的概率都是10/1000。继续吐球，当吐出i个球时，袋子里有10个球，并且1~i号中的每一个球被选中的概率都是10/i。也就是随着N的变化，1~N号球被选中的概率动态变化成k/N。

请将吐出第N个球时袋子中的球的编号返回。

分析：

当N<=k时，球被选中的概率为k/N>1，则一定被放入袋子
当N==k+1时，若k+1号球留下的概率为k/（k+1）,其中已经在袋子中的球不留下的概率为k/（k+1）*(1/k)=1/(k+1)；已经在袋子中的球留下的概率为1-1/(k+1)=k/（k+1）即全部留下的概率均为K/N 。
当N==k+2时，若k+2号球留下的概率为k/（k+2）,其中已经在袋子中的球不留下的概率为k/（k+2）*(1/k)=1/(k+2)；已经在袋子中的球留下的概率为1-1/(k+2)=k/（k+2）即全部留下的概率均为K/N 。
以此类推，则保证若N号球留下的概率为k/N时，每个球在袋中的概率均为k/N。

   class Bag { 
 
   public: 
 
       vector<int> ret; 
 
       // 每次拿一个球都会调用这个函数，N表示第i次调用，从0开始算 
 
       vector<int> carryBalls(int N, int k) { 
 
           if(N < k){ 
 
               ret.push_back(N); 
 
           }else{ 
 
               int num = rand()%N; 
 
               if(num < k){ 
 
                   ret[num] = N; 
 
               } 
 
           } 
 
           return ret; 
 
       } 
 
   };

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/227068