程式設計珠玑第12章

正文

如何生成0~n-1内的m個随機整數

1、方法一

比如要從5個數裡選出2個數，第一個數的機率是2/5，第二個數的機率是1/4，然後是0/3

那麼現在已經很清楚了。

可以寫代碼如下：

for (int i = 0; i < n; ++i)
     if (rand() %(n-i) < m)
      {    cout << i << endl; 
            --m;
        }
           

2、方法二

可以用一個set，每生成一個随機，就去set裡面檢視一下有沒有在set裡面，如果沒有就插入進去，直到set大小為m.

其實用散列應該更快。

3、方法三

首先把生n個随機數（注意範圍），用第一章裡面講到的随機數唯一生成算法生成之後，取前面m個就可以了。

4、方法四

for (int j = n - m; j < n; ++j)
{
      int t = rand() % (j  + 1);  //注意取模的對象：生成[0,j]之間的随機數
      if (set.find(t) == set.end())
           set.insert(t); 
      else set.insert(j);   //注意放進去的數值。
}
           

習題

1、

參考答案

int bigrand()
{
      return RAND_MAX*rand() + rand();
}
int region(int l, int u)  //[l, u]
{
     ++u;
      return l + rand() % (u - l);
}
           

2、

算法導論中提到過這個問題，可以這樣設計一下，随機選擇一個數，随其後的m個數就被選中（假設這些數排列成圓形）。

3、當m < n/2時，

總共試了k次，則前面k-1次找到的數都是在集合中，那麼隻有第k次不在裡面，那麼機率

p = (m/n)^(k-1) * (n-m)/n

那麼期望是 連加 k = 1至無窮大，根據二項式分布可知，期望等于

n/(n-m) < 2

進而可知得證

4、這裡可以看一下算法導論裡面的中文版64頁的題目，把n個球投到m個框中，每個框中至少有一個球時，至少要投mlgm次。

     如果是n則是nlogn.

5、6、

7、非遞歸的代碼在正文中，是按照升序進行輸出。

      第二個問題，生成n個元素的m元子集的所有情況，應該可以使用DFS來進行處理。

8、先生成這些數，然後再按第一章的處理，生成亂序的情況。

     調用m次随機數函數生成器。輸出即可。

9、使用floyd的生成算法。

10、答案可能比較難想到。

問題：如何随機從n個對象中選擇一個對象，這n個對象是按序排列的，但是在此之前你并不知道n的值？具體些說，在事先并不知道行數的情況下，如何讀一個文本檔案，随機選擇并輸出一行？

證明： 解答：我們總是選擇第一行，并使用二分之一的機率選擇第二行，使用三分之一的機率選擇第三行，以此類推。在該過程結束的時候，每一行具有相同的選中機率（1/n，其中n是檔案的總行數）：

i = 0

while more input lines

with probability 1.0/++i

choice = this input line  //如果前面做了選擇，并不會break，而是直到最後一個為止。

print choice

證明：

當做第i步選擇（選擇第i行）時，選擇該行的機率為1/i，則不選擇的機率為(i-1)/i

對于一篇有n行的文檔，現需證明最終標明第i行的機率為1/n。

當最終選擇第i行，前（i-1）步的選擇對最終結果不會産生影響，第i步選擇的機率為1/i，即選擇第i行，第（i+1～n）步中均采取不選擇的動作，即對于任意j(i+1<=j<=n)，目前步的機率為(j-1)/j，那麼最終的機率為：

(1/i)*((i)/(i+1))*...*((n-1)/n) = 1/n

以一篇隻有6行的文檔為例，最終選擇第2行的機率為：

1/2*(2/3)*(3/4)*(4/5)*(5/6) = 1/6

擴充：

原問題可簡化為：

如何從n個有序對象中等機率地任意抽取1個，簡記為sample（n,1），其中n未知；

若将該問題改為：

如何從n個有序對象中等機率地任意抽取m個，簡記為sample（n,m），其中n未知；

分析：

若n已知，sample(n,m)是普通的抽樣問題；當n未知時，可否根據上述算法進行相應的轉化求解？

解決方案：

将sample(n,m)問題轉化為m個sample(n*,1)問題，更具體一點是，轉化為

sample(n,1);sample(n-1,1);sample(n-2,1)....;sample(n-m+1,1)問題。

仍然以一篇6行文檔為例，任取其中2行，做法如下：

第一遍，以如下機率選中一行：

1(1)   2(1/2)  3(1/3)  4(1/4)  5(1/5)  6(1/6)

假設選中第2行，接着機率修改如下：

3(1)  4(1/2)  5(1/3)  6(1/4)  1(1/5)

[說明]:當選中第2行，從第3行開始修改機率，并将第2行排除在外，繼續掃描，這樣能保證在剩下的5個數中仍然以等機率抽取其中的一個。

11、實際上如查刮到1，2，3以外的數，就繼續，是以看遇到這三個數中的哪一個，是以勝的機率是2/3,輸的機率是1/3