概率题目汇总

分手后的思念是犯贱 2022-01-28 00:43 428阅读 0赞

### 概率题目汇总 ###

*  球队两强相遇
 *  蚂蚁碰头
 *  男女比例
 *  随机函数
 *  等概率产生0和1
 *  出现概率变为k次方
 *  等概率打印
 *  概率动态变化-蓄水池抽样算法

# 球队两强相遇 #

8只球队，有3个强队，其余都是弱队，随机把它们分成4组比赛，每组两个队，问两强相遇的概率是多大？

解题思路：

> 1.  首先求出**8只球队分成4组的方法数**：第一队有7种，第二队有5种，第三队有3种，第四队就剩下1种，所以总数为 **7 × 5 × 3 × 1 = 105** 种。
> 2.  **没有两强相遇的方法数**：在5个弱队中选出3个与强队配对，总数为 **C(5,3) × A(3,3) = 60** 种。
> 3.  两强不相遇的概率为：**(105-60)/105 = 3/7**。

# 蚂蚁碰头 #

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

**解题思路：**

> 如果3只蚂蚁方向都相同，一定不会相遇，所以3只蚂蚁方向一定有不同。  
> 每只蚂蚁方向数有2种，一共3只蚂蚁，一共有 **23 = 8** 种方向排列。  
> 其中，只有完全顺时针和完全逆时针这2种情况下不相遇，所以相遇的概率为：  
> **(8-2) / 8 = 0.75**

# 男女比例 #

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

**解题思路：**

> 假设这个地区一共有n个家庭：  
> n/2 的家庭第一胎就生出男孩，所以只有1个孩子。  
> n/4 的家庭先生1女孩，再生1男孩，有2个孩子。  
> n/8 的家庭先生2女孩，再生1男孩，有3个孩子。  
> …  
> 所以孩子总数为：  
> **n/2 + (n/4)×2 + (n/8)×3 + (n/16)×4 + … + n/2^n×n = 2 × n**  
> (求解过程：两边同乘2，再错位相减。)  
> 因为每个家庭都会有一个男孩，所以男孩有n个，则女孩数为 2n-n = n 个  
> 所以比例为 **1：1**

# 随机函数 #

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

**解题思路：**

> 1.  等概率随机函数产生 1、2、3、4、5
> 2.  将上述结果-1，将得到 f() ，其结果为0、1、2、3、4
> 3.  f() × 5 的结果为0、5、10、15、20
> 4.  **f() × 5 + f() 的结果为0、1、2、3、4、5 … 24**
> 5.  如果步骤4的结果大于20，则重复步骤4，直到结果在0-20之间
> 6.  步骤5的结果将等概率随机产生0-20，所以步骤5的结果\*\*%7\*\*之后就可以等概率产生0-6
> 7.  再将步骤6的结果+1即可

# 等概率产生0和1 #

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

**解题思路：**

> **产生01和10序列的概率都为 P × (1-P)**，所以不断调用f，直到产生的结果为01或10。如果**产生了01，就返回0；如果产生了10，就返回1**。

# 出现概率变为k次方 #

假设函数f()等概率随机返回一个在\[0,1)范围上的浮点数，那么在\[0,x)区间上的数出现的概率为x(0<x<=1)。给定一个大于0的整数k，并且可以使用f()函数，请事先一个函数依然返回在\[0,1)范围上的数，但是在\[0,x)区间上的数出现的概率为x的k次方。

**解题思路：**

> 先找出将概率x调整至x2的方法：调用两次f()，返回较大的数即可。  
> 所以，同理，**只需要调用k次f()，返回较大的数**即可。

# 等概率打印 #

给定一个长度为N且没有重复元素的数组arr和一个整数M，实现函数等概率随机打印arr中的M个数。

**解题思路：**

> 在**0 - N-1**中随机得到一个位置a，打印arr\[a\]，然后**将a和N-1进行交换**，在**从0 - N-2**中随机得到一个位置b，打印arr\[b\]，再与队尾交换，… ，直到打印了M个数。

# 概率动态变化-蓄水池抽样算法 #

原题：  
有一个机器按自然数序列的方式吐出球，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。

**解题思路—蓄水池抽样算法：**

> 1.  处理1-k号球时，直接放进袋子里。
> 2.  处理第 i 号球时，以 k/i 的概率决定是否将第 i 号球放进袋子中。如果不决定将第 i 号球放进袋子，直接扔掉第 i 号球。如果决定将第 i 号球放进袋子，那么就从袋子里的k个球中随机扔掉一个，然后把第 i 号球放入袋子。
> 
> 证明：
> 
> 1.  假设第 i 号球被选中并且 1<=i<=k，那么在选第 k+1 号球之前，第 i 号球留在袋子中的概率是1。在选第 k+1 号球时，在什么样的情况下第 i 号球会被淘汰，只有决定将第 k+1 号球放进袋子，同时在袋子中的第 i 号球被随机选中并决定扔掉，这两个时间同时发生时第 i 号球才会被淘汰。  
>     也就是说，第 i 号球会被淘汰的概率是 ( k / (k+1) ) × (1/k) = 1/(k+1)。所以第 i 号球留下来的概率为 1 - 1/(k+1) = k/(k+1)。这是1到k+1号球中第 i 号球被留下来的概率。
> 2.  在选第 k+2 号球时，什么时候第 i 号球会淘汰呢，只有把 k+2 号球放进袋子，同时在袋子中的第 i 号球被随机选中并决定扔掉，两件事同时发生时第 i 号球才能被淘汰。  
>     所以，第 i 号球会被淘汰的概率是 ( k / (k+2) ) × (1/k) = 1/(k+2)。所以第 i 号球留下来的概率为 1 - 1/(k+2) = (k+1)/(k+2)。那么，从1到k+2号球中第 i 号球被留下来的概率为：k/(k+1) × (k+1)/(k+2)。
> 3.  以此类推，在选第 N 号球时，第 i 号球最终留在袋子里的概率为：  
>     k/(k+1) × (k+1)/(k+2) × (k+2)/(k+3) × (k+3)/(k+4) × … × (N-1)/N = k/N
> 4.  同样推理，假设第 i 号球被选中并且 k<i<=N，那么在选第 i 号球之前，第 i 号球进入袋子中的概率是 k/i。在选第 i+1 号球时，在什么样的情况下第 i 号球会被淘汰，只有决定将第 i+1 号球放进袋子，同时在袋子中的第 i 号球被随机选中并决定扔掉，这两个时间同时发生时第 i 号球才会被淘汰。  
>     那么，第 i 号球会被淘汰的概率是 ( k / (i+1) ) × (1/k) = 1/(i+1)。所以第 i 号球留下来的概率为 1 - 1/(i+1) = i/(i+1)。所以，从第 i 号球被选中到第 i+1 号球的过程中，第 i 号球留在袋中的概率是 k/i × i/(i+1)。  
>     所以，在选第 N 号球时，第 i 号球最终留在袋子里的概率为：  
>     k/i × i/(i+1) × (i+1)/(i+2) × … × (N-1)/N = k/N