基于生成孪生素数算法的小型评测模型研究
2019-05-23孙金龙
孙金龙
摘要：孪生素数是指距离为2或1的相邻素数。可以通过编写程序的形式给出一定范围内的孪生素数组数。而对于指定孪生素数生成的算法，需要判定程序的可行性与正确性。该文研究一个程序评测系统模型，当用户提交了代码以后，系统会自动对代码进行编译，运行，最后得出相应的结果，作为评测结果反馈给用户。该模型用于校验指定算法的正确性，减少程序评测中的工作量。该文重点研究基于生成孪生素数算法的小型评测模型。
关键词：孪生素数；评测系统；JAVA
中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2019）05-0089-04
Research on Small Evaluation Model Based on Generating Twin Prime Algorithms
SUN Jin-long
（School of Data Science and Software Engineering，Baoding University， Baoding 071000， China）
Abstract： There is a more basic number in mathematics than integer numbers， prime numbers. The reason why prime numbers are important is that any integer larger than 1 can be decomposed into the product of prime numbers， and this product is unique. Twin primes are two adjacent prime numbers whose distance is 2. （stipulates that two prime numbers adjacent to 1 are also twin primes）. The number of twins elements in a certain range can be given in the form of programming. For the algorithm of generating twin primes， it is necessary to determine the feasibility and correctness of the program.In order to fulfill the above requirements， we need a small evaluation model， which is similar to the program evaluation system. When the user submits the code， the system automatically compiles and runs the code， and finally obtains the corresponding results， which are fed back to the user as the evaluation results. This model is used to check the correctness of the specified algorithm and reduce the workload in program evaluation. This paper focuses on the small evaluation model based on the generating Twin Prime algorithm. The following discussion is made for this model.
Key words： twin prime number； evaluation system；JAVA
1 前言
1.1 評测系统的概念和应用场景
评测系统是在编程中用来评测程序执行结果正确性的系统，通过该系统对程序的代码进行编译和执行，之后系统使用预设结果和程序输出结果进行比对，检测程序的正确性。对于程序设计的初学者而言，设计出全面的测试数据是较为困难的，如果一组数据、一组数据的逐个测试算法执行结果的正确性，又十分的浪费时间，而且容易造成测试不准确的情况。另一方面，由于对测试数据的考虑不够全面，在已完成的程序中往往有许多的边界数据没有考虑到，导致程序实质上是错误的，而程序设计者自己却没有察觉。因此算法评测系统用来检测结果的正确性就非常方便了。该系统的技术理论依据是软件工程方法学中的黑盒测试。研究目的主要是对算法进行自动化测试，校验指定算法执行结果的正确性，减少程序评测中的工作量。本文以孪生素数算法作为切入点，旨在研究一个一般化的小型评测模型。
1.2 孪生素数问题的描述
孪生素数问题多见于ACM竞赛中。是一类常见的具有代表性的算法，也是一个经典的数学问题。本文所述的孪生素数是指给出一百万以内的数，以算法的形式计算出该数范围内的全部孪生素数的组数（如10以内的孪生素数组为2和3，3和5，5和7共三组，则输出结果为3）。因此需要生成一百万条测试用例作为该算法的输入准备。
1.3 孪生素数问题的评测过程
首先给出正确程序生成的全部测试用例，通过I/O流输出到文件并且通过格式转换将所有测试用例生成到数据库中；
其次通过测试用例抽取程序从数据库中随机抽取五条包含正确结果的测试用例，并将待输入的测试用例与正确结果分离，将分离的待输入测试用例输入到正在执行的孪生素数算法中，将正确结果以文件的形式存储于本地计算机中，同时将待测算法执行结果输出到单独的文件中；
最终将正确答案文件内容与执行结果输出文件内容通过比对程序进行比对并返回测试结果到文件中。
实现技术： I/O流，java反射机制，线程。
1.4 数据流图
2 测试用例生成算法
2.1 功能描述
试用例生成算法的作用是生成正确的测试用例为评测系统的测试提供原始数据，生成的数据中包含一百万条测试数据及其对应的正确结果。由于生成的数据量较大，该算法不仅应当保证结果的准确性，还需要注意尽可能降低算法的时间复杂度，以保证运行效率。
2.2 核心代码
public static void main（String args[]）{
Scanner sc=new Scanner（System.in）；
int n=sc.nextInt（）；
int count=0；
try {
PrintStream out = new PrintStream（"f：//output.txt"）；//输出到文件
while（n-->0）
{
int m=sc.nextInt（）；
count=0；
for（int i=1；i<=m；i++）
{
if（PrimeNumber（i））
{
if（PrimeNumber（i-1））
count++；
if（PrimeNumber（i-2））
count++；
}
}
System.setOut（out）；
System.out.println（count）；
}
} catch （Exception e） {
e.printStackTrace（）；
}
}
static boolean PrimeNumber（int n）{
if（n<=3）
return n>1；
if（（n-1）%6！=0&&（n+1）%6！=0）
return false；
int tem=（int）Math.sqrt（n）；
for（int j=5；j<=tem；j+=6）
if（n%j==0||n%（j+2）==0）
return false；
return true；
}
3 抽取算法
3.1 功能描述
抽取算法即针对数据库中庞大的测试数据通过算法选择某几条测试用例作为待测程序的输入。通过与数据库的交互，获得测试用例。
3.2 流程图
3.3 核心代码
public String[] GainTest（） {
//获取数据库连接并返回抽取的结果集
ResultSet rs = DBConnection（）；
try {
//获取数据集中的正确答案
param = AquAns（rs）；
//获取数据集中的正确结果
String[] temp = AquAns（rs）；
for（int i=0；i System.setOut（out1）；//輸出到文件 System.out.println（temp[i]）； } } catch （Exception e） { e.printStackTrace（）； } return param； } 4 测试模型 4.1 功能描述 该部分是测试模型实现的核心。利用java反射机制，生成待测算法的class对象，启动一个单线程执行该对象的main方法，在抽取算法中获得的测试数据将通过标准输入流输入到待测试的孪生素数算法中，并将待测算法的输出结果以文件的形式保存起来。 4.2 流程图 4.3 核心代码 static int cnt = 5； static String[] temp=new String[cnt]； ReadRecordByJDBC rr=new ReadRecordByJDBC（）； String from = cnt+" "； public void run（） { temp = rr.GainTest（）； for（int i=0；i { from+=temp[i]+" "； } try { //将字符串转化为输入流 InputStream is = getStringStream（String.valueOf（from））； System.setIn（is）； //反射生成class对象 Class clazz = Class.forName（"com.oj.test.LuanShengSuShu"）； //获取该class对象的main方法
Method mainMethod = clazz.getMethod（"main"， String[].class）；
mainMethod.invoke（null，（Object）new String[]{""}）；
is.close（）；
} catch （Exception e） {
e.printStackTrace（）；
}
//输出答案比较
new CompareTxTFile（）；
}
5 比对算法
5.1 功能描述
该算法主要作用即对从数据库中获得的正确结果与通过孪生素数测试获得的结果以I/O流字符的形式逐行进行比对，并将评测结果一并输出到测试结果文件中。
5.2 流程图
6 测试
待测程序及测试结果
本节包含两个待测程序，分别给出测试结果中包含的全部两种情况。
待测程序1（输出正确结果）
public class TwinPrime {
static int[] prime = new int[1000005]；
public static void main（String[] args） {
int i， j， flag， T， M；
for （i = 2； i <= 1000000； i++）
// *筛选偶数/利用筛选法求素数
if （i % 2 == 0 && i > 2）
prime[i] = 0；
else
prime[i] = 1；
for （i = 3； i <= （int） Math.sqrt（1000000）； i += 2）// 奇数
{
if （prime[i] == 1）
for （j = i + i； j < 1000000； j += i）
prime[j] = 0；
}
Scanner sc = new Scanner（System.in）；
try {
PrintStream out = new PrintStream（"f：//output.txt"）；
T = sc.nextInt（）；
while （T-- > 0） {
M = sc.nextInt（）；
for （i = M， flag = 0； i >= 2； i--）
if （（prime[i] == 1 && prime[i - 1] == 1）
|| （prime[i] == 1 && prime[i - 2] == 1））
flag++；
System.setOut（out）；
System.out.println（flag）；
}
} catch （FileNotFoundException e） {
e.printStackTrace（）；
}
}
}
評测正确结果：
待测程序2（评测出错）
public class Test {
public static ArrayList
public static void main（String[]arg）{
int[] res=new int[1000005]；
int result=1；
res[3]=res[4]=1；
prime.add（2）；
prime.add（3）；
for（int i=5；i<1000005；i+=2）{
if（isPrime（i））{
prime.add（i）；
if（i-prime.get（prime.size（）-2）==2）{
result+=1；
}
}
res[i+1]=res[i]=result；
}
int num；
try {
PrintStream out = new PrintStream（"f：//output.txt"）；
Scanner in=new Scanner（System.in）；
num=in.nextInt（）；
for（int i=0；i System.setOut（out）； System.out.println（res[in.nextInt（）]+1）； } }catch （FileNotFoundException e） { e.printStackTrace（）； } } public static boolean isPrime（int num）{ for（int i=0；prime.get（i）*prime.get（i）<=num；i++）{ if（num%prime.get（i）==0） return false； } return true； } } 参考文献： [1] 臧双媛.C语言编程题在线评测系统的设计与研究[D].北京：北京交通大学，2017. [2] 晏燕.在线编程评测系统设计与实现[D].长春：吉林大学，2017. [3] 肖红玉，蓝荣祺，万志强.在线评测教学辅助系统设计与应用[J].电子设计工程，2017，25（23）：11-15. [4] 姚佳瑜.软件测试中的测试用例及复用研究[J].数字技术与应用，2018，36（1）：58-59. [5] 刘建亚.孪生素数猜想[J].数学通报，2014（1）. [6] 林围强.Java反射机制的研究[J].信息系统工程，2016（8）：109. [7] 周文刚，刘了一.程序设计结果在线即时评测系统的设计与实现[J].周口师范学院学报，2018，35（5）：87-89. 【通联编辑：谢媛媛】
