在線判題系統(tǒng)設(shè)計與實現(xiàn)【畢業(yè)設(shè)計+開題報告+文獻(xiàn)綜述】

1、<p>　　本科畢業(yè)設(shè)計(論文)</p><p><b>　?。ǘ?屆）</b></p><p>　　在線判題系統(tǒng)設(shè)計與實現(xiàn)</p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級 計算機科學(xué)與技術(shù) </p>

2、<p>　　學(xué)生姓名 學(xué)號 </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p>　　摘要：計算機編程學(xué)習(xí)過程中，單單只接受老師所傳授的知識是不夠的,而要在課后自己進(jìn)行編程練習(xí)和鞏固老師

3、教的知識。而Online Judge系統(tǒng)很好的為我們提供了一個學(xué)習(xí)和練習(xí)的平臺。它可以對程序原代碼進(jìn)行編譯和執(zhí)行，并通過預(yù)先設(shè)計的測試數(shù)據(jù)來檢驗程序原代碼的正確性。</p><p>　　本課題結(jié)合計算機學(xué)科編程語言教學(xué)中的需求，利用Visual Studio 2010 功能強大的集成開發(fā)環(huán)境，使用ASP.NET和SQL Server后臺數(shù)據(jù)庫，開發(fā)了一個能夠?qū)崿F(xiàn)C/C++程序在線自動評判的網(wǎng)上編程學(xué)習(xí)系統(tǒng)。系統(tǒng)包

4、括前臺管理模塊和后臺判定模塊。本系統(tǒng)很好的為用戶提供了一個學(xué)習(xí)編程、掌握編程與編程交互的平臺。</p><p>　　關(guān)鍵詞：程序設(shè)計;在線判題;API;編譯器 </p><p>　　Design and implementation of the Online Judge </p><p>　　Abstract ：Computer programming learn

5、ing process, just only accepted the knowledge taught by the teacher is not enough, but to practice program and the consolidation of their teacher's knowledge in the after-school. The Online Judge system provides a go

6、od platform for learning and practicing. It can compile the program and execute source code, and test data through pre-designed to test the correctness of program source code.</p><p>　　This subject combines

7、the needs of learning computer programming, using Visual Studio 2008 which provides a powerful integrated development platform, ASP.NET and SQL Server 2005, to build this E-Learning system which can judge C/C++ programs.

8、 This system is divided into two parts: Front Management Module and Background Judgment Module.</p><p>　　Key words: Program; Online Judge ; API ; Compiler</p><p><b>　　目 錄</b></p&

9、gt;<p><b>　　1 引言1</b></p><p>　　1.1 課題背景、意義1</p><p>　　1.2 系統(tǒng)開發(fā)語言C++1</p><p>　　1.3 相關(guān)技術(shù)簡介3</p><p>　　1.3.1 .Net簡介3</p><p>　　1.2.3

10、 Visual Studio簡介4</p><p>　　1.2.3 SQL server 簡介4</p><p>　　2 研究的基本內(nèi)容及解決方法錯誤!未定義書簽。</p><p>　　2.1課題的基本內(nèi)容錯誤!未定義書簽。</p><p>　　2.2 要解決的技術(shù)難點及解決方法錯誤!未定義書簽。</p>&l

11、t;p>　　2.2.1 登陸信息管理錯誤!未定義書簽。</p><p>　　2.2.2 題庫的設(shè)計實現(xiàn)錯誤!未定義書簽。</p><p>　　2.2.3編譯的實現(xiàn)錯誤!未定義書簽。</p><p>　　3 系統(tǒng)總體設(shè)計與目標(biāo)10</p><p>　　3.1 系統(tǒng)設(shè)計的原則錯誤!未定義書簽。</p>&l

12、t;p>　　3.2 系統(tǒng)設(shè)計方法12</p><p>　　3.3 系統(tǒng)結(jié)構(gòu)8</p><p>　　3.4 系統(tǒng)結(jié)構(gòu)圖8</p><p>　　3.1 系統(tǒng)設(shè)計目標(biāo)9</p><p>　　4 系統(tǒng)詳細(xì)設(shè)計錯誤!未定義書簽。</p><p>　　4.1 用戶注冊與登錄錯誤!未定義書簽。</

13、p><p>　　4.2 題庫的具體實現(xiàn)11</p><p>　　4.3 后臺程序算法的實現(xiàn)與分析12</p><p>　　4.4 判題的實現(xiàn)錯誤!未定義書簽。</p><p>　　4.5 系統(tǒng)測試21</p><p><b>　　結(jié)束語23</b></p><p&

14、gt;<b>　　致謝24</b></p><p><b>　　參考文獻(xiàn)25</b></p><p><b>　　1 引言</b></p><p><b>　　課題背景、意義</b></p><p>　　隨著信息化進(jìn)程的飛速發(fā)展以及計算機技術(shù)的普及，

15、高等院校開設(shè)了越來越多的計算機課程。和傳統(tǒng)的課程比較，計算機課程具有實踐性很強的特點。學(xué)生要學(xué)好這些課程不但要認(rèn)真學(xué)習(xí)理論知識，還需要大量的實踐訓(xùn)練。例如，C 語言課程的學(xué)習(xí)，就需要編寫大量的程序，才能夠積累足夠的經(jīng)驗，真正掌握程序設(shè)計的方法，編寫出正確、高效的程序。對傳統(tǒng)課程的考核多采用筆試的方式，但是，對于計算機方面的課程，特別是程序設(shè)計語言類課程這是不夠的，因為它并不能促使學(xué)生在平時的學(xué)習(xí)中加強實踐的鍛煉。如何對這些課程進(jìn)行有效的

16、考核，成為一個長期工作在第一線的計算機教育工作者反復(fù)思考和不斷探索的問題[1]。</p><p>　　在目前的教學(xué)方式中，多數(shù)高等院校基本上還是采用基于傳統(tǒng)方式的筆試來考核學(xué)生的計算機課程水平，然后在此基礎(chǔ)上稍作補充。在上機實踐考試中，學(xué)生采用FTP，Email，甚至手寫的方式提交編程作業(yè)，老師需要對他們的作業(yè)進(jìn)行一一批閱，相當(dāng)多的時候，任課教師從學(xué)生處得到的是一些低效的，甚至不能運行通過的源代碼，可是卻要花費不

