討論下算法導(dǎo)論第5章一道概率題

win_hate

原帖由 void_while 于 2008-7-13 09:49 發(fā)表
丟棄是不行的,丟棄的情況下返回什么呢?

套一個(gè)循環(huán)，生成的數(shù)若合格，則跳出 ，返回。若不合格，則繼續(xù)循環(huán)。

silverzi

本樓內(nèi)容完全跑題，實(shí)在對(duì)不起，全編輯掉。

[ 本帖最后由 silverzi 于 2008-7-13 10:15 編輯 ]

j_will

了不起

luckheadline

不明白為什么要用二分，這樣不行么？
random(a,b)=a+(b-a)*random(0,1)

jackin0627

“
   int n = 0;
    for(int i = 0; i < b; ++i){
        n += random(0, 1);
    }
    return n;
”
---------
這樣就嚴(yán)重破壞了概率的平均分布。

“
  我曾經(jīng)和同學(xué)討論過(guò)用random(0, 1)來(lái)產(chǎn)生目標(biāo)數(shù)的二進(jìn)制位，但問題在于，當(dāng)目標(biāo)數(shù)不是2^n時(shí)無(wú)法做到等概率
”
可以先生成一個(gè)范圍比較大的隨機(jī)數(shù)然m，然后再取模來(lái)得到你想要的數(shù)n，
這樣當(dāng)然也不是絕對(duì)的等概率。但當(dāng)m遠(yuǎn)遠(yuǎn)大于n時(shí)，誤差就很少了。
如：
  你要得到的數(shù)的范是0～N，生成的隨機(jī)數(shù)M=N+1時(shí)，
  1~N的根率是（1/N）
  0的概率是（2/N）
  當(dāng)M = 10*N + 1 時(shí)
  1~N的概率變成了  10/(10*N) ＝ 1/N
  0的概率變成了       11/(10*N)
  誤差是不是小了很多。

breakhearts

我的想法是這實(shí)際上就是完成2^p到(b-a+1)上的一個(gè)映射，因?yàn)槿绻�我只能做得是運(yùn)行ra
ndom(0,1)，運(yùn)行p次，所有可能的{0,1}序列都是等概率的，如果2^p可以整除(b-a+1)是很
簡(jiǎn)單的情形，如果不存在這樣的p的話按以下處理，
1.選擇最小p，使得2^p>b-a+1
把2^p個(gè){0,1}序列分成b-a+1和剩下的部分，如果出現(xiàn)前面的情況，直接返回對(duì)應(yīng)映射到(
b-a+1)的值，如出現(xiàn)后面的情況重新實(shí)驗(yàn).寫成偽代碼就類似。
random(a,b)
{
choice smallest p,s.t 2^p>b-a+1;
rs=0
for i=1 to p
     rs+=2*(random(0,1))
if rs<=b-a+1
    return rs+a
else
     random(a,b)
}

breakhearts

上面算法誤差是0，但是運(yùn)行時(shí)間可能會(huì)無(wú)限

tassard

又來(lái)做作業(yè)啦 倒

yaya_aoyu

原帖由 zylthinking 于 2008-7-10 01:05 發(fā)表
不知行不行， random(0, 1)和int random(int a, int b)假設(shè)不是同一個(gè)函數(shù)， 因此int random(int a, int b)中沒作相應(yīng)邏輯

int random(int a, int b){
    if(a == b){
        return a;
    }

    a ...

這種解法是有問題的，例如當(dāng)n=5,random_private(5)

n = 0;
for( int i=0; i<5; ++i)
n+=RANDOM(0,1);

問題是n的可能結(jié)果只有如下6種，分別為0，1，2，3，4，5
而這5個(gè)數(shù)生成的概率是不一樣的，分別為
0  ==> (1/2)^5
1 ==> (1/2)^5*5
2 ==>  (1/2)^5*10
3 ==> (1/2)^5*10
4 ==> (1/2)^5*5
5 ==> (1/2)^5
那么相應(yīng)的輸出概率也是不相等的。

8樓正解。

kenby

描述random(a, b)過(guò)程的一種實(shí)現(xiàn)，它只調(diào)用random(0,1)。作為a和b的函數(shù)，你的程序期望運(yùn)行時(shí)間是多少？

這個(gè)題目相當(dāng)于在能隨機(jī)生成0,1的前提下，要求生成[0, 1, ...,n-1]范圍內(nèi)的一個(gè)整數(shù)
1 求出最小的 m，使2^m >= n-1
2 通過(guò)random(0,1)，產(chǎn)生一個(gè)m比特的整數(shù)，這樣能隨機(jī)產(chǎn)生[0, 2^m-1]內(nèi)的整數(shù)，若產(chǎn)生的整數(shù)位于[0, n-1]內(nèi)，則取這個(gè)數(shù)作為結(jié)果。如果這個(gè)數(shù)在[0,n-1]外，則丟棄它，再次運(yùn)行算法重新生成一個(gè)。

        a) 證明上述算法可以產(chǎn)生 [0, n-1]范圍內(nèi)的隨機(jī)數(shù)
在范圍[0,1, ..., n-1, n, ..., 2^m-1]范圍內(nèi)，總共有p = 2^m個(gè)數(shù)，其中合法的數(shù)是[0, 1, ..., n-1]共n個(gè)，非法的數(shù)為
[n, ..., 2^m-1]共q = 2^m-n個(gè)，則有 n + q = p
算法最后會(huì)產(chǎn)生一個(gè)合法的隨機(jī)數(shù)，假設(shè)得到數(shù)i的概率為Pi，0 <= i <= n-1， 則

所以上述方法可以產(chǎn)生隨機(jī)數(shù)

        b) 求算法運(yùn)行的期望時(shí)間
設(shè)Pi表示產(chǎn)生隨機(jī)數(shù)時(shí)運(yùn)行了i次算法的概率，那么前i-1次產(chǎn)生的都是非法的數(shù)，第i次產(chǎn)生的是合法的數(shù)，所以

那么