热乎出炉，2015百度研发校招笔试题。
此题代码极其简单，关键看能想到不。凡概率相关，基本都是一个模子，需要使用条件概率算出某个具体事件出现的概率，然后再求和。这个题的关键还是在于证明，虽然实际并未要求证明，但是它的正确结果，看起来都不是那么的正确，需要仔细分析，才能发现他们是等概率的。
设有1-n一共n个数，如何构建一个长度为n的数组，使每一个数的位置都随机？我们有一个随机数发生器random(m),能够生成[0,m]的随机数.
1.问题转化一下：假设我们已经有一个长度为x-1的数组,其中每个数的位置都是随机的。这时候，我们增加一个数x,将它插入数组，如果才能保证真个长度为x的数组里面每一 个数的位置依然随机？
设原有集合为Set
a. 通过random(x-1)生成 [0,x-1]的随机数 p
b. 将x插入p位置，即将下标>p的数字全部向后移一位，再Set[p] = x 即可。
我们从x=1开始，重复这个过程。最终的伪代码如下：
设原有集合为Set
x = 1;
Set = [1]
while(x< = n){
通过random(x-1)生成 [0,x-1]的随机数 p
将下标>p的数字全部向后移一位，
Set[p] = x;
x++;
}
2.正确性证明：
a. 当n=1时，显然最后最后的随机数组只能为[1]
b. 当n=2:
random(1) = 0 最后的随机数组为[1,0] . 其出现的概率为 P(random(1) = 0) = 0.5
random(1) = 0 最后的随机数组为[0,1] . 其出现的概率为 P(random(1) = 1) = 0.5
所以，0出现在set[0]的概率为0.5, 出现在set[1]的概率为0.5；1出现在set[0]的概率为0.5, 出现在set[1]的概率为0.5
这时，任意数字在任意位置出现的概率相等
c. 假设n=k时，算法成立
对于数字x，其在set[i]出现的概率为P(k, x,i) = m, 任意数字在任意位置出现的概率相等，均为m = 1/k.
d.当n = k+1时
random(k) 的取值在[0,k]上均匀分布，取任意一个值的概率均为d = 1/(k+1)
显然，n = k+1出现在任意一位的概率为d,即
式I: p(k+1,k+1,i) = d
那么，由于n=k时 p(k, x,i) = m (x<=k)
那么对于，对于步骤c中x,i，再加入n=k+1后，
x在i位出现的概率 = x在i-1出现的概率 * （random(k)<= i的概率) + x在i出现的概率* (random(k)>i)的概率）
即:
p(k+1,x,i) = p(k,x,i-1)* (i+1)*d + p(k,x,i) *(k-i)*d
= mid +md + mkd -mid
= md *(k+1)
代入 d=1/(k+1) :
p(k+1,x,i) = m
得到下式：
式II: p(k+1,x,i) = (x∈[1,k], i∈[0,k])
e.合并I, II,即把新增的x+1也放在内，有
p(k+1,x,i) = m (x∈[1,k+1], i∈[0,k])
即对于任意的x属于[1,k+1](共k个数）,在任意的位置i∈[0,k]出现的概率均等，均为1/k
阅读(2260) | 评论(0) | 转发(1) |
