avatar
免费健康体检 (转载)# PennySaver - 省钱一族
j*7
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].
avatar
o*g
2
【 以下文字转载自 shopping 讨论区 】
发信人: Ookong (悟空), 信区: shopping
标 题: 免费健康体检
发信站: BBS 未名空间站 (Tue Feb 16 15:17:14 2010, 美东)
各位兄弟姐妹,身体是革命的本钱。CVS和To Your Health组织合作推出了一个
Community Health and Wellness Program,为以下几个城市的居民提供免费体检:
Dallas/Fort Worth, Houston, Los Angeles, Miami and San Antonio
具体的schedule,请查看。
http://www.asusalud.com/
To Your Health health fairs are a collection of health care screening
services coupled with the opportunities for an individual, or an entire
family, to consult directly with healt
avatar
l*8
3
random integers, not real numbers
avatar
b*f
4
顶,终于被include了一把!
avatar
h*0
5
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].

avatar
b*f
6
分特, 点开一看在irving
avatar
y*n
7
简单证伪:
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].

avatar
s*c
8
不只是整数的问题。你用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
avatar
p*p
9
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].

avatar
m*g
10
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;
}
avatar
j*7
11

我以为rand5()得出的是real number.

【在 l***8 的大作中提到】
: random integers, not real numbers
avatar
y*n
12
如果rand5()返回real number,你为什么认为:
rand5()产生[0,4]? rand5()应该产生[0,5)
如果返回real number,这道题就没必要做了
rand5()/5*7即可

【在 j**7 的大作中提到】
:
: 我以为rand5()得出的是real number.

avatar
y*n
13
你的算法返回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();

avatar
x*a
14
can we do this: generate 6 rand5() iid, take
rand5()*10*5+ rand5()*10*4+...rand5()*10^0 % 7
avatar
t*t
15
这是个老题我再说一遍:
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

avatar
h*i
16
是吗?那么reject sampling的原理就有问题了。

rand5

【在 t****t 的大作中提到】
: 这是个老题我再说一遍:
: N次调用rand5()产生的等概率状态数是5^N. 正确产生rand7()需要的等概率状态数必须
: 是7的倍数. 5^N永远不能被7整除. 所以任何试图用有限次调用rand5()来产生有限个
: rand7()的算法, 从数学上都必定是错误的. 正确的算法必定有一个无限循环调用rand5
: ().
: 这就好比用5进制写1/7. 如果有人说他有一个写法能用有限位5进制数写出1/7, 你不用
: 看他的结果就知道他是错的.

avatar
t*t
17
reject sampling有一个无限循环不是吗?当然作为一个可操作的算法, 这个循环真正变
成无限的机会是无限小.

【在 h***i 的大作中提到】
: 是吗?那么reject sampling的原理就有问题了。
:
: rand5

avatar
h*i
18
是的,被reject的sample,需要从新来,是loop.

【在 t****t 的大作中提到】
: reject sampling有一个无限循环不是吗?当然作为一个可操作的算法, 这个循环真正变
: 成无限的机会是无限小.

avatar
z*l
19
不是所有状态都要用吧。
提一个想法,大家轻拍。
用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, 你不用
: 看他的结果就知道他是错的.

avatar
z*l
20
刚查了下书,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 : 两种

avatar
t*t
21
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 : 两种

avatar
r*n
22
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
avatar
r*n
23
a simpler version of this problem could be using a fair coin to simulate an
unfair coin with probability p
avatar
L*e
24
这个不保证有限次实验内实现。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].

avatar
M*l
25
这种题一般都是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].

avatar
z*l
26
不好意思,当初概率就没学好,现在怎么拍脑袋都没用。
有个问题没搞懂,如果给定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
: 个...
: 概率论不难学, 不过肯定不是跟你这么拍脑袋的做法. 举反例前请自己想清楚先.

avatar
r*n
27
不是光数几种可能就行了,还要看没中可能出现的概率啊
你想想出现6的概率是多少?如果不是1/7,那么答案就是错的。

【在 z**l 的大作中提到】
: 不好意思,当初概率就没学好,现在怎么拍脑袋都没用。
: 有个问题没搞懂,如果给定rand5(我假定完美等概率输出0, 1, 2, 3, 4),如果大于等
: 于2的不输出,那么输出0或1的概率是多少?
: 如果这个问题理论上没有解,但是面试中碰到了总要给出一个最接近的算法。哪个方法
: 可以当答案呢?
:
: 5

avatar
t*t
28
你要搞清楚>=2的不输出的意思. "不输出"是指如果出现>=2的情况, 就重来一次. 你不
能说使用者调用一次rand2()却没有得到结果, 对吧. 按照这个算法, 输出0或1的概率
就是1/2.
关键点在于"重来"是不能避免的, 而且一定是不定次数的重来. 凡是用有限次rand5()
产生rand7()(或者rand2(), rand3())的算法, 都一定是错的.

【在 z**l 的大作中提到】
: 不好意思,当初概率就没学好,现在怎么拍脑袋都没用。
: 有个问题没搞懂,如果给定rand5(我假定完美等概率输出0, 1, 2, 3, 4),如果大于等
: 于2的不输出,那么输出0或1的概率是多少?
: 如果这个问题理论上没有解,但是面试中碰到了总要给出一个最接近的算法。哪个方法
: 可以当答案呢?
:
: 5

avatar
h*t
29
Then what if we generalize this question
given positive integers n>m,
how to generate randn() from randm() and vice versa
avatar
w*p
30
这里有个类似的题的解答。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。
有些糊的感觉。
avatar
y*n
31
(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此产生的数的概率是一样的,但是第六第七次

avatar
t*t
32
基本的概率问题: 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此产生的数的概率是一样的,但是第六第七次

avatar
r*n
33
其实有限次方法也不是不可行的,因为电脑都是finite precision。
比如我给的方法,1/7用base 5来表示,小数点后面有无穷循环位,但是实际上考虑10
位就足够了,因为5^(-10)已经很小了,如果觉得不够就用20位,30位。
这种方法模拟出来的rand7()和真正的rand7()在用起来是没有差别的,因为在rand7()
重复之前,你的counter已经溢出了。
avatar
w*p
34
谢谢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

avatar
w*p
35
你的解释有给我启发。
现在想请问下如果题目给的是 用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

avatar
r*n
36
我觉得是对的

【在 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 ) {

avatar
y*n
37
这个算法不对,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 ) {

avatar
y*n
38
这道题相对高效一点的算法是:
public int Rand7()
{
int num = 100;
while (num >= 21)
num = Rand5() * 5 + Rand5();
return num / 3; //或者 return num % 7;
}
avatar
w*p
39
没写清楚,我是想产生 用rand5() which create 1 to 5 to implement rand7() to
generate random number from 1 to 7 . 和楼主的原题有点点差别。思路相思。
不好意思,让大家迷惑了。不过还是多了个 0; 还是要修改下。

【在 y****n 的大作中提到】
: 这个算法不对,Rand7()的值范围应该是[0..6]。
: 你的算法有可能返回7。

avatar
w*p
40
嗯, 这个是经典答案。讨论到现在算是明白了。
之前其实看到答案,也不明白 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;
: }

avatar
j*x
41
就用fair coin simulate arbitrary probability的思路
分7分,不停rand5,产生完全处在某个区间内的就结束
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。