y****n
发帖数: 743 | 1 (rand5() + rand5() +rand5() +rand5() + rand5() +rand5() +rand5() ) %7
不可行。
因为你不能保证结果是均匀的。
rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5()
结果为14的概率远远大于结果是0或28的概率。
thrust的解释是正确的，有限次rand5()不可能产生rand7()
number |
|
w********p
发帖数: 948 | 2 这里有个类似的题的解答。BTW, 这题，我的理解 rand5 是 generate random number
between 1 到 5。不然 5＊ （rand5()-1) 是没有办法产生如图上的6－20的。 还有因
为设计到概览
rand5() + rand5() 和 2＊rand5() 是不一样的。一开始我没明白。
http://www.mytechinterviews.com/equal-probability-between-1-and
smartlhc 的解释对我有启发。
我的问题是
(rand5() + rand5() +rand5() +rand5() + rand5() +rand5() +rand5() ) %7 是不
是可行的呢？如果不对，问题出在哪儿呢？
写完了，觉得好像不对，不对在于，前5此产生的数的概率是一样的，但是第六第七次
的概率各有1／5。
有些糊的感觉。 |
|
w***y
发帖数: 6251 | 3 太激动了，终于看到一个自认为我很明白可以掰扯几句的题目haha
我没仔细看过cc150上的答案，如果rand5的意思是1-5均匀分布，这个的答案应该是5*(
rand5-1)+rand5， 对应一个1-25的均匀分布； 如果rand5产生0-4的均匀分布，5*
rand5+rand5 对应一个0-24的均匀分布。
把rand5想象成一个5-side的骰子，两个骰子的结果计算到一起，就很好理解为什么这
个公式会生成另外range 25的均匀分布数字
一个range 25的均匀分布转化成rand7， 就是再用一下rejection和取模 |
|
z****e
发帖数: 54598 | 4 这是其实是基础统计题
你把所有组合给罗列出来之后，就可以看出来了
9*rand5 + rand5 is ok
任何一个大于5的系数乘以rand5都 不 会导致结果重叠
唯一的问题在于，你这样做的结果集可能比较分散
你要重新建立映射到你想要的结果集中去
是否均匀分布是建立在rand5本身是均匀分布基础之上
如果rand5不是均匀分布，那9*rand5 + rand5也就不是均匀分布
这种题bbs上说起来太麻烦，现实生活中找个人解释一下
也就是两分钟的事，画个图，什么都解决了 |
|
m*********g
发帖数: 170 | 5 rand5() 产生0，1，2，3，4的概率应该是一样的吧 -- 都是20%。
rand5()/4得到0，0.25，0.5，0.75，1。把0.5去掉后【0，1】的概率就一样了。
rand7() = rand5() + get012()
//我们用rand5()来得到0，2，4. 排除1和3.
int get012()
{
int res = 0;
do
{
res = rand5();
}
while(res ==1 || rand5() == 3)
return res / 2;
} |
|
w********p
发帖数: 948 | 6 谢谢yishan， thrust， rainbowrain 的帮忙解释。
这样可以吗？ 假设rand5() 产生1，到 5， 用 rand5() 实现 rand7() 产生 1到7。
（和楼主的题，有点点不一样）
rand7() 用三个rand5（）， 每个rand5()产生一个bit. 每个rand5() 遇到5的时候
drop，这样可以吗？
public int rand7() {
int randNum = 0;
int returnNum = 0;
for ( int i=0; i<3; i++) {
while ( (randNum = rand5()) == 5 ) {
}
int bit = randNum % 2;
returnNum += (bit<
}
return returnNum;
}
这个最后是产生了0－7，还是不符合需要，不过可以过滤掉不想要的0。
这个和最佳答案比，思路还是差很多。 |
|
c*****e
发帖数: 3226 | 7 - 5 * rand5() = 5, 10, 15, 20, 25 +rand5() 补了 1-5, 6-10,11- 15, 16-
20, 21-25, 26-30. 洞很形象。：-）
- 9* rand5() 或者类似 3 * rand5() 不方便填补。
- rand5() * rand5() 也不是 even distributed, 因为 1 = 1*1, but 5 = 1*5 or 5
*1
+ |
|
j**7
发帖数: 143 | 8 Cracking the Coding Interview 17.11
搞不明白书上的答案。
My solution is 6* rand5()/4.
rand5()产生[0,4],rand5()/4产生[0,1].
6*rand5()/4产生[0,6]. |
|
s******c
发帖数: 99 | 9 不只是整数的问题。你用6*rand5()这样只能call rand5一次，rand5() 一定要call两
次，因为7比5大，就比如你用1个骰子不能产生0-7之间的随机数一样
其实书上的算法这样写比较抽象，实际情况是这样的，你call 2次rand5()，有如下组
合，他们分别对应相对的结果，每三个一组
0 0
0 1 ->0
0 2
--------------
0 3
0 4 ->1
1 0
--------------
1 1
1 2
1 3 ->2
--------------
1 4
2 0 ->3
2 1
--------------
2 2
2 3 ->4
2 4
--------------
3 0
3 1 ->5
3 2
--------------
3 3
3 4 ->6
4 0
--------------
4 1
4 2 discard
4 3
4 4 |
|
y****n
发帖数: 743 | 10 如果rand5()返回real number，你为什么认为：
rand5()产生[0,4]？ rand5()应该产生[0,5)
如果返回real number，这道题就没必要做了
rand5()/5*7即可 |
|
x******a
发帖数: 6336 | 11 can we do this: generate 6 rand5() iid, take
rand5()*10*5+ rand5()*10*4+...rand5()*10^0 % 7 |
|
w********p
发帖数: 948 | 12 嗯， 这个是经典答案。讨论到现在算是明白了。
之前其实看到答案，也不明白 1。 Rand5()* 5 + Rand5() 和 6＊ Rand5() 的区别 2
。 为什么是 5＊ Rand5() 而不是别的数6， 7， 8之类的。
谢谢大家及楼主的讨论，不然这题一直糊着。 |
|
w******j
发帖数: 185 | 13
是5 * (rand5() - 1) + rand5()吧...
rand5 generates 1 - 5.
6 * rand5怎么得到1？ |
|
c*****e
发帖数: 3226 | 14 一直没明白这道SB 题。
1）为何不是 9 * rand5 + rand5, 或者 8 * rand5？ 或者 (rand5 + 7 ) % 7
2） 怎么验证是均匀分布？
*( |
|
w**x
发帖数: 362 | 15 不行。 引为。。。
rand5() + rand5() are not equal distributed ... :)
5*rand5() is not equal dist. as well, but the hole is made up by another +
rand5().
Now, I think every thing is clear for everyone. |
|
t****t
发帖数: 6806 | 16 这是个老题我再说一遍:
N次调用rand5()产生的等概率状态数是5^N. 正确产生rand7()需要的等概率状态数必须
是7的倍数. 5^N永远不能被7整除. 所以任何试图用有限次调用rand5()来产生有限个
rand7()的算法, 从数学上都必定是错误的. 正确的算法必定有一个无限循环调用rand5
().
这就好比用5进制写1/7. 如果有人说他有一个写法能用有限位5进制数写出1/7, 你不用
看他的结果就知道他是错的. |
|
z**l
发帖数: 292 | 17 不是所有状态都要用吧。
提一个想法，大家轻拍。
用rand5()得到rand2()跟rand3()，留着用。
rand5() + rand3()一共情况如下：
0 ：0 + 0， 一种可能
1 : 0 + 1， 1 + 0, 两种可能
2 ： 0 + 2， 1 + 1， 2 + 0， 三种可能
3 ：三种
4 ： 三种
5 ： 两种
6 ： 一种
0,1直接输出，用rand2()过滤一下1跟5，rand3()过滤一下2,3,4。
rand5 |
|
r*********n
发帖数: 4553 | 18 idea:
first use rand5() to generate a binary random function with p = 1/7 as
follows
express 1/7 in base 5
e.g. 0.abc......
(Note if x can be expressed in base 5 with finite digits, after the last
digit, we assume an infinite number of 0s are padded)
check first digit a:
if rand5() < a return 1
else if rand5() > a return 0
else proceed to the next digit
similarly generate binary random functions with p=1/6, 1/5, ..... 1/2
denote these binary random functions as rand(), N = 2,3,...,7
if rand<7... 阅读全帖 |
|
r*******e
发帖数: 7583 | 19 6*rand5是调用一次rand5，把返回值乘以6
不是调用6次rand5 |
|
s*******r
发帖数: 197 | 20 carreercup那本书上有解释啊
int rand7() {
while (1) {
int num = 5*(rand5()-1) + rand5() - 1;
if (num < 21) return num % 7;
}
} |
|
m****u
发帖数: 3915 | 21 carreercup那本书上有解释啊
int rand7() {
while (1) {
int num = 5*(rand5()-1) + rand5() - 1; // 得出[0,24]的平均分布
if (num < 21) return num % 7; //只取前21个, 前21个也是平均分布,然后mod 7
就行了
}
} |
|
m*****k
发帖数: 64 | 22 莫非我看的书是旧版的？
那本书上先描述了怎么从rand2->rand3写。然后说
In order to generate a random number between 1 and 7, we just need to
uniformly generate
a larger range than we are looking for and then repeatedly sample until
we get a number that
is good for us. We will generate a base 5 number with two places with
two calls to the RNG.
int rand7() {
while (1) {
int num = 5*(rand5()-1) + rand5() - 1;
if (num < 21) return num % 7;
}
}
并没有解释怎么推到的。[0,24]的平均分布是怎么做出来的？谢谢
7 |
|
s*****i
发帖数: 355 | 23 你自己已经写出来了啊
5*(rand5()-1) 生成的是 0, 5,10,15,20各20％的概率
rand5()-1 是0,1,2,3,4各20％概率
两者相加，就是0-24各1/25的概率
天天啃算法，基本的概率和排列组合也要看看
mod |
|
y****n
发帖数: 743 | 24 简单证伪：
rand5()返回整数，只可能有5种不同值；
那么，(6*rand5()/4)也只会有5种不同值。所以不是rand7() |
|
t****t
发帖数: 6806 | 25 1. 如果不是所有状态都用, 那产生到那种状态就要重来. 这就是reject sampling的基
本原理. 总是有机会产生被拒绝的状态, 所以一定有无限循环.
2. 基于同样的原理, 不用无限循环是不可能从rand5()得到rand2()或者rand3()的, 更
不要说得到rand2()"和"rand3()了. rand2()和rand3()一共有6个状态, rand5()只有5
个...
概率论不难学, 不过肯定不是跟你这么拍脑袋的做法. 举反例前请自己想清楚先. |
|
M******l
发帖数: 479 | 26 这种题一般都是5*(rand5()-1)+rand5() 然后reject sampling |
|
t****t
发帖数: 6806 | 27 基本的概率问题: rand5()+rand5()能产生rand10()吗?
显然是不行的.
为什么不行? 想想吧. 两个独立随机数的相加是一个新的随机数, 但是一般来说新的分
布和两个旧的分布都不同.
number |
|
y****n
发帖数: 743 | 28 这道题相对高效一点的算法是：
public int Rand7()
{
int num = 100;
while (num >= 21)
num = Rand5() * 5 + Rand5();
return num / 3; //或者 return num % 7;
} |
|
c********p
发帖数: 1969 | 29 cc150里的，讲解没看明白，神马意思阿？
怎样能做到equally distributed?
为何5*rand5 + rand5 然后又不考虑后边几个数？。。。不懂阿不懂。。。 |
|
c********p
发帖数: 1969 | 30 为何 5*rand5 + rand5 而不直接用 6rand5? |
|
z****e
发帖数: 54598 | 31 rand5只能产生整数
如果返回值是double的话
rand5其实可以产生任何范围内的数 |
|
c********p
发帖数: 1969 | 32 阿？？
更不懂了。。。
我想产生0到24, 6个4就可以了阿。。。就是6个rand5阿。。。
rand5只能产生4的倍数到0的吧？ |
|
z****e
发帖数: 54598 | 33 不行，分布会重叠
比如你想产生10以内的随机数
那么很天真地以为rand5+rand5就行了
但是实际上
4＝2＋2＝1＋3＝3＋1＝4＋0＝0＋4，这么多种组合
但是0只有0+0才行
所以产生0的概率和产生4的概率是不一样的 |
|
g*********e
发帖数: 14401 | 34
9rand5+rand5 is OK
(rand5+7)->(7,11) wrong! |
|
c*******L
发帖数: 125 | 35 这个答案我觉得不严谨
rand5()产生的是[1,5]的均匀分布
但是最后产生的rand7()却是[0,6]的
应该再稍微修改一下
7 |
|
E*******0
发帖数: 465 | 36 1. rand5()->rand2() and rand4();
2. we can find 11/12/13/14/21/22/23/24, and we can find uniform 12/13/14/21/
22/23/24.
for 1. If we have 5 balls (1,2,3,4,5), the prob of choosing each ball is 1/5
. If we only choose 3,4,5, the prob of choosing each ball (one of 3,4,5) is
1/3. So we can easily get rand2() and rand4().
for 2. since all the 8 cases are uniformly distributed, when we choose the
first ball as 1 and choose the second ball as 1, we just ignore it.
So we can get 7 cased uniformly distr |
|
h********0
发帖数: 74 | 37 rand5()/4产生[0,1]. 0和1 的产生概率是不相等的
|
|
|
j**7
发帖数: 143 | 39
我以为rand5()得出的是real number. |
|
h***i
发帖数: 1970 | 40 是吗？那么reject sampling的原理就有问题了。
rand5 |
|
z**l
发帖数: 292 | 41 刚查了下书，rand5()我的定义是0到4，跟书上不一样，不过结论应该一样。 |
|
L********e
发帖数: 159 | 42 这个不保证有限次实验内实现。rand5在有限次实验中只能产生5的幂种状态，不可能被
7整除从而实习均匀的rand7。最直观有效的方法就是rejec sampling吧。 |
|
z**l
发帖数: 292 | 43 不好意思，当初概率就没学好，现在怎么拍脑袋都没用。
有个问题没搞懂，如果给定rand5(我假定完美等概率输出0, 1, 2, 3, 4),如果大于等
于2的不输出，那么输出0或1的概率是多少？
如果这个问题理论上没有解，但是面试中碰到了总要给出一个最接近的算法。哪个方法
可以当答案呢？
5 |
|
t****t
发帖数: 6806 | 44 你要搞清楚>=2的不输出的意思. "不输出"是指如果出现>=2的情况, 就重来一次. 你不
能说使用者调用一次rand2()却没有得到结果, 对吧. 按照这个算法, 输出0或1的概率
就是1/2.
关键点在于"重来"是不能避免的, 而且一定是不定次数的重来. 凡是用有限次rand5()
产生rand7()(或者rand2(), rand3())的算法, 都一定是错的. |
|
w********p
发帖数: 948 | 45 没写清楚，我是想产生 用rand5() which create 1 to 5 to implement rand7() to
generate random number from 1 to 7 . 和楼主的原题有点点差别。思路相思。
不好意思，让大家迷惑了。不过还是多了个 0； 还是要修改下。 |
|
j********x
发帖数: 2330 | 46 就用fair coin simulate arbitrary probability的思路
分7分，不停rand5，产生完全处在某个区间内的就结束 |
|
w******j
发帖数: 185 | 47
我说错了，我想说的是，6*rand5只能有6的倍数.... |
|
g*********e
发帖数: 14401 | 48
5rand5+rand5 可以产生一个0-24的随机数 equally distributed
然后取前面21个 0/1/2->0 3/4/5->1 ...
22-24的话discard 再算一次 |
|
u*****o
发帖数: 1224 | 49 既然这个题的思路是equally distributed那么我们的目标就是每个数只有一种
表达式，那么可不可以GENERALIZE成下面的CASE呢
rand3 to rand5 => 3*rand3+rand3 map to 0-8; delete 5-8, map 0-4 to 0-4 by %5
（当然这个例子没什么意义）
rand7 to rand11 => 7*rand7+ rand7 map to 0-48; delete 40-48, map 0-39 to 0-
10 by %11; |
|
c********p
发帖数: 1969 | 50 我知道这道题我卡在什么地方了。
凭我对这个equally distributed 的理解，应该 sum P(i) = 1
但这个题目里，是做不到的，只要求 P(0) = P(1) = ... P(6) 就可以了。。。
既然这样，他完全可以用 5rand5 + rand5 只有， 去 前7个， 这样每个出现的概率是
1／25， sum(P(i)) = 7/25 也可以阿？
如果按答案那样 %7，每个出现的概率是3/25, sum(P(25)) = 21/25. |
|
