<b>一种随机抽题的简单算法</b>[VC/C++编程]

随机抽题是很多有关测验软件常常会碰到的问题,设相关题库中有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;j>k;j--)
　　　 intArray [j+1]= intArray [j];
　 intArray [k] =temp; ①
/*以下按照题号产生题库部份省略*/
……
}
free(intArray);上述做法的好处在于,没有任何附加存储空间,运算的复杂性大致上等于一个插入排序算法,但原始产生的题号次序已经“被忽视了”,增添一个有m个元素的附加数组,便可以保存原始产生的题号次序,比方intRandArray是一个有m个元素的附加数组,将①改成:intRandArray[i] =intArray [k]= temp;如此我们便可以已很小的时间与空间代价,实现了无反复并且各个试题被抽取的概率相同的随机抽题算法.但C语言中rand()一向饱受垢病,专业人员一向追求更好的随机数生成算法,这方面有很多参考资料,请读者查阅,本文不再赘述.读者可考虑将随机数生成算法整合到本文的随机抽题算法中,以得到更好的随机抽题算法.