一种随机抽题的简单算法
一种随机抽题的简单算法
作者：贵州大学 王 凯
随机抽题是很多有关考试软件经常会遇到的问题，设相关题库中有n道题，要从中抽取m ( m<=n ) 道题，这要首先产生m个随机数。在C语言中，一般的做法是:int *intArray;
int i;
time_t t;
intArray = malloc(m*sizeof(int));
/*time(&t)将获取当前时间，srand把当前时间作为随机数的种子*/
srand((unsigned) time(&t));
/*依次产生m个随机数*/
for(i=0; i<m; i++)
intArray[i] = rand() %n;
……
free(intArray);
这样，就可以产生m个随机数，方法很简单，并且利用了当前时间作为随机数的种子，尽量地避免了出现重复抽题。但仔细一分析，重复抽题并未完全避免，同时是否已抽题不影响今后的抽取，将导致各个试题被抽取的几率不等。修正的方法有检查新抽取的题是否重复，若重复则重抽，这样做的方法很简单，仅仅在上面的程序中加入判断重复的语句，但各个试题被抽取的几率仍然不等。怎样办呢？
我们可以将1到n的n个数看成是n个人围成一个圆形，先产生一个随机数round，从1开始数（超过n有将是1），当数到round时，round号人退出（以后数到round时将跳过）；接着又产生一个随机数round1，从前面的round一直数到round1（依次往下数，若经过round时将跳过），…，如此下去，一直到m个题都被抽取。
此方法表面看来很难，要设一个有n个元的集合，已被数到的元素将被删除，直到m个元素都被抽取为止，这样要有一个n（一般n>>m）个元的集合，将消耗较多的时间和空间资源。有没有更简单的方法呢？
先分析“退出”的影响。round退出后，小于round的编号不变，大于round的编号减一；round1退出后，小于round1的编号不变，大于round1的编号又要减一；…，这样就可以很简单的分析出一个简单的算法：依旧按前面所述的方法抽取随机数roundk，将roundk按n求余数，再将roundk与round1,
round2, …, roundk-1（此k-1个数已增序排列，roundk-1为前k-1次得到的随机数最大者）相比较，然后进入比较程序，先与round1比较，若roundk>=
round1，则roundk增一，再与round2比较，若roundk>= round2，则roundk再增一，…，这样就可以很简单地实现了无重复而且各个试题被抽取的几率相同的随机抽题算法。具体的做法是:int *intArray;
int i,j,k,temp;
time_t t;
intArray = malloc(m*sizeof(int));
srand((unsigned) time(&t));
/*依次产生m个随机数*/
for(i=0; i<m; i++){
temp= rand() %n;
/*查找temp原先的“真实”编号*/
for(j=0; j<i; j++)
if(temp= intArray[j])
temp++;
else{
/*temp应插在k位置处, 这样数组intArray就实现了排序，同时得到了temp原先的编号*/
k=j-1;
break;
}
for(j=i-1;jk;j--)
intArray [j+1]= intArray [j];
intArray [k] =temp; ①
/*以下根据题号产生题库部分省略*/
……
}
free(intArray);
上述做法的好处在于，没有任何附加存储空间，运算的复杂性大致上等于一个插入排序算法，但原始产生的题号顺序已经“被忽略了”，添加一个有m个元素的附加数组，就可以保留原始产生的题号顺序，例如intRandArray是一个有m个元素的附加数组，将①改为：
intRandArray[i] =intArray [k]= temp;
如此我们就可以已很小的时间与空间代价，实现了无重复而且各个试题被抽取的几率相同的随机抽题算法。但C语言中rand()一直饱受垢病，专业人员一直寻求更好的随机数生成算法，这方面有很多参考资料，请读者查阅，本文不再赘述。读者可考虑将随机数生成算法整合到本文的随机抽题算法中，以获得更好的随机抽题算法。
作者信息：
王 凯 （贵州省贵阳市花溪贵州大学数学系，邮编：550025）
邮箱：e_listen@163.com
