從 n 個數種選出 m 個數，隨機
思路來源于《編程珠璣》和 TAOCP
問題來源：http://topic.csdn.net/u/20110920/20/94c9eba8-ccdf-44eb-b9bc-f2707ca78c99.html
http://hi.baidu.com/unixfy/blog/item/f064063266f1cdc9a3cc2b81.html
解法：
for (int i = 0; i != n; ++i)
{
if (rand() % (n - i) < m)
{
printf("%d ", a[i]);
--m;
}
}
重點在于該循環。
遍歷整個 n 個元素的數組，隨機生成一個數，這個數為 0 - (n - i) 之間，判斷其是否小于 m
i 每次循環自加，所以說對于最大的數只有 m / n 幾率被選中，如果前面 n - m 次都沒有選中元素，那么在 n - m + 1 次就必須選中一個元素，幾率是 100% 的，后面的也是 100%。
選中一個元素則 m 自減，對剩下的 n - i 個元素還有 m - j 個元素需要選擇。每個元素被選中的概率是一樣的即 m / n, 不被選中的概率也是一樣的，即 (n - m) / n 。
一個循環 O(N) 的時間復雜度。
1 #include <stdio.h>
2 #include <time.h>
3 #include <stdlib.h>
4
5 void foo(int a[], int n, int m)
6 {
7 srand(time(0));
8 for (int i = 0; i != n; ++i)
9 {
10 if (rand() % (n - i) < m)
11 {
12 printf("%d ", a[i]);
13 --m;
14 }
15 }
16 printf("\n");
17 }
18
19 int main()
20 {
21 int a[35];
22 for (int i = 0; i != 35; ++i)
23 {
24 a[i] = i;
25 }
26 foo(a, 35, 8);
27 return 0;
28 }
posted on 2011-09-22 23:48
unixfy 閱讀(1508)
評論(1) 編輯 收藏 引用