從 n 個(gè)數(shù)種選出 m 個(gè)數(shù)，隨機(jī)
思路來源于《編程珠璣》和 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;
}
}
重點(diǎn)在于該循環(huán)。
遍歷整個(gè) n 個(gè)元素的數(shù)組，隨機(jī)生成一個(gè)數(shù)，這個(gè)數(shù)為 0 - (n - i) 之間，判斷其是否小于 m
i 每次循環(huán)自加，所以說對(duì)于最大的數(shù)只有 m / n 幾率被選中，如果前面 n - m 次都沒有選中元素，那么在 n - m + 1 次就必須選中一個(gè)元素，幾率是 100% 的，后面的也是 100%。
選中一個(gè)元素則 m 自減，對(duì)剩下的 n - i 個(gè)元素還有 m - j 個(gè)元素需要選擇。每個(gè)元素被選中的概率是一樣的即 m / n, 不被選中的概率也是一樣的，即 (n - m) / n 。
一個(gè)循環(huán) O(N) 的時(shí)間復(fù)雜度。
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 閱讀(1516)
評(píng)論(1) 編輯 收藏 引用