欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(转)随机数生成函数面试题 博客分类: 算法题 随机数生成 

程序员文章站 2024-03-18 09:28:46
...

转载自: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()?

相关标签: 随机数生成