《编程珠玑》--读书笔记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