基于生成孿生素數(shù)算法的小型評測模型研究

孫金龍

摘要：孿生素數(shù)是指距離為2或1的相鄰素數(shù)?？梢酝ㄟ^編寫程序的形式給出一定范圍內(nèi)的孿生素數(shù)組數(shù)。而對于指定孿生素數(shù)生成的算法，需要判定程序的可行性與正確性。該文研究一個程序評測系統(tǒng)模型，當用戶提交了代碼以后，系統(tǒng)會自動對代碼進行編譯，運行，最后得出相應的結(jié)果，作為評測結(jié)果反饋給用戶。該模型用于校驗指定算法的正確性，減少程序評測中的工作量。該文重點研究基于生成孿生素數(shù)算法的小型評測模型。

關鍵詞：孿生素數(shù)；評測系統(tǒng)；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 評測系統(tǒng)的概念和應用場景

評測系統(tǒng)是在編程中用來評測程序執(zhí)行結(jié)果正確性的系統(tǒng)，通過該系統(tǒng)對程序的代碼進行編譯和執(zhí)行，之后系統(tǒng)使用預設結(jié)果和程序輸出結(jié)果進行比對，檢測程序的正確性。對于程序設計的初學者而言，設計出全面的測試數(shù)據(jù)是較為困難的，如果一組數(shù)據(jù)、一組數(shù)據(jù)的逐個測試算法執(zhí)行結(jié)果的正確性，又十分的浪費時間，而且容易造成測試不準確的情況。另一方面，由于對測試數(shù)據(jù)的考慮不夠全面，在已完成的程序中往往有許多的邊界數(shù)據(jù)沒有考慮到，導致程序?qū)嵸|(zhì)上是錯誤的，而程序設計者自己卻沒有察覺。因此算法評測系統(tǒng)用來檢測結(jié)果的正確性就非常方便了。該系統(tǒng)的技術理論依據(jù)是軟件工程方法學中的黑盒測試。研究目的主要是對算法進行自動化測試，校驗指定算法執(zhí)行結(jié)果的正確性，減少程序評測中的工作量。本文以孿生素數(shù)算法作為切入點，旨在研究一個一般化的小型評測模型。

1.2 孿生素數(shù)問題的描述

孿生素數(shù)問題多見于ACM競賽中。是一類常見的具有代表性的算法，也是一個經(jīng)典的數(shù)學問題。本文所述的孿生素數(shù)是指給出一百萬以內(nèi)的數(shù)，以算法的形式計算出該數(shù)范圍內(nèi)的全部孿生素數(shù)的組數(shù)（如10以內(nèi)的孿生素數(shù)組為2和3，3和5，5和7共三組，則輸出結(jié)果為3）。因此需要生成一百萬條測試用例作為該算法的輸入準備。

1.3 孿生素數(shù)問題的評測過程

首先給出正確程序生成的全部測試用例，通過I/O流輸出到文件并且通過格式轉(zhuǎn)換將所有測試用例生成到數(shù)據(jù)庫中；

其次通過測試用例抽取程序從數(shù)據(jù)庫中隨機抽取五條包含正確結(jié)果的測試用例，并將待輸入的測試用例與正確結(jié)果分離，將分離的待輸入測試用例輸入到正在執(zhí)行的孿生素數(shù)算法中，將正確結(jié)果以文件的形式存儲于本地計算機中，同時將待測算法執(zhí)行結(jié)果輸出到單獨的文件中；

最終將正確答案文件內(nèi)容與執(zhí)行結(jié)果輸出文件內(nèi)容通過比對程序進行比對并返回測試結(jié)果到文件中。

實現(xiàn)技術： I/O流，java反射機制，線程。

1.4 數(shù)據(jù)流圖

2 測試用例生成算法

2.1 功能描述

試用例生成算法的作用是生成正確的測試用例為評測系統(tǒng)的測試提供原始數(shù)據(jù)，生成的數(shù)據(jù)中包含一百萬條測試數(shù)據(jù)及其對應的正確結(jié)果。由于生成的數(shù)據(jù)量較大，該算法不僅應當保證結(jié)果的準確性，還需要注意盡可能降低算法的時間復雜度，以保證運行效率。

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 功能描述

抽取算法即針對數(shù)據(jù)庫中龐大的測試數(shù)據(jù)通過算法選擇某幾條測試用例作為待測程序的輸入。通過與數(shù)據(jù)庫的交互，獲得測試用例。

3.2 流程圖

3.3 核心代碼

public String[] GainTest（） {

//獲取數(shù)據(jù)庫連接并返回抽取的結(jié)果集

ResultSet rs = DBConnection（）；

try {

//獲取數(shù)據(jù)集中的正確答案

param = AquAns（rs）；

//獲取數(shù)據(jù)集中的正確結(jié)果

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 功能描述

該部分是測試模型實現(xiàn)的核心。利用java反射機制，生成待測算法的class對象，啟動一個單線程執(zhí)行該對象的main方法，在抽取算法中獲得的測試數(shù)據(jù)將通過標準輸入流輸入到待測試的孿生素數(shù)算法中，并將待測算法的輸出結(jié)果以文件的形式保存起來。

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 {

//將字符串轉(zhuǎn)化為輸入流

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 功能描述

該算法主要作用即對從數(shù)據(jù)庫中獲得的正確結(jié)果與通過孿生素數(shù)測試獲得的結(jié)果以I/O流字符的形式逐行進行比對，并將評測結(jié)果一并輸出到測試結(jié)果文件中。

5.2 流程圖

6 測試

待測程序及測試結(jié)果

本節(jié)包含兩個待測程序，分別給出測試結(jié)果中包含的全部兩種情況。

待測程序1（輸出正確結(jié)果）

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++）

// *篩選偶數(shù)/利用篩選法求素數(shù)

if （i % 2 == 0 && i > 2）

prime[i] = 0；

else

prime[i] = 1；

for （i = 3； i <= （int） Math.sqrt（1000000）； i += 2）// 奇數(shù)

{

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（）；

}

}

}

評測正確結(jié)果：

待測程序2（評測出錯）

public class Test {

public static ArrayListprime=new 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語言編程題在線評測系統(tǒng)的設計與研究[D].北京：北京交通大學，2017.

[2] 晏燕.在線編程評測系統(tǒng)設計與實現(xiàn)[D].長春：吉林大學，2017.

[3] 肖紅玉，藍榮祺，萬志強.在線評測教學輔助系統(tǒng)設計與應用[J].電子設計工程，2017，25（23）：11-15.

[4] 姚佳瑜.軟件測試中的測試用例及復用研究[J].數(shù)字技術與應用，2018，36（1）：58-59.

[5] 劉建亞.孿生素數(shù)猜想[J].數(shù)學通報，2014（1）.

[6] 林圍強.Java反射機制的研究[J].信息系統(tǒng)工程，2016（8）：109.

[7] 周文剛，劉了一.程序設計結(jié)果在線即時評測系統(tǒng)的設計與實現(xiàn)[J].周口師范學院學報，2018，35（5）：87-89.

【通聯(lián)編輯：謝媛媛】