17、少時間來判斷分析學(xué)生程序到底在什么地方出錯，然后給出相應(yīng)的得分。這需要老師和學(xué)生花費很多的精力，效果也不是很好。學(xué)生更無法得知自己所編寫的程序存在哪方面的問題，因而不能有效及時地進(jìn)行更正[2]。而Online Judge可以自動批閱作業(yè)并給出成績，并且直接統(tǒng)計學(xué)生作業(yè)的提交情況，以及成績的登記。這給老師帶來了很大的方便，同時學(xué)生也可以通過Online Judge直接查詢答題狀況。</p><p>　　采用 Onl

18、ine Judge 后，老師可以通過對參數(shù)進(jìn)行設(shè)置，限制學(xué)生提交的編程作業(yè)的類型、文件大小、運行時間長短和空間大小。學(xué)生在提交編程作業(yè)時能夠很快的得到作業(yè)是否正確的反饋。一方面，Online Judge 可以對作業(yè)進(jìn)行自動編譯，檢查出程序是否存在語法錯誤；另一方面，它還能驗證程序是否能得到正確結(jié)果，以及所花費的代價（時間和空間上的）。根據(jù)后處理的結(jié)果與相應(yīng)的參數(shù)設(shè)置，Online Judge 能自動給出學(xué)生此次編程作業(yè)的成績。這大大地減

19、小了學(xué)生提交錯誤程序的概率，還能給出與程序相應(yīng)的成績。當(dāng)然老師也可以進(jìn)行再次審查，對學(xué)生的作業(yè)提出評語，修改成績等。這種方式完全模擬了使用程序設(shè)計語言解決實際問題的過程，編寫程序、不斷測試修改、根據(jù)結(jié)果反饋修改程序[2]。這樣的考試方式對學(xué)生的學(xué)習(xí)過程具有很好的指導(dǎo)作用。與此同時，還消除了老師在檢查作業(yè)的過程中的主觀因素，增加了學(xué)生之間的公平性。</p><p>　　Online Judge 的實現(xiàn)，能很快地運用

20、到現(xiàn)實的學(xué)習(xí)生活中去，有效的考核學(xué)生的真實水平，促使學(xué)生更好的學(xué)習(xí)計算機知識，強化學(xué)生的實踐能力，給學(xué)生和老師帶來立竿見影的效果；極大地提高了學(xué)生和老師雙方面的效率，減輕了老師在教學(xué)管理上的負(fù)擔(dān)[3]；還使學(xué)生將來能更好地適應(yīng)快速發(fā)展的信息化時代；進(jìn)一步發(fā)揮出計算機網(wǎng)絡(luò)對當(dāng)今教育領(lǐng)域甚至其他行業(yè)的突出貢獻(xiàn)。</p><p>　　1.2 系統(tǒng)開發(fā)語言C++</p><p>　　系統(tǒng)采用的主要

21、開發(fā)技術(shù)是C++。C++這個詞在中國大陸的程序員圈子中通常被讀做“C加加”，而西方的程序員通常讀做“C plus plus”，“CPP”。 它是一種使用非常廣泛的計算機編程語言。C++是一種靜態(tài)數(shù)據(jù)類型檢查的，支持多重編程范式的通用程序設(shè)計語言。它支持過程化程序設(shè)計、數(shù)據(jù)抽象、面向?qū)ο蟪绦蛟O(shè)計、制作圖標(biāo)等等泛型程序設(shè)計等多種程序設(shè)計風(fēng)格。C語言之所以要起名為“C”，是因為它是主要參考那個時候的一門叫B的語言，它的設(shè)計者認(rèn)為C語言是B語言

22、的進(jìn)步，所以就起名為C語言；但是B語言并不是因為之前還有個A語言，而是B語言的作者為了紀(jì)念他的妻子，他的妻子名字的第一個字母是B； 當(dāng)C語言發(fā)展到頂峰的時刻，出現(xiàn)了一個版本叫C with Class，那就是C++最早的版本，在C語言中增加class關(guān)鍵字和類，那個時候有很多版本的C都希望在C語言中增加類的概念；后來C標(biāo)準(zhǔn)委員會決定為這個版本的C起個新的名字，那個時候征集了很多種名字，最后采納了其中一個人的意見，以C語言中的++運算符來體

23、現(xiàn)它是C語言的進(jìn)步，故而叫C++，成立了C++標(biāo)準(zhǔn)委員會。 </p><p>　　美國AT&T貝爾實驗室的本賈尼·斯特勞斯特盧普（Bjarne Stroustrup）博士在20世紀(jì)80年代初期發(fā)明并實現(xiàn)了C++（最初這種語言被稱作“C with Classes”）。一開始C++是作為C語言的增強版出現(xiàn)的，從給C語言增加類開始，不斷的增加新特性。虛函數(shù)（virtual function）、運算符重

24、載（operator overloading）、多重繼承（multiple inheritance）、模板（template）、異常（exception）、RTTI、命名空間（name space）逐漸被加入標(biāo)準(zhǔn)。1998年國際標(biāo)準(zhǔn)組織（ISO）頒布了C++程序設(shè)計語言的國際標(biāo)準(zhǔn)ISO/IEC 1988-1998。C++是具有國際標(biāo)準(zhǔn)的編程語言，通常稱作ANSI/ISO C++。1998年是C++標(biāo)準(zhǔn)委員會成立的第一年，以后每5年視實際

25、需要更新一次標(biāo)準(zhǔn)，下一次標(biāo)準(zhǔn)更新原定是在2009年，目前我們一般稱該標(biāo)準(zhǔn)C++0x，但是由于對于新特性的爭端激烈，除了在Technical Report 1（tr1）中的新增修改被基本確定外，完整的標(biāo)準(zhǔn)還遙遙無期。況且遺憾的是，由于C++語言過</p><p>　　目前最符合和接近C++標(biāo)準(zhǔn)的編譯器有為 GNU GCC 4.6.1 和 Visual Studio 2010 sp1 等。 </p>&

