我在网上查到下面的方法,感觉方法还不错,几率比较平均。但是中的这部分代码好像有点错误,实现不了效果。希望高手帮帮看看!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; ①
/*以下根据题号产生题库部分省略*/
……
}
随机抽题是很多有关考试软件经常会遇到的问题,设相关题库中有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()一直饱受垢病,专业人员一直寻求更好的随机数生成算法,这方面有很多参考资料,请读者查阅,本文不再赘述。读者可考虑将随机数生成算法整合到本文的随机抽题算法中,以获得更好的随机抽题算法。

解决方案 »

  1.   

    如果要考虑题的抽取均匀的话,那就不是真正意义上的"随机"了。
    不过,最好的算法也确实是那样,像开彩票一样,把所有的球装在一个容器内。选中一个后,球会从容器中排除出去。在程序中要模拟容器这种东西,那就要用环形链表,vector,动态数组等结构了。其实这个程序写起来并不难,只要可以使用这些结构。
      

  2.   

    手上没有c的IDE,php下有更简单的办法!$arr = array('0','1','2','3','4','5','6','7','8','9','10');
    $arr_get_value = array_rand( $arr,6 );
    print_r($arr_get_value);这应该满足你的需求的了。我发现array_rand这个函数取出的随机key序列没有重复的!看手册里面并没有说明它不重复呀,太强了!
      

  3.   

    array_rand的工作原理是返回一个包含随机键名的数组。这样你就可以随机从数组中取出键名和值。这样完全保证了你所谓的"平均",而且没有重复!感谢php对数组支持的强大与方便吧!
      

  4.   

    谢谢ShadowSniper(青春不等人呀...) 提出的方法,这个方法我也使用过,确实不错!
    大家再帮我看看,我贴的那种算法是我从网上下载的,因为我没有调通,不知道那种算法是否可行.大家帮我试试,用php怎么实现,!
      

  5.   

    那个代码看了一下,只看到一个错误,就是在循环外部k需要初始化为0,否则 intArray [0] 就没有值了,后面的循环就没意义了(我还没有去验证)