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

void_while

5.1-2 用random(0,1)來實(shí)現(xiàn)random(a,b),并估計(jì)運(yùn)行時(shí)間.

想到一種解法,分治法:
     1.分解,將a-b區(qū)間分成2部分,通過random(0,1)控制,則進(jìn)入前半部和后半部的概率是一樣的;
     2.遞歸的處理前后兩個(gè)部分,若問題足夠小,即落到某個(gè)具體位置上時(shí),則直接返回;

偽代碼:
int random( a, b )
{
   if( a == b )
     return a;
   if( random( 0, 1 ) )
     return random( a, (a+b)/2 );
   else
     return random( (a+b)/2 + 1, b );
}

但仔細(xì)分析下發(fā)現(xiàn)有問題.

令 n = b-a, 問題簡化為 1/n = f( 1/(2^x) ),
                root
                 / \
                0    1
               / \   / \
             /   .....   \
            0 .........  1
時(shí)間復(fù)雜度為 O(lgn),通過lgn次random(0,1)調(diào)用,即生成長度為lg(b-a)的"前后后前..."隨機(jī)序列來控制最后落定的位置,類似2叉決策樹的決策過程,x次random(0,1)調(diào)用最多可能產(chǎn)生2^x條路徑,即最多可能返回2^x種結(jié)果,每條路徑的產(chǎn)生概率相等,即1/(2^x).

但如果n不是2的整數(shù)次方,不可能將概率平均分配到每條路徑,所以不可能在有限次調(diào)用內(nèi)生成精確的平均返回概率.

如, n=8時(shí),可以取x=3,正好8種返回結(jié)果的概率一樣,都是1/8.但如果n=7,那么b的返回概率可能會(huì)是2/8,其余值的返回概率均為1/8.
  
所以得到的結(jié)果是不精確的,上網(wǎng)查了很久,也沒找到答案

void_while

沒人理 自己偷偷頂下

有人一起做題玩么?

zylthinking

不知行不行， 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;
    }

    assert(b > a);
    int n = b - a;
    return a + random_private(n);
}

int random_private(int b){
    if(b % 2){
        int half = b / 2;
        if(random(0, 1) == 0){
            return random(0, half);
        }
        return random(half + 1, b);
    }

    int n = 0;
    for(int i = 0; i < b; ++i){
        n += random(0, 1);
    }
    return n;
}

void_while

贊,應(yīng)該就是樓上的思路!
我咋想不到呢

win_hate

原帖由 void_while 于 2008-7-8 23:24 發(fā)表
5.1-2 用random(0,1)來實(shí)現(xiàn)random(a,b),并估計(jì)運(yùn)行時(shí)間.

想到一種解法,分治法:
     1.分解,將a-b區(qū)間分成2部分,通過random(0,1)控制,則進(jìn)入前半部和后半部的概率是一樣的;
     2.遞歸的處理前后兩個(gè)部分 ...

按書上的記號(hào)，random(3,7) 應(yīng)該隨機(jī)生成 3,4,5,6,7 中的一個(gè)。你好像只生成 4 個(gè)數(shù)。

win_hate

原帖由 zylthinking 于 2008-7-10 01:05 發(fā)表
int random_private(int b){
    if(b % 2){
        int half = b / 2;
        if(random(0, 1) == 0){
            return random(0, half);
        }
        return random(half + 1, b);
    }

    int n = 0;
    for(int i = 0; i < b; ++i){
        n += random(0, 1);
    }
    return n;
}

看不懂，后面累加的含義是什么？

慮而后能得

呵呵 頂一下 樓主還是比較強(qiáng)的

win_hate

這個(gè)題目相當(dāng)于在能隨機(jī)生成 0, 1 的前提下，要求隨機(jī)生成 n 個(gè)整數(shù)。

把要生成的數(shù)標(biāo)記為 0,1,2,..., n-1

取最小的 m，使得 2^m >= n-1

通過隨機(jī)生成 0,1 的函數(shù)生成一個(gè)  m 比特整數(shù)（隨機(jī)生成每一位），這樣能隨機(jī)生成 [0, 2^m) 內(nèi)的整數(shù)。

隨機(jī)生成一個(gè) [0,2^m) 中的整數(shù)，如果這個(gè)數(shù)大小在 [0,n-1] 內(nèi)，則取這個(gè)數(shù)為結(jié)果。
如果這個(gè)數(shù)在 [0,n-1] 外，則丟棄它，重新生成一個(gè)。

[ 本帖最后由 win_hate 于 2008-7-12 11:46 編輯 ]

tyc611

原帖由 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 ...

1. 你的random(b)應(yīng)該產(chǎn)生[0, b]，因此，b % 2的判斷是錯(cuò)誤的（因?yàn)檫@里有b + 1個(gè)數(shù)）
2. 后面的循環(huán)產(chǎn)生的b + 1個(gè)數(shù)的每個(gè)數(shù)的概率是不均等的。舉個(gè)簡單的例子：產(chǎn)生0和b的概率為(1/2)^b，而不是期望的1/(b+1)。
   如果你寫成了n = n0 + n1 + n2 + .... + nb的形式，其中ni的產(chǎn)生概率為1/2，就很容易知道你方法有問題了

[ 本帖最后由 tyc611 于 2008-7-12 11:52 編輯 ]

tyc611

原帖由 win_hate 于 2008-7-12 11:43 發(fā)表
這個(gè)題目相當(dāng)于在能隨機(jī)生成 0, 1 的前提下，要求隨機(jī)生成 n 個(gè)整數(shù)。

把要生成的數(shù)標(biāo)記為 0,1,2,..., n-1

取最小的 m，使得 2^m >= n-1

通過隨機(jī)生成 0,1 的函數(shù)生成一個(gè)  m 比特整數(shù)（隨機(jī)生成每一位 ...

我曾經(jīng)和同學(xué)討論過用random(0, 1)來產(chǎn)生目標(biāo)數(shù)的二進(jìn)制位，但問題在于，當(dāng)目標(biāo)數(shù)不是2^n時(shí)無法做到等概率