26、lt;p>　　另外，就目前學(xué)習(xí)C++而言，可以認(rèn)為他是一門獨立的語言；他并不依賴C語言，我們可以完全不學(xué)C語言，而直接學(xué)習(xí)C++。根據(jù)《C++編程思想》（Thinking in C++）一書所評述的，C++與C的效率往往相差在正負(fù)5%之間。所以有人認(rèn)為在大多數(shù)場合C++ 完全可以取代C語言(然而我們在單片機等需要謹(jǐn)慎利用空間、直接操作硬件的地方還是要使用C語言)[3]。</p><p>　　C++設(shè)計成靜態(tài)

27、類型、和C同樣高效且可移植的多用途程序設(shè)計語言。 </p><p>　　C++設(shè)計成直接的和廣泛的支援多種程序設(shè)計風(fēng)格（程序化程序設(shè)計、資料抽象化、面向?qū)ο蟪绦蛟O(shè)計、泛型程序設(shè)計）。 </p><p>　　C++設(shè)計成給程序設(shè)計者更多的選擇，即使可能導(dǎo)致程序設(shè)計者選擇錯誤。 </p><p>　　C++設(shè)計成盡可能與C兼容，籍此提供一個從C到C++的平滑過渡。 &l

28、t;/p><p>　　C++避免平臺限定或沒有普遍用途的特性。 </p><p>　　C++不使用會帶來額外開銷的特性。 </p><p>　　C++設(shè)計成無需復(fù)雜的程序設(shè)計環(huán)境。 </p><p><b>　　1.3相關(guān)技術(shù)簡介</b></p><p>　　本系統(tǒng)是基于Visual Web Deve

29、loper和SQL Server開發(fā)環(huán)境下的畢業(yè)設(shè)計過程管理系統(tǒng)，是以Visual Web Developer為前臺開發(fā)工具，以SQL Server 作為后臺數(shù)據(jù)庫開發(fā)的B/S（瀏覽器/服務(wù)器）結(jié)構(gòu)的應(yīng)用系統(tǒng)。</p><p>　　1.3.1 .Net簡介</p><p>　　系統(tǒng)采用的主要開發(fā)技術(shù)是.Net技術(shù)。.Net首先是一個平臺，它定義了一種公用語言子集（Common Langua

30、ge Subset，CLS），這是一種為符合其規(guī)范的語言與類庫之間提供無縫集成的混合語。.Net統(tǒng)一了編程類庫，提供了對下一代網(wǎng)絡(luò)通訊標(biāo)準(zhǔn)，可擴展標(biāo)記語言（Extensible Markup Language，XML）的完全支持，使應(yīng)用程序的開發(fā)變得更容易，更簡單。Microsoft.Net計劃還將實現(xiàn)人機交互方面的革命，微軟將在其軟件中添加手寫和語音識別的功能，讓人們能夠與計算機進(jìn)行更好的交流，并在此基礎(chǔ)上繼續(xù)擴展功能，增加對各種用戶

31、終端的支持能力。最為重要的是.Net將改變因特網(wǎng)的行為方式：軟件將變?yōu)榉?wù)。與Microsoft的其他產(chǎn)品一樣，.Net與Windows平臺緊密集成，并且與其他微軟產(chǎn)品相比它更進(jìn)一步：由于其運行庫已經(jīng)與操作系統(tǒng)融合在了一起，從廣義上把它稱為一個運行庫也不為過。</p><p>　　.Net框架是.Net平臺的基礎(chǔ)架構(gòu)。其強大功能來自于公共語言運行時（Common Language Runtime，CLR）環(huán)境和類

32、庫。CLR和類庫緊密結(jié)合在一起，提供了不同系統(tǒng)之間交叉與綜合的解決方案和服務(wù)。.Net框架創(chuàng)造了一個完全可操控的、安全的和特性豐富的應(yīng)用執(zhí)行環(huán)境。這不但使得應(yīng)用程序的開發(fā)與發(fā)布更加簡單，并且成就了眾多種類語言間的無縫集成。</p><p>　　.Net的核心組件包括：</p><p>　　● 一組用于創(chuàng)建互聯(lián)網(wǎng)操作系統(tǒng)的構(gòu)件塊，其中包括Passport.Net（用于用戶認(rèn)證）以及用于文件存

33、儲的服務(wù)、用戶首選項管理、日歷管理以及眾多的其他任務(wù)。</p><p>　　● 構(gòu)建和管理新一代服務(wù)的基本結(jié)構(gòu)和工具，包括Visual Studio.Net、.Net企業(yè)服務(wù)器、.Net Framework和Windows.Net。</p><p>　　● 能夠啟用新型智能互聯(lián)網(wǎng)設(shè)備的.Net設(shè)備軟件。</p><p>　　● .Net用戶體驗。</p>

34、<p><b>　　.Net結(jié)構(gòu)包括：</b></p><p>　　● 虛擬對象系統(tǒng)（Visual Object System ,VOS）類型系統(tǒng)</p><p><b>　　● 元數(shù)據(jù)</b></p><p>　　● 公用語言規(guī)范（Common Language Specification，CLS）<

35、/p><p>　　● 虛擬執(zhí)行系統(tǒng)（Visual Execution System,VES）</p><p>　　簡而言之，.Net是一種面向網(wǎng)絡(luò)、支持各種用戶終端的開發(fā)平臺環(huán)境。微軟的宏偉目標(biāo)是讓.Net徹底改變軟件的開發(fā)方式、發(fā)行方式、使用方式等等，并且不止是針對微軟一家，而是面向所有開發(fā)商與運營商。.Net的核心內(nèi)容之一就是搭建第三代因特網(wǎng)平臺，這個網(wǎng)絡(luò)平臺將解決網(wǎng)站之間的協(xié)同合作問題，

