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

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

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

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

4、括前臺管理模塊和后臺判定模塊。本系統(tǒng)很好的為用戶提供了一個學習編程、掌握編程與編程交互的平臺。</p><p>　　關鍵詞：程序設計;在線判題;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 相關技術簡介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 要解決的技術難點及解決方法錯誤!未定義書簽。</p>&l

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

12、t;p>　　3.2 系統(tǒng)設計方法12</p><p>　　3.3 系統(tǒng)結構8</p><p>　　3.4 系統(tǒng)結構圖8</p><p>　　3.1 系統(tǒng)設計目標9</p><p>　　4 系統(tǒng)詳細設計錯誤!未定義書簽。</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>　　結束語23</b></p><p&

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

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

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

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

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

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

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

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

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

23、現(xiàn)它是C語言的進步，故而叫C++，成立了C++標準委員會。 </p><p>　　美國AT&T貝爾實驗室的本賈尼·斯特勞斯特盧普（Bjarne Stroustrup）博士在20世紀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）逐漸被加入標準。1998年國際標準組織（ISO）頒布了C++程序設計語言的國際標準ISO/IEC 1988-1998。C++是具有國際標準的編程語言，通常稱作ANSI/ISO C++。1998年是C++標準委員會成立的第一年，以后每5年視實際

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

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

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

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

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

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

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

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

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

34、<p><b>　　.Net結構包括：</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)絡、支持各種用戶終端的開發(fā)平臺環(huán)境。微軟的宏偉目標是讓.Net徹底改變軟件的開發(fā)方式、發(fā)行方式、使用方式等等，并且不止是針對微軟一家，而是面向所有開發(fā)商與運營商。.Net的核心內(nèi)容之一就是搭建第三代因特網(wǎng)平臺，這個網(wǎng)絡平臺將解決網(wǎng)站之間的協(xié)同合作問題，

36、從而最大限度地獲取信息。在.Net平臺上，不同網(wǎng)站之間通過相關的協(xié)定聯(lián)系在一起，網(wǎng)站之間形成自動交流，協(xié)同工作，提供最全面的服務。</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是一種簡便的、易學易用的開發(fā)工具，重點專注于使用ASP.NET 3.5進行網(wǎng)絡開發(fā)，構建動態(tài)網(wǎng)絡應用。通過具有易用的拖拽界面的可視化設計器、功能強大的代碼編輯器

38、、嵌入式數(shù)據(jù)控制和到SQL Server的集成入口、以及對Visual Basic, C#和J#等多種語言的支持，創(chuàng)建并管理網(wǎng)絡應用。</p><p>　　Visual Web Developer內(nèi)置完備的開發(fā)套件，可以快速進行Web應用開發(fā)。通過所見即所得的拖拽界面就可以創(chuàng)建出美觀、易用的網(wǎng)站。內(nèi)置60余種控件、上百段代碼片斷，可以幅度降低創(chuàng)建互動式Web應用的時間。支持頁面模板，從而統(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開始構建網(wǎng)絡應用的所有材料。它包括：</p><p>　　通過易用的拖拽界面使創(chuàng)建網(wǎ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)絡應用。</p><p>　　支持多種語言：Visual Basic, C#和J#。</p

41、><p>　　使用嵌入式的全功能的初學者套件來起步，如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ū)動的應用程序，這些應用程序功能豐富、提供了增強的存儲安全性并可快速進行部署。</p><p>　　Microsoft具有高級服務的SQL Server 2005 Express Edition(SQL Ser

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

44、isual Web Developer安裝過程中進行安裝。與Microsoft Access相似，可以使用SQL Server 2005特定的強大功能，將數(shù)據(jù)庫作為獨立的文件進行創(chuàng)建和部署。這為構建網(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>　　題目的設計與算法實現(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 權限信息表</b></p><p>　　表 2用戶角色信息表</p><p>　　2.2.2 題庫

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

65、寫完整(以C語言為例)，空缺部分可以是所要考核的知識點的關鍵部分。比如：</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ù)庫中，其中還包括其他的屬性，例如題目類型，知識點，難度，程序進程運行的時間、空間限制。題目類型、知識點、難度用于出卷；程序進程運行的時間、空間限制用于控制判題時服務器資源。</p><p>　　4.3后臺源程序算法的實現(xiàn)與分析</p><p>　　算法設計與分析的基本方法[8]： </p&

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

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

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

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

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

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

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

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

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

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

78、oryljm計exceeded(內(nèi)存使用超限)，并且返回。最后更新數(shù)據(jù)庫判題運行表(t_runs)寫入判題結果和輸出，刪除工作臨時文件，進行語義匹配，給出分數(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)