• 隨機函數發生器的設計

假設你希望以各1/2的概率輸出0和1.你可以自由使用一個輸出0或1的過程BIASED-RANDOM。它以概率p輸出1，以概率1 - p輸出0，其中 0 < p < 1，但是你并不知道p的值。給出一個利用BIASED-RANDOM作為子程序的算法，返回一個無偏向的結果，即以概率1/2返回0，以概率1/2返回1。作為p的函數，你的算法的期望運行時間是多少？

算法分析：

已知BIASED-RANDOM可產生0和1，那么 1 - BIASED-RANDOM也產生1和0，且以1 - p的概率輸出1，以p的概率輸出0。

如果我們將1 - BIASED-RANDOM看做另外一個函數發生器，和BIASED-RANDOM組合成對被調用，有以下結論：

調用結果　　　　00　　　　　　01　　　　　10　　　　11

1的個數　　 　　0?? 1　　　　　　1　　 　　2

出現概率?? (1-p)*(1-p)　　(1-p)*(1-p)　　p*p　　p*(1-p)

那么，進行一次調用，出現1的個數的期望值為： 0 * (1-p)*(1-p)　+ 1 *　(1-p)*(1-p)　+ 1 *　p*p　+ 2 *　p*(1-p) = 1。進行4次成對調用，則1的期望個數為4。為什么要調用4次呢？因為BIASED-RANDOM產生0的概率和 1 - BIASED-RANDOM產生1的概率相等；BIASED-RANDOM產生1的概率和 1 - BIASED-RANDOM產生0的概率相等，那么4次剛好覆蓋了所有組合對（00,01,10,11），也可進行8次，16次等調用。當進行4次成對調用后，統計1出現的個數，若小于4次，則返回0；大于4次，則返回1（這里相當于將4次調用封裝為了一個函數）。但有個問題，等于4次該返回0還是1呢？（因為1的可能次數為0至8）所以，可進行大量成對調用，以使單個現象可被忽略。如，進行1024次調用，統計1的個數，小于1024返回0，否則返回1。

• 隨機概率發生器

題目：

已知一隨機發生器，產生0的概率是p，產生1的概率是1-p，現在要你構造一個發生器，使得它構造0和1的概率均為1/2

解決方案：

這是隨機概率發生器的典型題目。

由于需要產生1/2，而用1位0，或1位1無法產生等概率，因此，考慮將隨機數擴展成2位：

00?? p*p

01? p*(1-p)

10? (1-p)*p

11 (1-p)*(1-p)

有上述分析知道，01和10是等概率的，因此我們只需要產生01和10就行了。

于是可以，遇到00和11就丟棄，只記錄01和10。可以令，01表示0,10表示1，則等概率1/2產生0和1了。

擴展：

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

解答：

對n=2，認為01表示0、10表示1，等概率，其他情況放棄

對n=3，認為001表示1、010表示2，100表示3，等概率，其他情況放棄

對n=4，認為0001表示1、0010表示2，0100表示3，1000表示4，等概率，其他情況放棄

首先是1/2的情況，我們一次性生成兩個數值，如果是00或者11丟棄，否則留下，01為1，10為0，他們的概率都是p*(1-p)是相等的，所以等概率了。然后是1/n的情況了，我們以5為例，此時我們取x=2，因為C(2x,x)=C(4,2)=6是比5大的最小的x，此時我們就是一次性生成4位二進制，把1出現個數不是2的都丟棄，這時候剩下六個:0011,0101,0110,1001,1010,1100，取最小的5個，即丟棄1100，那么我們對于前5個分別編號1到5，這時候他們的概率都是p*p*(1-p)*(1-p)相等了。

關鍵是找那個最小的x，使得C(2x,x)>=n這樣能提升查找效率

• 平均要取多少個(0,1)中的隨機數才能讓和超過1

數學常數最令人著迷的就是，它們常常出現在一些看似與之毫不相干的場合中。 隨便取一個 0 到 1 之間的數，再加上另一個 0 到 1 之間的隨機數，然后再加上一個 0 到 1 之間的隨機數??直到和超過 1 為止。一個有趣的問題：平均需要加多少次，才能讓和超過 1 呢？答案是 e 次。

#define NUM 9999999 int main() { int sum=0; srand(time(NULL)); for (int i=0;i<NUM;i++) { double val=0; while(val <1) { val+=(rand()/(double)RAND_MAX); sum++; } } printf("%f\n",sum/(double)NUM); return 0; }

為了證明這一點，讓我們先來看一個更簡單的問題：任取兩個 0 到 1 之間的實數，它們的和小于 1 的概率有多大？容易想到，滿足 x+y<1 的點 (x, y) 占據了正方形 (0, 1)×(0, 1) 的一半面積，因此這兩個實數之和小于 1 的概率就是 1/2 。類似地，三個數之和小于 1 的概率則是 1/6 ，它是平面 x+y+z=1 在單位立方體中截得的一個三棱錐。這個 1/6 可以利用截面與底面的相似比關系，通過簡單的積分求得：

可以想到，四個 0 到 1 之間的隨機數之和小于 1 的概率就等于四維立方體一角的“體積”，它的“底面”是一個體積為 1/6 的三維體，在第四維上對其進行積分便可得到其“體積”

∫(0..1) (x^3)*1/6 dx = 1/24

依此類推， n 個隨機數之和不超過 1 的概率就是 1/n! ，反過來 n 個數之和大于 1 的概率就是 1 - 1/n! ，因此加到第 n 個數才剛好超過 1 的概率就是

(1 - 1/n!) - (1 - 1/(n-1)!) = (n-1)/n!

因此，要想讓和超過 1 ，需要累加的期望次數為

∑(n=2..∞) n * (n-1)/n! = ∑(n=1..∞) n/n! = e

• x&(x-1)表達式的意義

求下面函數的返回值(微軟) -- 統計1的個數

int func(int x) {int countx = 0;while(x){countx++;x = x&(x-1);}return countx; }

假定x = 9999

10011100001111

答案: 8

思路: 將x轉化為2進制，看含有的1的個數。

注:?每執行一次x = x&(x-1)，會將x用二進制表示時最右邊的一個1變為0，因為x-1將會將該位(x用二進制表示時最右邊的一個1)變為0。

?

判斷一個數(x)是否是2的n次方

#include <stdio.h>int func(int x) {if( (x&(x-1)) == 0 )return 1;elsereturn 0; }int main() {int x = 8;printf("%d\n", func(x)); }

注:

(1)?如果一個數是2的n次方，那么這個數用二進制表示時其最高位為1，其余位為0。

(2)?== 優先級高于&

本文轉自我愛物聯網博客園博客，原文鏈接：http://www.cnblogs.com/yydcdut/p/3878319.html，如需轉載請自行聯系原作者

總結

以上是生活随笔為你收集整理的一些数据结构的思想(3)的全部內容，希望文章能夠幫你解決所遇到的問題。

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