36、從而最大限度地獲取信息。在.Net平臺上，不同網(wǎng)站之間通過相關(guān)的協(xié)定聯(lián)系在一起，網(wǎng)站之間形成自動交流，協(xié)同工作，提供最全面的服務(wù)。</p><p>　　1.3.2 Visual Studio簡介</p><p>　　Visual Studio 2008 Express Editions包括Visual Web Developer 2008 Express Edition、Visual B

37、asic 2008 Express Edition、Visual C# 2008 Express Edition、Visual C++ 2008 Express Edition和Visual J# 2005 Express Edition。Visual Web Developer是一種簡便的、易學(xué)易用的開發(fā)工具，重點專注于使用ASP.NET 3.5進(jìn)行網(wǎng)絡(luò)開發(fā)，構(gòu)建動態(tài)網(wǎng)絡(luò)應(yīng)用。通過具有易用的拖拽界面的可視化設(shè)計器、功能強大的代碼編輯器

38、、嵌入式數(shù)據(jù)控制和到SQL Server的集成入口、以及對Visual Basic, C#和J#等多種語言的支持，創(chuàng)建并管理網(wǎng)絡(luò)應(yīng)用。</p><p>　　Visual Web Developer內(nèi)置完備的開發(fā)套件，可以快速進(jìn)行Web應(yīng)用開發(fā)。通過所見即所得的拖拽界面就可以創(chuàng)建出美觀、易用的網(wǎng)站。內(nèi)置60余種控件、上百段代碼片斷，可以幅度降低創(chuàng)建互動式Web應(yīng)用的時間。支持頁面模板，從而統(tǒng)一地管理網(wǎng)頁的排版與布局

39、。通過IntelliSense，可以更快的訪問資源庫和方法。并可以通過Common Tasks和Smart Tags調(diào)用最常用的Web開發(fā)功能。</p><p>　　此外，Visual Web Developer 2008 Express 提供使用ASP.NET 3.5開始構(gòu)建網(wǎng)絡(luò)應(yīng)用的所有材料。它包括：</p><p>　　通過易用的拖拽界面使創(chuàng)建網(wǎng)絡(luò)應(yīng)用更加容易的Visual Desi

40、gner。</p><p>　　功能豐富的強大的代碼編輯器，例如Intellisense，它可以使編寫代碼和HTML變得更加迅速。</p><p>　　使用嵌入式數(shù)據(jù)控制和到Microsoft SQL Server 2005 Express的集成入口，快速創(chuàng)建數(shù)據(jù)驅(qū)動的網(wǎng)絡(luò)應(yīng)用。</p><p>　　支持多種語言：Visual Basic, C#和J#。</p

41、><p>　　使用嵌入式的全功能的初學(xué)者套件來起步，如Personal Web Starter Kit。</p><p>　　1.3.3 SQL server簡介</p><p>　　Microsoft SQL Server 2005 Express Edition(SQL Server Express)是基于Microsoft SQL Server 2005的數(shù)據(jù)庫

42、平臺。它也可用于替換Microsoft Desktop Engine(MSDE)。與Microsoft Visual Studio 2005集成之后的SQL Server Express使得能夠輕松開發(fā)數(shù)據(jù)驅(qū)動的應(yīng)用程序，這些應(yīng)用程序功能豐富、提供了增強的存儲安全性并可快速進(jìn)行部署。</p><p>　　Microsoft具有高級服務(wù)的SQL Server 2005 Express Edition(SQL Ser

43、ver Express) 是SQL Server Express的一個版本，包括新的圖形管理工具、報告功能和基于文本的高級搜索功能。這兩個SQL Server Express版本可以根據(jù)協(xié)議重新進(jìn)行分發(fā)。其中每個版本都可以充當(dāng)客戶端數(shù)據(jù)庫和基本服務(wù)器數(shù)據(jù)庫。</p><p>　　SQL Server 2005 Express Edition是適用于負(fù)載較小的網(wǎng)站的一種輕型數(shù)據(jù)庫服務(wù)器。它作為可選組件提供，可以在V

44、isual Web Developer安裝過程中進(jìn)行安裝。與Microsoft Access相似，可以使用SQL Server 2005特定的強大功能，將數(shù)據(jù)庫作為獨立的文件進(jìn)行創(chuàng)建和部署。這為構(gòu)建網(wǎng)站提供了不可估量的數(shù)據(jù)庫功能和管理功能。</p><p>　　2 研究的基本內(nèi)容及解決的問題</p><p>　　2.1 課題的基本內(nèi)容</p><p><b

45、>　　用戶注冊的實現(xiàn)。</b></p><p><b>　　用戶信息的管理。</b></p><p>　　題目的設(shè)計與算法實現(xiàn)。</p><p>　　建立數(shù)據(jù)庫保存信息。</p><p>　　編譯器的調(diào)用于實現(xiàn)。</p><p><b>　　調(diào)用后臺源程序。</b

46、></p><p>　　判斷輸入程序的真確性。</p><p>　　2.2 解決的問題</p><p>　　2.2.1 登錄信息管理</p><p><b>　　表1 權(quán)限信息表</b></p><p>　　表 2用戶角色信息表</p><p>　　2.2.2 題庫

47、的設(shè)計實現(xiàn)</p><p>　　程序設(shè)計在線判題系統(tǒng)的題庫由各類基本程序設(shè)計題組成，程序設(shè)計題目是進(jìn)行判題和評分的單元，是測試驅(qū)動源文件。在本系統(tǒng)中，并不是所有的題目都能夠進(jìn)行在線編譯判題，所以設(shè)計時必須針對程序設(shè)計題程序設(shè)計在線判題系統(tǒng)設(shè)計一個特定的題目結(jié)構(gòu)，這種題目結(jié)構(gòu)的目的在于考核學(xué)生對于一定的知識點的掌握并且能夠被正確評估，一個切實可行的方案是限定程序題目的輸入和輸出。在程序中適當(dāng)?shù)牧艨?，在這種條件下系統(tǒng)

