转让S家的奶票 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PennySaver - 省钱一族

转让S家的奶票

转让S家的奶票# PennySaver - 省钱一族

i*n2010-03-19 07:03

1 楼

给定一个随机数组比如A=[2, 7, 15, 20, 10],还有一个数组是每个数对应的出现概率
比如B=[0.12, 0.25, 0.56, 0.02, 0.05]。（数字记不清了）
1。如何设计这个随机数生成器？
2。如果其中一个数概率很小，比如10^-12，需要修改1的设计吗？
3。如果需要生成很多随机数，有什么优化可以做？

b*i2010-03-19 07:03

2 楼

有三张S家的$5的奶票，两张4月7日到期，一张6月5日到期。$5 包邮。需要的请短我
。

i*n2010-03-19 07:03

3 楼

没人知道？

【在 i*******n 的大作中提到】

: 给定一个随机数组比如A=[2, 7, 15, 20, 10],还有一个数组是每个数对应的出现概率
: 比如B=[0.12, 0.25, 0.56, 0.02, 0.05]。（数字记不清了）
: 1。如何设计这个随机数生成器？
: 2。如果其中一个数概率很小，比如10^-12，需要修改1的设计吗？
: 3。如果需要生成很多随机数，有什么优化可以做？

T*y2010-03-19 07:03

4 楼

偶错过了?

【在 b******i 的大作中提到】

: 有三张S家的$5的奶票，两张4月7日到期，一张6月5日到期。$5 包邮。需要的请短我
: 。

r*h2010-03-19 07:03

5 楼

1.假设有一个1-100的随机数生成器
那么将1-12映射到2,13-37映射到7.。。即可
2.需要。如果其中一个数概率很小那么应该先单独取一次随机数检查是否生成这个特殊
的数，如果未命中则再使用1的方法。由于10^-12很小，因此造成的影响基本可以忽略。
3.很多随机数指的是A里面元素很多，还是说给定一个A和B要生成符合分布的很多数？
我能想到的就是用一个hash存下每个映射的值对以减少重复计算

【在 i*******n 的大作中提到】

b*i2010-03-19 07:03

6 楼

已送出。谢谢！

【在 b******i 的大作中提到】

: 有三张S家的$5的奶票，两张4月7日到期，一张6月5日到期。$5 包邮。需要的请短我
: 。

c*72010-03-19 07:03

7 楼

^_^，我没有面试过你吧？我一般问人家这题：
given a list of key value paire, randomly pick key based on values.
这题是我自己创的呀，被人偷去了？

【在 i*******n 的大作中提到】

s*d2010-03-19 07:03

8 楼

miss掉了，很可惜

【在 b******i 的大作中提到】

: 已送出。谢谢！

t*h2010-03-19 07:03

9 楼

这个一般是先计算CDF（Cumulative distribution function),然后用[0,1] uniform
随机数来判断。小概率随机数产生是个tricky的问题。如果一般是算期望的话（Monte
Carlo)，可能就要change of measure了，本质上就是换权重。

z*e2010-03-19 07:03

10 楼

看了下楼上的回帖
貌似你漏了一个前提
就是人家给没给一个随机数生成的函数
如果没给这题你要做出来就是超级大牛
因为姚期智之所以拿图灵奖就是因为搞出了伪随机数算法
2需要啊，因为如果全部放到同一个sample里面去的话
size会变得很大，算起来会很恶心
3越多随机数概率越接近平均值
所以可以直接用population乘以概率算出每一个随机数出现的频率
误差normally distributed
找一个mean为0的normal distribution随机数生成api
直接生成误差值就好了

【在 i*******n 的大作中提到】