考场随机分配算法研究.docVIP

考场随机分配算法研究 引言：本文采用数学建模建立随机分配考场和座位的数学模型，然后结合算法分析设计出考场随机分配算法，算法中提供了相应的控制机制来智能排除重复结果保证每一位考生获得的考场号和座位号的唯一性，并通过对影响排座算法复杂度问题的分析对算法进行优化。 随着高考人数的增加和计算机技术的发展，考场编排方式逐渐由人工编排转向了计算机自动排考。目前由于国内高考招生考试时间短，考生考点分散，各考点的考场容量不一致，各校的考场编排需求不同等因素使得考生考场号和座位号的生成方式尤为复杂，准确性和效率方面都有很高的要求。合理分配时间与空间资源以保证无冲突的发生，科学地解决考生编排和考场设置的问题是考试信息管理中的一项重要工作。本文中设计了用于实现计算机自动编排考场的随机分配算法，该算法具有执行效率高、通用性强、易于实现、随机性强的特点，对高考管理工作能起到很大的促进作用。 1 算法分析 设total 为报考相应专业的考生总人数，count为每个考场的人数最大考生数，rc为考场数，i为考生报名编号，设集合A为已生成的考场号和座位号的元数据集合。Ai为第i为考生的考场号和座位号的二元组。（Ai∈A） 2 数学建模 公式1：Aj f（a，b）0　　其中Aj A Aj为第j位考生的考场号和座位号，Aj应不在已生成的考生考场号与座位号集合中。 公式2：rc g（total， count） total/count+1当 total mod count≠0；其中rc为考场数 公式3：b h（count） Random（count）+1 公式4：a l（rc） Random（rc）+1 3 算法描述（java语言）： 3.1考场数目计算 根据公式2得到以下算法： int room total%count 0？total/count：total/count+1； 3.2设置已生成考号集合 int rncode new int [total][2]； 3.3设置考场随机编码 根据随机产生器得到考场编码： Random random new Random（）；//设置座位随机产生器 int coucer 0；//设置游标指针初值为0； 3.4考场号和座位号算法 根据公式1-4，采用循环为每一个考生计算并生成考场号和座位号，为生成考号提供了数据基础。 while（coucer total） int r 0，c 0； r random.nextInt（room）+1；//随机获得考场号 c random.nextInt（count）+1；//随机获得座位号 //判断当前考场号的当前座位是否在已生成集合中，如果在//重新生成并继续判断直到当前考场号和当前座位号不在//集合中时将其存入已生成集合。 for（int i 0；i coucer；i++） if（rncode[i][0] rrncode[i][1] c） r random.nextInt（room）+1； c random.nextInt（count）+1； i 0； rncode[coucer][0] r； rncode[coucer][1] c； coucer++； 4 算法总结 该算法首先采用数学建模建立随机分配考场和座位的数学模型，从而保证了算法的正确性和科学性。再结合算法分析，依据报考人数和考场最大人数为每一位考生随机生成考场号和座位号。为了保证考场号和座位号的唯一性，算法中提供了相应的控制机制来智能排除重复结果保证每一位考生获得的考场号和座位号唯一。该算法复杂度大，执行效率欠佳。 5 算法改进 5.1影响算法复杂度的主要原因 通过分析我们不难发现，上述算法的主要开销用在冲突检测上，所以改进算法的主要途径也应该放在改进检测算法上。 5.2改进方案 为了实现冲突域快速定位，我们设置一个长度为total的标志： boolean flag new boolean [total]； 通过检测第m位是否为true 即可检测冲突。考场号和座位号可依据如下公式算得： r m/total//获得考场号 c m%total//获得座位号 5.3改进算法实现 while（coucer total） //生成随机种子 int m random.nextInt（total）+1； //判断种子是否存在，若存在则重新生成 while（flag[m]） m random.nextInt（total）+1； flag[m] true； //设置标志位 //根据种子生成考场和座位 int r m/total； int c m%total； rncode[coucer][0] r； rncode[coucer][1] c； //游标自加 coucer++； 6改进算法总结 改进算法通过对影响排座算法复杂度的主要原因进行