48、就能夠有效實現(xiàn)程序正確性的判定。每一道題目由以下五部分組成：Input(標(biāo)準(zhǔn)輸入)，Output(標(biāo)準(zhǔn)輸出)，RII．c(程序填空)。Text(題目的正文)，Title(題目標(biāo))。為此引用MYSQL建立后臺使用C和C++編寫，并使用了多種編譯器進(jìn)行測試，保證源代碼的可移植性。 支持AIX、FreeBSD、HP-UX、Linux、Mac OS、Novell Netware、OpenBSD、OS/2 Wrap、Solaris、Windows

49、等多種操作系統(tǒng)。為多種編程語言提供了API。支持多線程，充分利用CPU資源 。優(yōu)化的SQL查詢算法，有效地提高查詢速度 。既能夠作為一個單獨的應(yīng)用程序應(yīng)用在客戶端服務(wù)器網(wǎng)絡(luò)環(huán)境</p><p>　　2.2.3 編譯的實現(xiàn)</p><p>　　用戶提交(submit)代碼之后，OJ調(diào)用相應(yīng)的編譯器(compiler)編譯這段代碼，如果出現(xiàn)編譯錯誤(CE)，立即將編譯器給出的CE消息返回給用戶

50、。.如果編譯階段通過后，將代碼轉(zhuǎn)換為可執(zhí)行文件.exe(C/C++)或類文件.class(Java)。然后需要調(diào)入事先準(zhǔn)備好的各類測試數(shù)據(jù)考驗用戶程序。.這時候OJ需要執(zhí)行用戶程序，但用戶程序是讀入和寫出標(biāo)準(zhǔn)I/O流，與你準(zhǔn)備好的輸入/輸出測試數(shù)據(jù)需要一個連接器(connector)。這里我準(zhǔn)備使用類似管道的技術(shù)。.在windows上可以書寫批處理.bat文件，將輸入數(shù)據(jù)1000.in文件重定向到1000.exe，然后將1000.exe

51、執(zhí)行后存入標(biāo)準(zhǔn)輸出流的數(shù)據(jù)重定向到輸出數(shù)據(jù)1000.out文件中。這時候如果有運行時錯誤RE則和處理CE過程類似。如果有運行結(jié)果，則將這一結(jié)果和標(biāo)準(zhǔn)結(jié)果做對比。</p><p>　　3 系統(tǒng)總體設(shè)計與目標(biāo)</p><p>　　3.1 系統(tǒng)設(shè)計的原則</p><p>　　實用性：系統(tǒng)的設(shè)計從用戶的需求出發(fā)，滿足了判題活動的一系列要求，而且力求用戶操作方便、簡單易懂、

52、界面友好。</p><p>　　安全性：系統(tǒng)采用了輸入“用戶名”和“密碼”來識別用戶的登錄界面，從而防止了非法用戶的入侵；通過對用戶權(quán)限的設(shè)置實現(xiàn)了管理員與用戶相分離，充分保證了系統(tǒng)的安全性。</p><p>　　可維護(hù)性和可擴展性：系統(tǒng)具有良好的可擴展性和可維護(hù)性。系統(tǒng)中各個模塊的獨立性可以完全保證各個模塊的適當(dāng)擴展和修改不會影響到其他模塊的運行。</p><p>

53、;　　標(biāo)準(zhǔn)性：軟件設(shè)計嚴(yán)格執(zhí)行國家有關(guān)軟件工程的標(biāo)準(zhǔn)，保證系統(tǒng)質(zhì)量，提供完整、準(zhǔn)確、詳細(xì)的開發(fā)文檔。</p><p>　　簡單化：界面盡量簡單化，做到實用、方便，盡量滿足不同角色用戶的需要。</p><p>　　3.2 系統(tǒng)設(shè)計方法</p><p>　　結(jié)構(gòu)化方法是系統(tǒng)在設(shè)計時采用的主要方法。結(jié)構(gòu)化方法的基本思路就是把整個系統(tǒng)開發(fā)過程分為若干階段，每個階段進(jìn)行若干

54、活動，每項活動應(yīng)用一系列標(biāo)準(zhǔn)、規(guī)范、方法和技術(shù)，完成一個或多個任務(wù)，形成符合給定規(guī)范的產(chǎn)品。</p><p>　　結(jié)構(gòu)化系統(tǒng)開發(fā)方法的特點是：</p><p>　　用“自上而下”的開發(fā)策略，進(jìn)行系統(tǒng)分析和系統(tǒng)設(shè)計，然后“自下而上”地開發(fā)和調(diào)試各個模塊，最后實現(xiàn)模塊聯(lián)調(diào)和整個系統(tǒng)的聯(lián)調(diào)。</p><p>　　工作文件的標(biāo)準(zhǔn)化與文檔化。即每一階段、每一步驟都有詳細(xì)的文檔

55、記錄，并有完整的管理制度。</p><p>　　強調(diào)面向用戶的特點。即將用戶的參與程度和滿意與否作為系統(tǒng)開發(fā)能否成功的關(guān)鍵。</p><p>　　結(jié)構(gòu)化開發(fā)方法在大多數(shù)情況下是信息系統(tǒng)工程開發(fā)的有效方法。它首先用結(jié)構(gòu)化分析(SA)對軟件進(jìn)行需求分析，然后用結(jié)構(gòu)化設(shè)計(SD)方法進(jìn)行總體設(shè)計，最后是結(jié)構(gòu)化編程(SP)。</p><p>　　結(jié)構(gòu)化方法又可以分為自頂向下

56、和自底向上開發(fā)方法。兩者結(jié)合是實際開發(fā)過程中常用的方法。</p><p>　　結(jié)構(gòu)化方法的主要原則是：</p><p><b>　　用戶參與的原則；</b></p><p>　　“先邏輯，后物理”的原則；</p><p>　　“自頂向下”的原則；</p><p>　　工作成果描述標(biāo)準(zhǔn)化的原則。&l

