内容简介:这个系列是我多年前找工作时对数据结构和算法总结,其中有基础部分,也有各大公司的经典的面试题,最早发布在CSDN。现整理为一个系列给需要的朋友参考,如有错误,欢迎指正。本系列完整代码地址在随机算法涉及大量概率论知识,有时候难得去仔细看推导过程,当然能够完全了解推导的过程自然是有好处的,如果不了解推导过程,至少记住结论也是必要的。本文总结最常见的一些随机算法的题目,是几年前找工作的时候写的。需要说明的是,这里用到的随机函数假设给定一个数组
这个系列是我多年前找工作时对数据结构和算法总结,其中有基础部分,也有各大公司的经典的面试题,最早发布在CSDN。现整理为一个系列给需要的朋友参考,如有错误,欢迎指正。本系列完整代码地址在 这里 。
0 概述
随机算法涉及大量概率论知识,有时候难得去仔细看推导过程,当然能够完全了解推导的过程自然是有好处的,如果不了解推导过程,至少记住结论也是必要的。本文总结最常见的一些随机算法的题目,是几年前找工作的时候写的。需要说明的是,这里用到的随机函数 randInt(a, b)
假定它能随机的产生范围 [a,b]
内的整数,即产生每个整数的概率相等(虽然在实际中并不一定能实现,不过不要太在意,这个世界很多事情都很随机)。本文代码在 这里 。
1 随机排列数组
假设给定一个数组 A
,它包含元素 1 到 N,我们的目标是构造这个数组的一个均匀随机排列。
一个常用的方法是为数组每个元素 A[i]
赋一个随机的优先级 P[i]
,然后依据优先级对数组进行排序。比如我们的数组为 A = {1, 2, 3, 4}
,如果选择的优先级数组为 P = {36, 3, 97, 19}
,那么就可以得到数列 B={2, 4, 1, 3}
,因为 3
的优先级最高(为97),而 2
的优先级最低(为3)。这个算法需要产生优先级数组,还需使用优先级数组对原数组排序,这里就不详细描述了,还有一种更好的方法可以得到随机排列数组。
产生随机排列数组的一个更好的方法是原地排列( in-place
)给定数组,可以在 O(N)
的时间内完成。伪代码如下:
RANDOMIZE-IN-PLACE ( A , n ) for i ←1 to n do swap A[i] ↔ A[RANDOM(i , n )] 复制代码
如代码中所示,第 i
次迭代时,元素 A[i]
是从元素 A[i...n]
中随机选取的,在第 i
次迭代后,我们就再也不会改变 A[i]
。
A[i] 位于任意位置j的概率为 1/n。这个是很容易推导的,比如 A[1]
位于位置 1 的概率为 1/n
,这个显然,因为 A[1]
不被1到n的元素替换的概率为 1/n
,而后就不会再改变 A[1]
了。而 A[1]
位于位置 2 的概率也是 1/n
,因为 A[1]
要想位于位置2,则必须在第一次与 A[k]
(k=2...n) 交换,同时第二次 A[2]
与 A[k]
替换,第一次与 A[k]
交换的概率为 (n-1)/n
,而第二次替换概率为 1/(n-1)
,所以总的概率是 (n-1)/n * 1/(n-1) = 1/n
。同理可以推导其他情况。
当然这个条件只能是随机排列数组的一个必要条件,也就是说,满足元素 A[i]
位于位置 j
的概率为 1/n
不一定就能说明这可以产生随机排列数组。因为它可能产生的排列数目少于 n!
,尽管概率相等,但是排列数目没有达到要求,算法导论上面有一个这样的反例。
算法 RANDOMIZE-IN-PLACE
可以产生均匀随机排列,它的证明过程如下:
首先给出k排列的概念,所谓 k 排列就是从n个元素中选取k个元素的排列,那么它一共有 n!/(n-k)!
个 k 排列。
循环不变式:for循环第i次迭代前,对于每个可能的i-1排列,子数组A[1...i-1]包含该i-1排列的概率为 (n-i+1)! / n!
。
-
初始化:在第一次迭代前,i=1,则循环不变式指的是对于每个0排列,子数组A[1...i-1]包含该0排列的概率为
(n-1+1)! / n! = 1
。A[1...0]为空的数组,0排列则没有任何元素,因此A包含所有可能的0排列的概率为1。不变式成立。 -
维持:假设在第i次迭代前,数组的i-1排列出现在
A[1...i-1]
的概率为(n-i+1) !/ n!
,那么在第i次迭代后,数组的所有i排列出现在A[1...i]
的概率为(n-i)! / n!
。下面来推导这个结论:- 考虑一个特殊的 i 排列 p = {x 1 , x 2 , ... x i },它由一个 i-1 排列 p' ={x1, x2,..., x i−1 } 后面跟一个 x i 构成。设定两个事件变量E1和E2:
-
E1为该算法将排列
p'
放置到A[1...i-1]
的事件,概率由归纳假设得知为Pr(E1) = (n-i+1)! / n!
。 -
E2为在第 i 次迭代时将 x i 放入到
A[i]
的事件。 因此我们得到 i 排列出现在A[1...i]
的概率为Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}
。而Pr {E2 | E1} = 1/(n − i + 1)
,所以Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}= 1 /(n − i + 1) * (n − i + 1)! / n! = (n − i )! / n!
。 -
结束:结束的时候
i=n+1
,因此可以得到A[1...n]
是一个给定 n 排列的概率为1/n!
。
C实现代码如下:
void randomInPlace(int a[], int n) { int i; for (i = 0; i < n; i++) { int rand = randInt(i, n-1); swapInt(a, i, rand); } } 复制代码
扩展
如果上面的随机排列算法写成下面这样,是否也能产生均匀随机排列?
PERMUTE-WITH-ALL( A , n ) for i ←1 to n do swap A[i] ↔A[RANDOM(1 , n )] 复制代码
注意,该算法不能产生均匀随机排列。假定 n=3
,则该算法可以产生 3*3*3=27
个输出,而3个元素只有 3!=6
个不同的排列,要使得这些排列出现概率等于 1/6
,则必须使得每个排列出现次数 m 满足 m/27=1/6
,显然,没有这样的整数符合条件。而实际上各个排列出现的概率如下,如 {1,2,3}
出现的概率为 4/27
,不等于 1/6
。
排 列 | 概 率 |
---|---|
<1, 2, 3> | 4/27 |
<1, 3, 2> | 5/27 |
<2, 1, 3> | 5/27 |
<2, 3, 1> | 5/27 |
<3, 1, 2> | 4/27 |
<3, 2, 1> | 4/27 |
2 随机选取一个数字
题:给定一个未知长度的整数流,如何随机选取一个数?(所谓随机就是保证每个数被选取的概率相等)
解1:如果数据流不是很长,可以存在数组中,然后再从数组中随机选取。当然题目说的是未知长度,所以如果长度很大不足以保存在内存中的话,这种解法有其局限性。
解2:如果数据流很长的话,可以这样:
- 如果数据流在第1个数字后结束,那么必选第1个数字。
- 如果数据流在第2个数字后结束,那么我们选第2个数字的概率为1/2,我们以1/2的概率用第2个数字替换前面选的随机数,得到新的随机数。
- ......
- 如果数据流在第n个数字后结束,那么我们选择第n个数字的概率为1/n,即我们以1/n的概率用第n个数字替换前面选的随机数,得到新的随机数。
一个简单的方法就是使用随机函数 f(n)=bigrand()%n
,其中 bigrand()
返回很大的随机整数,当数据流到第 n
个数时,如果 f(n)==0
,则替换前面的已经选的随机数,这样可以保证每个数字被选中的概率都是 1/n
。如当 n=1
时,则 f(1)=0
,则选择第 1 个数,当 n=2
时,则第 2 个数被选中的概率都为 1/2
,以此类推,当数字长度为 n 时,第 n 个数字被选中的概率为 1/n
。代码如下(注:在 Linux/MacOS 下, rand()
函数已经可以返回一个很大的随机数了,就当做bigrand()用了):
void randomOne(int n) { int i, select = 0; for (i = 1; i < n; i++) { int rd = rand() % n; if (rd == 0) { select = i; } } printf("%d\n", select); } 复制代码
3 随机选取M个数字
题: 程序输入包含两个整数 m 和 n ,其中 m<n
,输出是 0~n-1
范围内的 m 个随机整数的有序列表,不允许重复。从概率角度来说,我们希望得到没有重复的有序选择,其中每个选择出现的概率相等。
解1:先考虑个简单的例子,当 m=2,n=5
时,我们需要从 0~4
这 5 个整数中等概率的选取 2 个有序的整数,且不能重复。如果采用如下条件选取: bigrand() % 5 < 2
,则我们选取 0 的概率为 2/5
。但是我们不能采取同样的概率来选取 1,因为选取了 0 后,我们应该以 1/4
的概率来选取1,而在没有选取0的情况下,我们应该以 2/4
的概率选取1。选取的伪代码如下:
select = m remaining = n for i = [0, n) if (bigrand() % remaining < select) print i select-- remaining-- 复制代码
只要满足条件 m<=n
,则程序输出 m 个有序整数,不多不少。不会多选,因为每选择一个数, select--
,这样当 select 减到 0 后就不会再选了。同时,也不会少选,因为每次都会 remaining--
,当 select/remaining=1
时,一定会选取一个数。每个子集被选择的概率是相等的,比如这里5选2则共有 C(5,2)=10
个子集,如 {0,1},{0,2}...
等,每个子集被选中的概率都是 1/10
。
更一般的推导,n选m的子集数目一共有 C(n,m)
个,考虑一个特定的 m 序列,如 0...m-1
,则选取它的概率为 m/n * (m-1)/(n-1)*....1/(n-m+1)=1/C(n,m)
,可以看到概率是相等的。
Knuth 老爷爷很早就提出了这个算法,他的实现如下:
void randomMKnuth(int n, int m) { int i; for (i = 0; i < n; i++) { if ((rand() % (n-i)) < m) { printf("%d ", i); m--; } } } 复制代码
解2:还可以采用前面随机排列数组的思想,先对前 m 个数字进行随机排列,然后 排序 这 m 个数字并输出即可。代码如下:
void randomMArray(int n, int m) { int i, j; int *x = (int *)malloc(sizeof(int) * n); for (i = 0; i < n; i++) x[i] = i; // 随机数组 for (i = 0; i < m; i++) { j = randInt(i, n-1); swapInt(x, i, j); } // 对数组前 m 个元素排序 for (i = 0; i < m; i++) { for (j = i+1; j>0 && x[j-1]>x[j]; j--) { swapInt(x, j, j-1); } } for (i = 0; i < m; i++) { printf("%d ", x[i]); } printf("\n"); } 复制代码
4 rand7 生成 rand10 问题
题:已知一个函数rand7()能够生成1-7的随机数,每个数概率相等,请给出一个函数rand10(),该函数能够生成 1-10 的随机数,每个数概率相等。
解1:要产生 1-10 的随机数,我们要么执行 rand7() 两次,要么直接乘以一个数字来得到我们想要的范围值。如下面公式(1)和(2)。
idx = 7 * (rand7()-1) + rand7() ---(1) 正确 idx = 8 * rand7() - 7 ---(2) 错误 复制代码
上面公式 (1) 能够产生 1-49
的随机数,为什么呢?因为 rand7() 的可能的值为 1-7,两个 rand7() 则可能产生 49 种组合,且正好是 1-49 这 49 个数,每个数出现的概率为 1/49
,于是我们可以将大于 40 的丢弃,然后取 (idx-1) % 10 + 1
即可。公式(2)是错误的,因为它生成的数的概率不均等,而且也无法生成49个数字。
1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 8 9 10 1 2 3 4 3 5 6 7 8 9 10 1 4 2 3 4 5 6 7 8 5 9 10 1 2 3 4 5 6 6 7 8 9 10 * * 7 * * * * * * * 复制代码
该解法基于一种叫做拒绝采样的方法。主要思想是只要产生一个目标范围内的随机数,则直接返回。如果产生的随机数不在目标范围内,则丢弃该值,重新取样。由于目标范围内的数字被选中的概率相等,这样一个均匀的分布生成了。代码如下:
int rand7ToRand10Sample() { int row, col, idx; do { row = rand7(); col = rand7(); idx = col + (row-1)*7; } while (idx > 40); return 1 + (idx-1) % 10; } 复制代码
由于row范围为1-7,col范围为1-7,这样idx值范围为1-49。大于40的值被丢弃,这样剩下1-40范围内的数字,通过取模返回。下面计算一下得到一个满足1-40范围的数需要进行取样的次数的期望值:
E(# calls to rand7) = 2 * (40/49) + 4 * (9/49) * (40/49) + 6 * (9/49)2 * (40/49) + ... ∞ = ∑ 2k * (9/49)k-1 * (40/49) k=1 = (80/49) / (1 - 9/49)2 = 2.45 复制代码
解2:上面的方法大概需要2.45次调用 rand7 函数才能得到 1 个 1-10 范围的数,下面可以进行再度优化。对于大于40的数,我们不必马上丢弃,可以对 41-49 的数减去 40 可得到 1-9 的随机数,而rand7可生成 1-7 的随机数,这样可以生成 1-63 的随机数。对于 1-60 我们可以直接返回,而 61-63 则丢弃,这样需要丢弃的数只有3个,相比前面的9个,效率有所提高。而对于61-63的数,减去60后为 1-3,rand7 产生 1-7,这样可以再度利用产生 1-21 的数,对于 1-20 我们则直接返回,对于 21 则丢弃。这时,丢弃的数就只有1个了,优化又进一步。当然这里面对rand7的调用次数也是增加了的。代码如下,优化后的期望大概是 2.2123。
int rand7ToRand10UtilizeSample() { int a, b, idx; while (1) { a = randInt(1, 7); b = randInt(1, 7); idx = b + (a-1)*7; if (idx <= 40) return 1 + (idx-1)%10; a = idx-40; b = randInt(1, 7); // get uniform dist from 1 - 63 idx = b + (a-1)*7; if (idx <= 60) return 1 + (idx-1)%10; a = idx-60; b = randInt(1, 7); // get uniform dist from 1-21 idx = b + (a-1)*7; if (idx <= 20) return 1 + (idx-1)%10; } } 复制代码
5 趣味概率题
1)称球问题
题: 有12个小球,其中一个是坏球。给你一架天平,需要你用最少的称次数来确定哪个小球是坏的,并且它到底是轻了还是重了。
解: 之前有总结过二分查找算法,我们知道二分法可以加快有序数组的查找。相似的,比如在数字游戏中,如果要你猜一个介于 1-64
之间的数字,用二分法在6次内肯定能猜出来。但是称球问题却不同。称球问题这里 12 个小球,坏球可能是其中任意一个,这就有 12 种可能性。而坏球可能是重了或者轻了这2种情况,于是这个问题一共有 12*2 = 24
种可能性。每次用天平称,天平可以输出的是 平衡、左重、右重
3 种可能性,即称一次可以将问题可能性缩小到原来的 1/3
,则一共 24
种可能性可以在 3
次内称出来( 3^3 = 27
)。
为什么最直观的称法 6-6
不是最优的?在 6-6
称的时候,天平平衡的可能性是0,而最优策略应该是让天平每次称量时的概率均等,这样才能三等分答案的所有可能性。
具体怎么实施呢? 将球编号为1-12,采用 4, 4
称的方法。
- 我们先将
1 2 3 4
和5 6 7 8
进行第1次称重。 - 如果第1次平衡,则坏球肯定在
9-12
号中。则此时只剩下9-12
4个球,可能性为9- 10- 11- 12- 9+ 10+ 11+ 12+
这8种可能。接下来将9 10 11
和1 2 3
称第2次:如果平衡,则12
号小球为坏球,将12号小球与1号小球称第3次即可确认轻还是重。如果不平衡,则如果重了说明坏球重了,继续将9和10号球称量,重的为坏球,平衡的话则11为坏球。 - 如果第1次不平衡,则坏球肯定在
1-8
号中。则还剩下的可能性是1+ 2+ 3+ 4+ 5- 6- 7- 8-
或者1- 2- 3- 4- 5+ 6+ 7+ 8+
,如果是1 2 3 4
这边重,则可以将1 2 6
和3 4 5
称,如果平衡,则必然是7 8
轻了,再称一次7和1,便可以判断7和8哪个是坏球了。如果不平衡,假定是1 2 6
这边重,则可以判断出1 2
重了或者5
轻了,为什么呢?因为如果是3+ 4+ 6-
,则1 2 3 4
比5 6 7 8
重,但是1 2 6
应该比3 4 5
轻。其他情况同理,最多3次即可找出坏球。
下面这个图更加清晰说明了这个原理。
2)生男生女问题
题:在重男轻女的国家里,男女的比例是多少?在一个重男轻女的国家里,每个家庭都想生男孩,如果他们生的孩子是女孩,就再生一个,直到生下的是男孩为止。这样的国家,男女比例会是多少?
解:还是1:1。在所有出生的第一个小孩中,男女比例是1:1;在所有出生的第二个小孩中,男女比例是1:1;.... 在所有出生的第n个小孩中,男女比例还是1:1。所以总的男女比例是1:1。
3)约会问题
题:两人相约5点到6点在某地会面,先到者等20分钟后离去,求这两人能够会面的概率。
解:设两人分别在5点X分和5点Y分到达目的地,则他们能够会面的条件是 |X-Y| <= 20
,而整个范围为 S={(x, y): 0 =< x <= 60, 0=< y <= 60}
,如果画出坐标轴的话,会面的情况为坐标轴中表示的面积,概率为 (60^2 - 40^2) / 60^2 = 5/9
。
4)帽子问题
题:有n位顾客,他们每个人给餐厅的服务生一顶帽子,服务生以随机的顺序归还给顾客,请问拿到自己帽子的顾客的期望数是多少?
解:使用指示随机变量来求解这个问题会简单些。定义一个随机变量X等于能够拿到自己帽子的顾客数目,我们要计算的是 E[X]
。对于 i=1, 2 ... n
,定义 X i =I {顾客i拿到自己的帽子},则 X=X 1 +X 2 +...X n 。由于归还帽子的顺序是随机的,所以每个顾客拿到自己帽子的概率为1/n,即 P r (X i =1)=1/n,从而 E(X i )=1/n,所以E(X)=E(X 1 + X 2 + ...X n )= E(X 1 )+E(X 2 )+...E(X n )=n*1/n = 1,即大约有1个顾客可以拿到自己的帽子。
5)生日悖论
题:一个房间至少要有多少人,才能使得有两个人的生日在同一天?
解:对房间k个人中的每一对(i, j)定义指示器变量 X ij = {i与j生日在同一天} ,则i与j生日相同时,X ij =1,否则 X ij =0。两个人在同一天生日的概率 Pr(X ij =1)=1/n 。则用X表示同一天生日的两人对的数目,则 E(X)=E(∑k i=1 ∑k j=i+1 X ij ) = C(k,2)*1/n = k(k-1)/2n,令 k(k-1)/2n >=1
,可得到 k>=28
,即至少要有 28 个人,才能期望两个人的生日在同一天。
6)概率逆推问题
题:如果在高速公路上30分钟内看到一辆车开过的几率是0.95,那么在10分钟内看到一辆车开过的几率是多少?(假设常概率条件下)
解:假设10分钟内看到一辆车开过的概率是x,那么没有看到车开过的概率就是1-x,30分钟没有看到车开过的概率是 (1-x)^3
,也就是 0.05
。所以得到方程 (1-x)^3 = 0.05
,解方程得到 x 大约是 0.63。
参考资料
- 算法导论第6章随机算法
- 编程珠玑第12章
- leetcode.com/articles/im…
- mindhacks.cn/2008/06/13/…
- blog.csdn.net/wxwtj/artic…
以上所述就是小编给大家介绍的《数据结构和算法面试题系列—随机算法总结》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 算法与数据结构之递归算法
- Python 数据结构与算法 —— 初识算法
- js实现数据结构及算法之排序算法
- 数据结构和算法面试题系列—递归算法总结
- 数据结构与算法——常用排序算法及其Java实现
- 数据结构和算法面试题系列—二分查找算法详解
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
网络多人游戏架构与编程
格雷泽 (Joshua Glazer)、马达夫 (Sanjay Madhav) / 王晓慧、张国鑫 / 人民邮电出版社 / 2017-10-1 / CNY 109.00
本书是一本深入探讨关于网络多人游戏编程的图书。 全书分为13章,从网络游戏的基本概念、互联网、伯克利套接字、对象序列化、对象复制、网络拓扑和游戏案例、延迟、抖动和可靠性、改进的延迟处理、可扩展性、安全性、真实世界的引擎、玩家服务、云托管专用服务器等方面深入介绍了网络多人游戏开发的知识,既全面又详尽地剖析了众多核心概念。 本书的多数示例基于C++编写,适合对C++有一定了解的读者阅读。本......一起来看看 《网络多人游戏架构与编程》 这本书的介绍吧!