一种随机抽题的简单算法

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

时间: 2024-11-02 17:19:43

一种随机抽题的简单算法的相关文章

控制随机抽中几率[ C# | Random ]

前言 关于这个算法也许(肯定)已经被发明,但是我.我身边的朋友.我的老师在这之前是不知道也没能想出来的,如果你不知道的话,那么也包括你了: ) 在这个范围内被首次提出应该算是"发明"的!!增加.减少随机抽中几率--我的好朋友狄鹏在三年前想到的一个算法,我现在拿出来发扬光大.此算法可用于题库随机抽题.赌博机控制出彩率,甚至俄罗斯方块等游戏,有广泛的用途!也希望能帮得到你! 强调 在随机的基础上增控制抽中几率,注意随机性!! 正文 一.文字解说: 为待随机抽取的集合每个项加一个权值,这个权

struts2 考试题数据库-考试题数据库抽题的随机算法,但实现后每次刷新或者再输入地址,显示的题总是变怎么办

问题描述 考试题数据库抽题的随机算法,但实现后每次刷新或者再输入地址,显示的题总是变怎么办 老师让写个struts2考试系统从考试题数据库抽题的随机算法,但实现后每次刷新或者再输入地址,显示的题总是变怎么办, 有个bug,就是每次刷新题目都会变,那学生做题不断刷新怎么办,怎么简单的解决呢,有例子代码最好了,最简单的解决是什么呢,本人学生一枚,刚开始学,这个问题纠结两天了,网上的都很笼统,求学习,求指导 解决方案 顶一下啊,求教育,求解答

LinkedList和List在三种简单算法中效率比较

.Net 框架提供了两种List类型,一种是基于链表的LinkedList, 一种是基于数组的List.那么在实际应用中到底采用哪种List,如何取舍呢?本文对两种类型在队列,堆栈和简单插入三种简单算法中的效率进行了一个比较. 首先先让我们来看一下List的初始容量Capacity对List的性能是否有影响. 测试方法:分别设置初始容量为0,64,255,1024. List插入的最大长度为1000,循环1000次,得到如下结果,单位为ms,下同. 算法/初始容量 0 64 255 1024 队

《Java特种兵》1.2 一些简单算法,你会如何理解

本文是<Java特种兵>的样章感谢博文视点和作者授权本站发布 1.2 一些简单算法你会如何理解 终于迎来第二次聚会的机会本节内容会轻松许多也许一盏茶的工夫就可以听完这个小故事. 注其实本节并不是讨论算法例子也会很简单如果你对算法很熟悉请跳过此节. 想要从一堆数据中找出一个max.min. 想要从100万个数字中找出最大的10个数字. 你的想法是什么你会如何找先排序再找或者摸不到头脑. 胖哥的一些方法也许会帮到你"想想学校里面排队.找人是怎么做的". 假如一个学校有几千人你要

管理-服务器简单算法,大转盘活动,中奖概率,靠谱吗????

问题描述 服务器简单算法,大转盘活动,中奖概率,靠谱吗???? public Integer getRand() { Integer result = null; int sum = 100;//后台可更改 int randomNum = new Random().nextInt(sum);// 随机生成1到sum的整数 if (randomNum == 1) { result = 1;// 一等奖 } else if (randomNum < 5) { result = 2; // 二等奖 }

java几种排序算法的实现及简单分析_java

本文实例讲述了java几种排序算法的实现及简单分析.分享给大家供大家参考.具体如下: package test; public class first { /*普通的插入排序*/ public void insertSort(int[] list) { int i, j; list[0] = -999; //相当于设置一个监视哨兵,不用判断是否越界, //但要求数组从第二个数开始即i=1开始存储 for (i = 1; i < list.length; i++) { j = i; while (

根据权重挑选通道的简单算法

当存在一批通道,根据权重,选择哪个通道去使用的简单算法. 利用随机数,数据区间,来获取通道. 通道权重越大,单位时间内使用该通道的概率会大一些. 代码 1 //利用了一个权重区间的比例问题,抓取随机数的可能性,来体现权重思想 2 public static void main(String[] args) { 3 //定义三个通道的权重,按随机数选拔使用哪个通道. 4 //A 10 B 70 C 30 5 //从数据库查询出list集合 6 ChannelD A=new ChannelD("A&

需求一种可以使流布局居中的算法

问题描述 需求一种可以使流布局居中的算法 之前找的算法都是一些每行排满再换下一行. 需求把流布局从中间开始排列的算法. 解决方案 问题描述得有点难理解,能详细点描述么? 我喜欢搞算法方面的,或许我可以帮你

用js实现简单算法的实例代码_javascript技巧

一.冒泡排序 var arr1=[3,9,2,7,0,8,4]; for(var i=0;i<arr1.length;i++){ for(var j=i+1;j<arr1.length;j++){ var temp=0; if(arr1[i]>arr1[j]){ temp=arr1[i]; arr1[i]=arr1[j]; arr1[j]=temp; } } } alert(arr1); 二.快速排序 var a=[3,5,0,9,2,7,5]; function quickSort(a