57、t;/p><p><b>　　3.3 系統(tǒng)結(jié)構(gòu)</b></p><p>　　判題模塊中在線編譯器和在線判題器的設(shè)計和實現(xiàn)。調(diào)用編譯配置腳本，傳入?yún)?shù)題目號、使用語言，使用語言決定調(diào)用GCC、G++或其他編譯器。然后編譯腳本對程序進(jìn)行編譯并執(zhí)行，輸出提交程序的結(jié)果文件。在線判題器使用Bash Shell腳本語言實現(xiàn)。首先檢查由編譯腳本輸出的結(jié)果文件，如果編譯出錯則判定Co

58、mpile Error(編譯錯誤)并返回。如果程序編譯通過，判題腳本fo水出子進(jìn)程，根據(jù)題目的相應(yīng)限制設(shè)置進(jìn)程運行的時間、空間限制。同時判題腳本判斷子進(jìn)程運行及返回狀態(tài)，分別判定Runtime Error(運行時錯誤)，Time limit exceeded(程序運行超時)，Memory limit exceeded(內(nèi)存使用超限)，并且返回。</p><p>　　3.4 系統(tǒng)結(jié)構(gòu)圖</p>&l

59、t;p>　　圖1 系統(tǒng)總體結(jié)構(gòu)圖</p><p>　　3.5 系統(tǒng)設(shè)計目標(biāo)</p><p>　　預(yù)期系統(tǒng)應(yīng)達(dá)到的實施效果：</p><p>　　程序設(shè)計語言熟練程度和程序設(shè)計能力是計算機相關(guān)專業(yè)學(xué)生的最基本的技能。傳統(tǒng)的上機練習(xí)往往依賴于教師的指導(dǎo)，在教師資源有限的情況下，上機指導(dǎo)教師的工作量普遍較大。設(shè)計一個能對程序設(shè)計題進(jìn)行在線編譯判題不需任何人工輔助的

60、系統(tǒng)，不僅可以給學(xué)生提供一個訓(xùn)練程序設(shè)計能力的互動平臺[13]。也使教師能夠通過系統(tǒng)更能把握學(xué)生對教學(xué)內(nèi)容掌握程度并可作為監(jiān)督學(xué)生學(xué)習(xí)的重要工具，還可以在一定程度上強化實踐、激發(fā)自主性；其次，作為一個網(wǎng)絡(luò)教學(xué)練習(xí)和考試系統(tǒng)，提供了在線判題功能，可以有效降低教師的閱卷工作量。</p><p><b>　　4 系統(tǒng)詳細(xì)設(shè)計</b></p><p><b>　　4

61、.1 用戶登錄</b></p><p>　　系統(tǒng)登錄界面部分，前臺視覺設(shè)計如下圖所示：</p><p><b>　　圖2登錄界面設(shè)計</b></p><p>　　4.2 題庫的具體實現(xiàn)</p><p>　　程序設(shè)計在線判題系統(tǒng)的題庫由各類基本程序設(shè)計題組成，程序設(shè)計題目是進(jìn)行判題和評分的單元，是測試驅(qū)動源

62、文件。在本系統(tǒng)中，并不是所有的題目都能夠進(jìn)行在線編譯判題，所以設(shè)計時必須針對程序設(shè)計題程序設(shè)計在線判題系統(tǒng)設(shè)計一個特定的題目結(jié)構(gòu)，這種題目結(jié)構(gòu)的目的在于考核學(xué)生對于一定的知識點的掌握并且能夠被正確評估，一個切實可行的方案是限定程序題目的輸入和輸出。在程序中適當(dāng)?shù)牧艨?，在這種條件下系統(tǒng)就能夠有效實現(xiàn)程序正確性的判定。每一道題目由以下五部分組成：Input(標(biāo)準(zhǔn)輸入)，Output(標(biāo)準(zhǔn)輸出)，F(xiàn)II．c(程序填空),Text(題目的正文)

63、，Title(題目標(biāo))。對于一個考核學(xué)生是否掌握求兩個數(shù)和與差的題目示例如下：</p><p>　　(a)Text：題目的內(nèi)容，是對題目的說明。如題：“程序填空，不要改變與輸入輸出有關(guān)的語句。輸入整數(shù)a和b，計算并輸出a、b的和與差。例：輸入2—8；輸出The sum is一6；The difference is 10” 。</p><p>　　(b)Title：題目標(biāo)題，如上述的題目標(biāo)題

64、就是“求兩個數(shù)的和與差”。</p><p>　　(c)Input：程序的標(biāo)準(zhǔn)輸入。如上述的題目輸入就是“2—8”。</p><p>　　(d)Output：程序的標(biāo)準(zhǔn)輸出，作為提交程序輸出的語義匹配的模板。如上述的題目輸出就是“The sum is一6：The difference is 10”。</p><p>　　(c)Fill．c：程序主體，空缺部分需要學(xué)生填

65、寫完整(以C語言為例)，空缺部分可以是所要考核的知識點的關(guān)鍵部分。比如：</p><p>　　#iclude<sldio．h></p><p>　　int main(){</p><p>　　int a，b，sum，diff；</p><p>　　scanf(“％d％d”，&a，&b)；</p>&l

66、t;p><b>　　sum=a+b；</b></p><p>　　diff=a—b：／*fill_n*／</p><p>　　printf(“The sum is％d＼n”，sum)；</p><p>　　printf(“The difference ls％d＼n”，diff)；</p><p><b>

67、　　}</b></p><p>　　程序題目作為記錄存入數(shù)據(jù)庫中，其中還包括其他的屬性，例如題目類型，知識點，難度，程序進(jìn)程運行的時間、空間限制。題目類型、知識點、難度用于出卷；程序進(jìn)程運行的時間、空間限制用于控制判題時服務(wù)器資源。</p><p>　　4.3后臺源程序算法的實現(xiàn)與分析</p><p>　　算法設(shè)計與分析的基本方法[8]： </p&

68、gt;<p><b>　　1).遞推法</b></p><p>　　遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關(guān)系，從而達(dá)到目的，此方法稱為遞推法。 </p><p><b>　　2).遞歸</b></p><p>　　遞歸指的是一個過程：函數(shù)不斷引用自身，

