一种随机抽题的简朴算法

随机抽题是许多有关测验软件常常会碰着的问题，设相关题库中有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()一直饱受垢病，专业人员一直寻求更好的随机数生成算法，这方面有许多参考资料，请读者查阅，本文不再赘述。读者可思量将随机数生成算法整合到本文的随机抽题算法中，以得到更好的随机抽题算法。