http://blog.163.com/kevinlee_2010/blog/static/16982082020120792429856/

百度的一個面試題目:

.已知一隨機發生器，產生0的概率是p，產生1的概率是1-p，現在要你構造一個發生器，?
使得它構造0和1的概率均為1/2；構造一個發生器，使得它構造1、2、3的概率均為1/3；…，?
構造一個發生器，使得它構造1、2、3、…n的概率均為1/n，要求復雜度最低。

初看確實有點頭暈，也沒什么思路。但是仔細想想為什么生成0和1的概率均為1/2，我們可以看成是生成0和1的概率是均等的。這樣想之后，似乎就沒那么不好理解了。

原始的隨機數生成器，生成0 的概率為p,生成1的概率為1-p,那么怎么構造才能使得生成0和1的概率相等呢。或者說有兩個獨立的事件的概率是相等呢？

這樣來做一下，讓該隨機數生成器生成兩個數，那么序列是00,01,10,11概率分別為 p*p,p(1-p),(1-p)p,(1-p)*(1-p)

很明顯，這四種情況中存在兩個獨立的事件概率是相等。也就是01和10，那么我把01看成是0,10看成是1，那么他們輸出的概率均為p(1-p)，其他的情況舍棄。這樣就得到了0和1均等生成的隨機器了。

思維在擴展一下，生成1,2,…n的概率分別是1/n，也就是均等的。那么我們可以想怎么生成一個序列，里面有n個獨立時間，概率是相等。而且我們能夠猜測到這些概率的形式為 p^x*(1-p)^y,如果要相等，那么x必須等于y.這樣就說明了序列中0和1的個數是相等的。而且這樣的情況必須有多與n個才行。

數學表示就是 C(2x,x) >=n ，我們只需要知道x就能夠知道序列要多長了。而且中間必定有超過n個概率為{p(1-p)}^x不相等序列。

問題就可以解決了。

為什么要讓1和0出現的次數相等，時間復雜度就最低呢？

4位數，如果是兩個1和兩個0，可以等概率輸出c(4,2) = 6

如果1個1和三個0，等概率輸出的數值為c(4,1) = 4

騰訊面試題:

已知有個rand7()的函數，返回1到7隨機自然數，讓利用這個rand7()構造rand10() 隨機1~10。

利用的方法和上個問題類似，如何能夠得到一個等概率的獨立事件。這個問題和上個問題不同的是，這里產生的序列，要變成和的形式或者其他的形式，那么概率就會發生變化了。

如果能夠得到一組等概率的數，不管是什么數，只要等概率而且個數大于10，那么問題就可以解決了。

發現(rand7()-1)*7+rand7(),可以等概率的生成1到49。

呵呵，這不就得了，只要把11-49砍掉就可以了。不過這樣的效率比較低。可以砍掉41-49，然后在把1-40映射到1-10，那么問題也就解決了。

騰訊面試題:

等概率采樣數據流中的數字。

比如從數據流中等概率的采樣k個數字。

怎么做呢？先拿到最開始的k個數字，然后以后的每個數字等概率的和這k個數字交換。那么就可以達到每個數字被抽取的概率是等概率的。

怎么證明呢？

采用歸納方法，假設前n個數字等概率的采樣k個數字，那么每個數字被采樣的概率為k/n,現在新來一個數字，變成了n+1個數字，那么每個數字被采樣的概率變位k/(n+1),我們要證明這個

這個問題在計算機程序設計藝術書中提到，叫Reservoir Sampling（蓄水池采樣），屬于隨機算法的一種。

現在假定存在了n個數字，來了第n+1個數字，那么第n+1個數字被選擇的概率是k/n+1,那么我們推算其他的數字被選擇的概率也是k/n+1

P(其余數字) = p(其余數字|第n+1個選擇)*p(第n+1個選擇) + p(其余數字|第n+1個不選擇)*p(第n+1個不選擇)

????????????????????? =? k/n*(1-1/k)*k/(n+1) + k/n*(n+1-k)/(n+1)

????????????????????? = k*(k-1) / (n *(n+1) ) + k*(n+1-k) / (n*(n+1))

????????????????????? = k*n/(n *(n+1))

????????????????????? = k/(n+1)

得證。其余數字被選擇的概率依然也是 k/(n+1)

這里的其余數字是指在n中已經被選中的數字。

描述RANDOM(a,b)的過程的一種實現，它只調用RANDOM(0,1)。作為a和b的函數，你的程序的期望運行時間是多少？
注：RANDOM(0,1)以等概率輸出0或者1，
????? 要求RANDOM(a,b)以等概率輸出[a,b]之間的數(整數)

?

解決方案：

???????? 1，取 n=b-a+1，取最小的正整數m，使得 2^m >= n
???????? 2，調用RANDOM(0,1)，輸出m-bit位整數N?? (? N >= 0 and N <= 2^m-1)
???????? 3，? if?? N >=0? and N <= b-a
????????????????????? then return a+N?????
??????????????? else 重新執行步驟 2
?
[a,b]之間每個數都是以 1/2^m 的概率輸出的 ?

總結

以上是生活随笔為你收集整理的概率生产器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。