69、直到引用的對象已知。 </p><p><b>　　3).窮舉搜索法</b></p><p>　　窮舉搜索法是對可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗，并從眾找出那些符合要求的候選解作為問題的解。 </p><p><b>　　4).貪婪法</b></p><p>　　貪婪法是一種不追求

70、最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。 </p><p><b>　　5).分治法</b></p><p>　　分治法是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題

71、……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 </p><p><b>　　6).動態(tài)規(guī)劃法</b></p><p>　　動態(tài)規(guī)劃是一種在數(shù)學(xué)和計算機科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計算機科學(xué)

72、和工程領(lǐng)域。 </p><p><b>　　7).迭代法</b></p><p>　　迭代法是數(shù)值分析中通過從一個初始估計出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。</p><p><b>　　4.4 判題的實現(xiàn)</b></p><p>

73、　　下圖是程序設(shè)計在線判題系統(tǒng)的實現(xiàn)原理。</p><p><b>　　圖 3 判題原理</b></p><p>　　程序設(shè)計在線判題系統(tǒng)的測試用例運行控制是整個系統(tǒng)運行控制中心，包含調(diào)度編譯和判題兩個功能。這部分的實現(xiàn)需要涉及操作系統(tǒng)的部分底層操作，如信號操作、進(jìn)程間通信和控制等，所以系統(tǒng)測試用例運行控制主程序選擇C++實現(xiàn)。用戶交互由PHP程序?qū)崿F(xiàn)，后臺數(shù)據(jù)庫系

74、統(tǒng)采用MySQL。PHP程序負(fù)責(zé)與用戶交互，處理用戶登錄、查看題目、提交答案、比對輸出和顯示結(jié)果等請求。系統(tǒng)測試用例運行控制具體設(shè)計流程如下：考生首先在PHP頁面下載程序題目，完成程序填空部分或者整個程序，然后提交題目到判題服務(wù)，并在數(shù)據(jù)庫中插入相應(yīng)的記錄，提交要求判題信號，然后主程序收到信號后讀取數(shù)據(jù)庫記錄，并且調(diào)用判題主程序。判題主程序是判題系統(tǒng)的核心子系統(tǒng)，它主要功能是負(fù)責(zé)接收和分派判題請求，并且調(diào)用判題模塊實現(xiàn)判題評分。判題主程

75、序首先主要負(fù)責(zé)從數(shù)據(jù)庫中讀取所需要的題庫信息(Input、Output和Fill．c)，為每一題目建立臨時工作目錄，并把這些信息保存到臨時工作目錄。一旦考生通過WEB頁面提交要求被評估源代碼，判題主程序接收到提交請求并且自動查詢數(shù)據(jù)庫，檢查題庫表中是否有對應(yīng)題目存在，并同時查詢題目狀態(tài)是否為可提交到數(shù)據(jù)庫判題</p><p>　　圖 4 在線編譯判題流程</p><p>　　判題模塊負(fù)責(zé)

76、處理判題的具體實現(xiàn)，包含在線編譯器和在線判題器兩個重要部件，是一個處理用戶、操作系統(tǒng)、數(shù)據(jù)庫、判題系統(tǒng)多方面交互的過程：判題模塊首先查詢數(shù)據(jù)庫判題運行表(小ns表)獲得提交詳細(xì)信息，同時查詢當(dāng)場考試信息表獲得當(dāng)前考試時間，比較提交時間是否在考試時間內(nèi)，如果不在考試時間內(nèi)則判定超時并返回。如果在考試時間內(nèi)，調(diào)用編譯配置腳本，傳入?yún)?shù)題目號、使用語言，使用語言決定調(diào)用GCC、G++或其他編譯器。然后編譯腳本對程序進(jìn)行編譯并執(zhí)行，輸出提交程序

77、的結(jié)果文件。</p><p>　　在線判題器使用Bash Shell腳本語言實現(xiàn)。首先檢查由編譯腳本輸出的結(jié)果文件，如果編譯出錯則判定Compile Error(編譯錯誤)并返回。如果程序編譯通過，判題腳本fo水出子進(jìn)程，根據(jù)題目的相應(yīng)限制設(shè)置進(jìn)程運行的時間、空間限制。同時判題腳本判斷子進(jìn)程運行及返回狀態(tài)，分別判定Runtime Error(運行時錯誤)，Time Iim計exceeded(程序運行超時)，Mem

78、oryljm計exceeded(內(nèi)存使用超限)，并且返回。最后更新數(shù)據(jù)庫判題運行表(t_runs)寫入判題結(jié)果和輸出，刪除工作臨時文件，進(jìn)行語義匹配，給出分?jǐn)?shù)。</p><p>　　系統(tǒng)實現(xiàn)調(diào)用g++編譯器判斷用戶程序的對錯。</p><p>　　#include <QtCore></p><p>　　#include <QtSql><

79、/p><p>　　#include "daemon.h"</p><p>　　#include "executer.h"</p><p>　　#include "compiler.h"</p><p>　　const int BufferSize = 50;</p><

80、;p>　　int buffer[BufferSize]; </p><p>　　bool isJudgeActivated = false;</p><p>　　QSemaphore freeBuffer(BufferSize); </p><p>　　QSemaphore usedBuffer;</p><p>　　void jud

