(转)随机数生成函数面试题

转载自：http://sumnous.github.io/blog/2014/05/13/random-pick-function/

前阵子去某公司笔试，有道题是

已知随机数生成函数f()，返回0的概率是60%，返回1的概率是40%。根据f()求随机数函数g()，使返回0和1的概率是50%，不能用已有的随机生成库函数。

分析：

调用f()两次即可，会出现4种结果(0,0), (0,1), (1,0), (1,1)，其中出现(0,1), (1,0)的概率是一样的，可以构造出等概率事件，比如出现(0,1)可返回0，出现(1,0)可返回1，如果出现其他两种情况则舍掉重新调用。

代码如下：

1 2 3 4 5 6 7 8

def g(): while(true): a = f() b = f() if [a,b] == [0,1]: return 0 if [a,b] == [1,0]: return 1

这道笔试题到此为止。

接下来扩展一下，如何实现这个随机数生成函数f()，可用random()，也就是以指定概率获取元素。《Python Cookbook》中有此示例。分析一下，也就是在(0, 0.6]区间内取0，在(0.6, 1]区间内取1。扩展到多个数也一样。

1 2 3 4 5 6 7 8 9

def withProbRandomPick(probList): import random import sys r, s = random.random(), 0 for num in probList: s += num[1] if s >= r: return num[0] print >> sys.stderr, "Error: shouldn't get here"

验证一下：

1 2 3 4 5 6 7

probList = [[0, 0.6], [1, 0.4]] import collections count = collections.defaultdict(int) for i in xrange(10000): count[withProbRandomPick(probList)] += 1 for n in count: print n, count[n] / 10000.0

得到的结果是：

1 2	0 0.5953 1 0.4047

《程序员面试金典第5版》(Cracking the Coding Interview)中也有一道给定一个随机数函数生成另一个随机数函数的题目。

给定rand5()，实现一个方法rand7()。也即，给定一个产生0到4（含）随机数方法，编写一个产生0到6（含）随机数的方法。（第105页）

分析：随机数函数的关键是确保产生每一个数的的概率相等。我们可用通过5 * rand5() + rand5()产生[0:24]，舍弃[21:24]，最后除以7取余数，则可得到概率相等的[0:6]的数值。

1 2 3 4 5

def rand7(): while(true): num = 5 * rand5() + rand5() if num < 21: return num % 7

变形一下，给定rand7()，如何实现rand5()？

Original link: http://sumnous.github.io/blog/2014/05/13/random-pick-function/
 Written by sumnous Posted at http://sumnous.github.io