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

win_hate

原帖由 tyc611 于 2008-7-12 11:51 發(fā)表

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

擴(kuò)大范圍，丟掉不合格的就可以了。

win_hate

比如一個(gè)機(jī)器，等概率吐出 1,2,3,4

如果把輸出的 4 全丟掉，則 1,2,3 是等概率的。

tyc611

原帖由 win_hate 于 2008-7-12 11:58 發(fā)表
比如一個(gè)機(jī)器，等概率吐出 1,2,3,4

如果把輸出的 4 全丟掉，則 1,2,3 是等概率的。

問題是去年不合格的后，需要重新產(chǎn)生，此時(shí)還會等概率嗎？我再好好想想

tyc611

原帖由 win_hate 于 2008-7-12 11:58 發(fā)表
比如一個(gè)機(jī)器，等概率吐出 1,2,3,4

如果把輸出的 4 全丟掉，則 1,2,3 是等概率的。

把合法子集和非法子集看作一個(gè)整體，這樣看來確實(shí)是等概率的

zylthinking

原帖由 win_hate 于 2008-7-12 11:36 發(fā)表


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

累加是奇數(shù)的情況下的處理， 因?yàn)橐�估�?jì)到嚴(yán)格的概率相等, 偶數(shù)可以根據(jù)random(0, 1)返回值進(jìn)入?yún)^(qū)間的前半部分或后半部分， 但如果區(qū)間不能均分， 則這個(gè)辦法不能用， 否則不能保證嚴(yán)格的等概率。 所以只能使用多個(gè)random(0, 1)相加達(dá)到這個(gè)效果： 這個(gè)效率比較低， 所以在偶數(shù)區(qū)間的情況下， 就不會使用了

zylthinking

原帖由 tyc611 于 2008-7-12 11:49 發(fā)表

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 ...

第一個(gè)算是小問題， 只是個(gè)思路而已， 也沒那么精確。
第二個(gè)問題我是我錯(cuò)了， 汗

[ 本帖最后由 zylthinking 于 2008-7-12 22:55 編輯 ]

tyc611

原帖由 zylthinking 于 2008-7-12 22:26 發(fā)表


第一個(gè)算是小問題， 只是個(gè)思路而已， 也沒那么精確。
第二個(gè)問題我有點(diǎn)不理解， 產(chǎn)生0的可能性怎么就應(yīng)該是(1/2)^b呢， 從[0, b]中產(chǎn)生一個(gè)任意數(shù)的概率應(yīng)該就是 1/(b + 1), 相當(dāng)于從b+1個(gè)雞蛋里面隨手挑 ...

你產(chǎn)生的數(shù)實(shí)質(zhì)上是這種形式：n = n1 + n2 + .... + nb的形式，其中ni ＝{0, 1}，概率分別為1/2
產(chǎn)生總的樣本數(shù)為2^b；產(chǎn)生的數(shù)0只有一個(gè)樣本（ni = 0 for all i form 1 to b），而產(chǎn)生的數(shù)1有b個(gè)樣本（分別為ni = 1 when i = k, ni = 0 when i != k, where 1 <= k <= b），所以產(chǎn)生數(shù)0和1的概率是不相等的。其它數(shù)的概率類似。

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

zylthinking

原帖由 tyc611 于 2008-7-12 22:43 發(fā)表

你產(chǎn)生的數(shù)實(shí)質(zhì)上是這種形式：n = n1 + n2 + .... + nb的形式，其中ni ＝{0, 1}，概率分別為1/2
產(chǎn)生總的樣本數(shù)為2^b；產(chǎn)生的數(shù)0只有一個(gè)樣本（ni = 0 for all i form 1 to b），而產(chǎn)生的數(shù)1有b個(gè)樣本（分別 ...

3x, 我理解了

silverzi

為什么不用浮點(diǎn)？

void_while

丟棄是不行的,丟棄的情況下返回什么呢?