81、ge(int id)</p><p><b>　　{</b></p><p>　　QSqlQuery query;</p><p>　　QString tempString;</p><p>　　query.prepare("select compiler from status where runID =

82、:id");</p><p>　　query.bindValue(":id", id);</p><p>　　query.exec();</p><p>　　query.first();</p><p>　　QString languageName = query.value(0).toString();<

83、/p><p>　　QString compilerName;</p><p>　　QStringList opt;</p><p>　　if(languageName == "C++")</p><p><b>　　{</b></p><p>　　compilerName = &q

84、uot;g++";</p><p>　　opt << "-w" << "-o" << "../judge/oexe/temp.exe";</p><p>　　tempString = "../judge/src/";</p><p>　　te

85、mpString.append(QString::number(id));</p><p>　　tempString.append(".cpp");</p><p>　　opt << tempString;</p><p><b>　　}</b></p><p>　　else if(lan

86、guageName == "C")</p><p><b>　　{</b></p><p>　　compilerName = "gcc";</p><p>　　opt << "-w" << "-o" << "../jud

87、ge/oexe/temp.exe";</p><p>　　tempString = "../judge/src/";</p><p>　　tempString.append(QString::number(id));</p><p>　　tempString.append(".c");</p><

88、p>　　opt << tempString;</p><p><b>　　}</b></p><p>　　else if(languageName == "Java")</p><p><b>　　{</b></p><p><b>　　}</

89、b></p><p>　　else// Pascal</p><p><b>　　{</b></p><p><b>　　}</b></p><p>　　Compiler compiler(compilerName);</p><p>　　// set compile

90、r environment & options</p><p>　　compiler.setCompilerOption(opt);</p><p>　　compiler.execute();</p><p>　　tempString = compiler.getStatus();</p><p>　　if( tempString =

91、= "Compile Error" )</p><p><b>　　{</b></p><p>　　query.prepare("update status set judgeStatus = 'Compile Error', "</p><p>　　"remarks = :re

92、m where runID = :rid");</p><p>　　query.bindValue(":rem", compiler.getErrorInfo());</p><p>　　query.bindValue(":rid", id);</p><p>　　query.exec();</p>&

93、lt;p>　　// return this function earlier</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　// compile OK, continue</p><p>　　// first, select t

94、he problem ID.</p><p>　　Executer executer;</p><p>　　query.prepare("select problemID from status where runID = :rid");</p><p>　　query.bindValue(":rid", id);</p

95、><p>　　query.exec();</p><p>　　query.first();</p><p>　　QString pidString = query.value(0).toString();</p><p>　　tempString = "../judge/cases/in/";</p><

96、p>　　tempString.append(pidString);</p><p>　　executer.setInputFile(tempString);</p><p>　　tempString = "../judge/cases/output/";</p><p>　　tempString.append(QString::number

97、(id));</p><p>　　executer.setOutputFile(tempString);</p><p>　　tempString = "../judge/oexe/";</p><p>　　tempString.append("temp.exe");</p><p>　　execute

98、r.setExePath(tempString);</p><p>　　executer.setTimeLimit();</p><p>　　executer.setMemoryLimit();</p><p>　　tempString = "../judge/cases/out/";</p><p>　　tempStri

99、ng.append(pidString);</p><p>　　executer.setTestCasePath(tempString);</p><p>　　executer.execute();</p><p>　　qDebug() << executer.getStatus();</p><p>　　const QTime

100、startTime(11, 30, 0); </p><p>　　query.prepare("update status set judgeStatus = :js where runID = :rid");</p><p>　　query.bindValue(":js", executer.getStatus());</p>&

101、lt;p>　　query.bindValue(":rid", id);</p><p>　　query.exec();</p><p>　　if( executer.getStatus() == "Accepted" )</p><p><b>　　{</b></p><p>

102、;　　qDebug() << "Accepted, updating the database.\n";</p><p>　　query.prepare("update problemLib set accepted = accepted + 1, ratio = accepted / submited "</p><p>　　"

103、;where pid = :pid");</p><p>　　query.bindValue(":pid", pidString.toInt());</p><p>　　query.exec();</p><p>　　QString team;</p><p>　　QTime submitTime;</p&

104、gt;<p>　　query.prepare("select author,submitTime from status where runID = :rid");</p><p>　　query.bindValue(":rid", id);</p><p>　　query.exec();</p><p>　　w

105、hile(query.next())</p><p><b>　　{</b></p><p>　　team = query.value(0).toString();</p><p>　　submitTime = query.value(1).toTime();</p><p><b>　　}</b>

106、</p><p>　　QString passTime, submitTimes;</p><p>　　passTime = "passTime_" + pidString;</p><p>　　submitTimes = "submitTimes_" + pidString;</p><p>　　QS

107、tring queryString;</p><p>　　queryString.append("select solvedNumber, contestTime, ");</p><p>　　queryString.append(passTime);</p><p>　　queryString.append(", ");&l

108、t;/p><p>　　queryString.append(submitTimes);</p><p>　　queryString.append(" from rankList where team = '");</p><p>　　queryString.append(team);</p><p>　　querySt

109、ring.append("'");</p><p>　　qDebug() << queryString;</p><p>　　query.exec(queryString);</p><p>　　QTime pTime, cTime; //pass time, contest time</p><p>

110、　　int sNum(0); //submit times</p><p>　　int solved(0); //solved number</p><p><b>　　int temp;</b></p><p>　　while(query.next())</p><p><b>　　{</b>&

111、lt;/p><p>　　solved = query.value(0).toInt();</p><p>　　cTime = query.value(1).toTime();</p><p>　　pTime = query.value(2).toTime();</p><p>　　sNum = query.value(3).toInt();<

112、;/p><p><b>　　}</b></p><p>　　solved += 1;</p><p>　　sNum = 1 + sNum;</p><p>　　temp = startTime.secsTo(QTime(0, 0, 0));</p><p>　　submitTime = submitT

113、ime.addSecs(temp);</p><p>　　temp = (-sNum) * 1200;</p><p>　　pTime = submitTime.addSecs(temp);</p><p>　　temp = pTime.secsTo(QTime(0, 0, 0));</p><p>　　cTime = cTime.addS

114、ecs(-temp);</p><p>　　qDebug() << "cTime: " << cTime;</p><p>　　qDebug() << "solved: " << solved;</p><p>　　qDebug() << "sNum: &q

115、uot; << sNum;</p><p>　　QString updateString;</p><p>　　updateString = QString("update rankList set solvedNumber = %1, contestTime = \'").arg(solved);</p><p>　　upd

116、ateString.append(cTime.toString("HH:mm:ss"));</p><p>　　updateString.append("\', ");</p><p>　　updateString.append(passTime);</p><p>　　updateString.append(&quo

117、t; = \'");</p><p>　　updateString.append(pTime.toString("HH:mm:ss"));</p><p>　　updateString.append("\', ");</p><p>　　updateString.append(submitTimes)