j**7
发帖数: 143 | 1 Cracking the Coding Interview 17.11
搞不明白书上的答案。
My solution is 6* rand5()/4.
rand5()产生[0,4],rand5()/4产生[0,1].
6*rand5()/4产生[0,6]. |
l***8
发帖数: 149 | 2 random integers, not real numbers |
h********0
发帖数: 74 | 3 rand5()/4产生[0,1]. 0和1 的产生概率是不相等的
【在 j**7 的大作中提到】
: Cracking the Coding Interview 17.11
: 搞不明白书上的答案。
: My solution is 6* rand5()/4.
: rand5()产生[0,4],rand5()/4产生[0,1].
: 6*rand5()/4产生[0,6].
|
y****n
发帖数: 743 | 4 简单证伪：
rand5()返回整数，只可能有5种不同值；
那么，(6*rand5()/4)也只会有5种不同值。所以不是rand7()
【在 j**7 的大作中提到】
: 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 | 5 不只是整数的问题。你用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 |
p*****p
发帖数: 379 | 6 rand5() % 2加6次行么
【在 j**7 的大作中提到】
: Cracking the Coding Interview 17.11
: 搞不明白书上的答案。
: My solution is 6* rand5()/4.
: rand5()产生[0,4],rand5()/4产生[0,1].
: 6*rand5()/4产生[0,6].
|
m*********g
发帖数: 170 | 7 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;
} |
j**7
发帖数: 143 | 8
我以为rand5()得出的是real number.
【在 l***8 的大作中提到】
: random integers, not real numbers
|
y****n
发帖数: 743 | 9 如果rand5()返回real number，你为什么认为：
rand5()产生[0,4]？ rand5()应该产生[0,5)
如果返回real number，这道题就没必要做了
rand5()/5*7即可
【在 j**7 的大作中提到】
:
: 我以为rand5()得出的是real number.
|
y****n
发帖数: 743 | 10 你的算法返回2的概率要远大于返回6的概率。
[0,1,2,3,4] + [0,1,2]
有三种可能返回2，一种可能返回6
【在 m*********g 的大作中提到】
: 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();
|
|
|
x******a
发帖数: 6336 | 11 can we do this: generate 6 rand5() iid, take
rand5()*10*5+ rand5()*10*4+...rand5()*10^0 % 7 |
t****t
发帖数: 6806 | 12 这是个老题我再说一遍:
N次调用rand5()产生的等概率状态数是5^N. 正确产生rand7()需要的等概率状态数必须
是7的倍数. 5^N永远不能被7整除. 所以任何试图用有限次调用rand5()来产生有限个
rand7()的算法, 从数学上都必定是错误的. 正确的算法必定有一个无限循环调用rand5
().
这就好比用5进制写1/7. 如果有人说他有一个写法能用有限位5进制数写出1/7, 你不用
看他的结果就知道他是错的.
【在 x******a 的大作中提到】
: can we do this: generate 6 rand5() iid, take
: rand5()*10*5+ rand5()*10*4+...rand5()*10^0 % 7
|
h***i
发帖数: 1970 | 13 是吗？那么reject sampling的原理就有问题了。
rand5
【在 t****t 的大作中提到】
: 这是个老题我再说一遍:
: N次调用rand5()产生的等概率状态数是5^N. 正确产生rand7()需要的等概率状态数必须
: 是7的倍数. 5^N永远不能被7整除. 所以任何试图用有限次调用rand5()来产生有限个
: rand7()的算法, 从数学上都必定是错误的. 正确的算法必定有一个无限循环调用rand5
: ().
: 这就好比用5进制写1/7. 如果有人说他有一个写法能用有限位5进制数写出1/7, 你不用
: 看他的结果就知道他是错的.
|
t****t
发帖数: 6806 | 14 reject sampling有一个无限循环不是吗?当然作为一个可操作的算法, 这个循环真正变
成无限的机会是无限小.
【在 h***i 的大作中提到】
: 是吗？那么reject sampling的原理就有问题了。
:
: rand5
|
h***i
发帖数: 1970 | 15 是的，被reject的sample，需要从新来，是loop.
【在 t****t 的大作中提到】
: reject sampling有一个无限循环不是吗?当然作为一个可操作的算法, 这个循环真正变
: 成无限的机会是无限小.
|
z**l
发帖数: 292 | 16 不是所有状态都要用吧。
提一个想法，大家轻拍。
用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
【在 t****t 的大作中提到】
: 这是个老题我再说一遍:
: N次调用rand5()产生的等概率状态数是5^N. 正确产生rand7()需要的等概率状态数必须
: 是7的倍数. 5^N永远不能被7整除. 所以任何试图用有限次调用rand5()来产生有限个
: rand7()的算法, 从数学上都必定是错误的. 正确的算法必定有一个无限循环调用rand5
: ().
: 这就好比用5进制写1/7. 如果有人说他有一个写法能用有限位5进制数写出1/7, 你不用
: 看他的结果就知道他是错的.
|
z**l
发帖数: 292 | 17 刚查了下书，rand5()我的定义是0到4，跟书上不一样，不过结论应该一样。
【在 z**l 的大作中提到】
: 不是所有状态都要用吧。
: 提一个想法，大家轻拍。
: 用rand5()得到rand2()跟rand3()，留着用。
: rand5() + rand3()一共情况如下：
: 0 ：0 + 0， 一种可能
: 1 : 0 + 1， 1 + 0, 两种可能
: 2 ： 0 + 2， 1 + 1， 2 + 0， 三种可能
: 3 ：三种
: 4 ： 三种
: 5 ： 两种
|
t****t
发帖数: 6806 | 18 1. 如果不是所有状态都用, 那产生到那种状态就要重来. 这就是reject sampling的基
本原理. 总是有机会产生被拒绝的状态, 所以一定有无限循环.
2. 基于同样的原理, 不用无限循环是不可能从rand5()得到rand2()或者rand3()的, 更
不要说得到rand2()"和"rand3()了. rand2()和rand3()一共有6个状态, rand5()只有5
个...
概率论不难学, 不过肯定不是跟你这么拍脑袋的做法. 举反例前请自己想清楚先.
【在 z**l 的大作中提到】
: 不是所有状态都要用吧。
: 提一个想法，大家轻拍。
: 用rand5()得到rand2()跟rand3()，留着用。
: rand5() + rand3()一共情况如下：
: 0 ：0 + 0， 一种可能
: 1 : 0 + 1， 1 + 0, 两种可能
: 2 ： 0 + 2， 1 + 1， 2 + 0， 三种可能
: 3 ：三种
: 4 ： 三种
: 5 ： 两种
|
r*********n
发帖数: 4553 | 19 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>() == 1 return 0
else if rand<6>() == 1 return 1
...
else if rand<2>() == 1 return 5
else return 6 |
r*********n
发帖数: 4553 | 20 a simpler version of this problem could be using a fair coin to simulate an
unfair coin with probability p |
|
|
L********e
发帖数: 159 | 21 这个不保证有限次实验内实现。rand5在有限次实验中只能产生5的幂种状态，不可能被
7整除从而实习均匀的rand7。最直观有效的方法就是rejec sampling吧。
【在 j**7 的大作中提到】
: Cracking the Coding Interview 17.11
: 搞不明白书上的答案。
: My solution is 6* rand5()/4.
: rand5()产生[0,4],rand5()/4产生[0,1].
: 6*rand5()/4产生[0,6].
|
M******l
发帖数: 479 | 22 这种题一般都是5*(rand5()-1)+rand5() 然后reject sampling
【在 j**7 的大作中提到】
: Cracking the Coding Interview 17.11
: 搞不明白书上的答案。
: My solution is 6* rand5()/4.
: rand5()产生[0,4],rand5()/4产生[0,1].
: 6*rand5()/4产生[0,6].
|
z**l
发帖数: 292 | 23 不好意思，当初概率就没学好，现在怎么拍脑袋都没用。
有个问题没搞懂，如果给定rand5(我假定完美等概率输出0, 1, 2, 3, 4),如果大于等
于2的不输出，那么输出0或1的概率是多少？
如果这个问题理论上没有解，但是面试中碰到了总要给出一个最接近的算法。哪个方法
可以当答案呢？
5
【在 t****t 的大作中提到】
: 1. 如果不是所有状态都用, 那产生到那种状态就要重来. 这就是reject sampling的基
: 本原理. 总是有机会产生被拒绝的状态, 所以一定有无限循环.
: 2. 基于同样的原理, 不用无限循环是不可能从rand5()得到rand2()或者rand3()的, 更
: 不要说得到rand2()"和"rand3()了. rand2()和rand3()一共有6个状态, rand5()只有5
: 个...
: 概率论不难学, 不过肯定不是跟你这么拍脑袋的做法. 举反例前请自己想清楚先.
|
r*********n
发帖数: 4553 | 24 不是光数几种可能就行了，还要看没中可能出现的概率啊
你想想出现6的概率是多少？如果不是1/7，那么答案就是错的。
【在 z**l 的大作中提到】
: 不好意思，当初概率就没学好，现在怎么拍脑袋都没用。
: 有个问题没搞懂，如果给定rand5(我假定完美等概率输出0, 1, 2, 3, 4),如果大于等
: 于2的不输出，那么输出0或1的概率是多少？
: 如果这个问题理论上没有解，但是面试中碰到了总要给出一个最接近的算法。哪个方法
: 可以当答案呢？
:
: 5
|
t****t
发帖数: 6806 | 25 你要搞清楚>=2的不输出的意思. "不输出"是指如果出现>=2的情况, 就重来一次. 你不
能说使用者调用一次rand2()却没有得到结果, 对吧. 按照这个算法, 输出0或1的概率
就是1/2.
关键点在于"重来"是不能避免的, 而且一定是不定次数的重来. 凡是用有限次rand5()
产生rand7()(或者rand2(), rand3())的算法, 都一定是错的.
【在 z**l 的大作中提到】
: 不好意思，当初概率就没学好，现在怎么拍脑袋都没用。
: 有个问题没搞懂，如果给定rand5(我假定完美等概率输出0, 1, 2, 3, 4),如果大于等
: 于2的不输出，那么输出0或1的概率是多少？
: 如果这个问题理论上没有解，但是面试中碰到了总要给出一个最接近的算法。哪个方法
: 可以当答案呢？
:
: 5
|
h***t
发帖数: 2540 | 26 Then what if we generalize this question
given positive integers n>m,
how to generate randn() from randm() and vice versa |
w********p
发帖数: 948 | 27 这里有个类似的题的解答。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。
有些糊的感觉。 |
y****n
发帖数: 743 | 28 (rand5() + rand5() +rand5() +rand5() + rand5() +rand5() +rand5() ) %7
不可行。
因为你不能保证结果是均匀的。
rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5()
结果为14的概率远远大于结果是0或28的概率。
thrust的解释是正确的，有限次rand5()不可能产生rand7()
number
【在 w********p 的大作中提到】
: 这里有个类似的题的解答。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此产生的数的概率是一样的，但是第六第七次
|
t****t
发帖数: 6806 | 29 基本的概率问题: rand5()+rand5()能产生rand10()吗?
显然是不行的.
为什么不行? 想想吧. 两个独立随机数的相加是一个新的随机数, 但是一般来说新的分
布和两个旧的分布都不同.
number
【在 w********p 的大作中提到】
: 这里有个类似的题的解答。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此产生的数的概率是一样的，但是第六第七次
|
r*********n
发帖数: 4553 | 30 其实有限次方法也不是不可行的，因为电脑都是finite precision。
比如我给的方法，1/7用base 5来表示，小数点后面有无穷循环位，但是实际上考虑10
位就足够了，因为5^(-10)已经很小了，如果觉得不够就用20位，30位。
这种方法模拟出来的rand7()和真正的rand7()在用起来是没有差别的，因为在rand7()
重复之前，你的counter已经溢出了。 |
|
|
w********p
发帖数: 948 | 31 谢谢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。
这个和最佳答案比，思路还是差很多。
【在 y****n 的大作中提到】
: (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 | 32 你的解释有给我启发。
现在想请问下如果题目给的是 用randM() 实现 randN() M
思路改是咋样的？ 是不是 M * randM() + randM() ; drop 掉 最后几个( M*M %N)
cases.
【在 s******c 的大作中提到】
: 不只是整数的问题。你用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
|
r*********n
发帖数: 4553 | 33 我觉得是对的
【在 w********p 的大作中提到】
: 谢谢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 ) {
|
y****n
发帖数: 743 | 34 这个算法不对，Rand7()的值范围应该是[0..6]。
你的算法有可能返回7。
【在 w********p 的大作中提到】
: 谢谢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 ) {
|
y****n
发帖数: 743 | 35 这道题相对高效一点的算法是：
public int Rand7()
{
int num = 100;
while (num >= 21)
num = Rand5() * 5 + Rand5();
return num / 3; //或者 return num % 7;
} |
w********p
发帖数: 948 | 36 没写清楚，我是想产生 用rand5() which create 1 to 5 to implement rand7() to
generate random number from 1 to 7 . 和楼主的原题有点点差别。思路相思。
不好意思，让大家迷惑了。不过还是多了个 0； 还是要修改下。
【在 y****n 的大作中提到】
: 这个算法不对，Rand7()的值范围应该是[0..6]。
: 你的算法有可能返回7。
|
w********p
发帖数: 948 | 37 嗯， 这个是经典答案。讨论到现在算是明白了。
之前其实看到答案，也不明白 1。 Rand5()* 5 + Rand5() 和 6＊ Rand5() 的区别 2
。 为什么是 5＊ Rand5() 而不是别的数6， 7， 8之类的。
谢谢大家及楼主的讨论，不然这题一直糊着。
【在 y****n 的大作中提到】
: 这道题相对高效一点的算法是：
: public int Rand7()
: {
: int num = 100;
: while (num >= 21)
: num = Rand5() * 5 + Rand5();
: return num / 3; //或者 return num % 7;
: }
|
j********x
发帖数: 2330 | 38 就用fair coin simulate arbitrary probability的思路
分7分，不停rand5，产生完全处在某个区间内的就结束 |
