《编程珠玑》--读书笔记12章：取样问题

 第十二章，作者提出了一个问题：程序的输入包含两个整数m和n,其中m < n。输出是0~n- 1范围内的m个随机整数，不允许重复

有两种方法达到目的：

1.思路：从r个剩余的整数中选出s个，以概率s/r来选择下一个数：

比如，m=2,n = 5,选择第一个数的时候：rand()%n < m是否成立。0是否被选中，那么依赖于rand()%5是否小于m。A:如果成立，那么输出0;B：不成立，不输出0；

下一步：就判断1是否要被输出：

在A发生的情况下，1有1/4的概率输出；

在B发生的情况下，1有2/4的概率输出；

两种情况的不同，实际上是rand()%n < m此不等式中的m不同；

A：m = 1;B : m = 2; n 在两种情况下都是n - 1(相比于判断0是否输出的时候，因为总个数减少了一个)

不难写出下面的函数：

// genknuth:顺序输出随即不重复的数 void genknuth(int m, int n) { int i; srand((int)(time(0))); for(i = 0; i < n; i++) if(rand()%(n - i) < m) //以m/(n - i)的概率选择数目； { printf("%d ",i); m --; } }

注意在不等式成立的时候，m要自减；

2：按序列生成数，然后再随即交换（类似于洗牌程序）

void genbyme(int m, int n) { int i; int a[n]; int tmp; int index = 0; srand((int)(time(0))); for (i = 0; i < n; i ++) a[i] = i; for (i = 0; i < m; i ++) { tmp = a[i]; index = rand()%n; a[i] = a[index]; a[index] = tmp; } for (i = 0; i < m; i ++) printf("%d ", a[i]); }

两种方法的比较：

两种方法的结果都达到了，但是有细微的区别：

1.方法1输出的是按升序的输出的随机数，方法2输出的是乱序的随机数

2.方法2需要一个额外的数组来存放，空间复杂度为O(N)，而方法1没有此限制

测试程序及其结果：

# include <stdio.h> # include <stdlib.h> int main() { int m = 10, n = 100; genknuth(m, n); genbyme(m,n); return 0; }

测试结果：

genknuth:  9  12  22  34  39  46  50  74  91  96 
genbyme:  26  79  5  90  76  89  82  73  59  39