从 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 阅读(1492)
评论(1) 编辑 收藏 引用