天天看點

online judge(ACM) 簡易核心設計與分析

      online judge(以下簡稱OJ)是用于acm的線上評判系統,有名的OJ包括有

  puk:http://poj.org/

  zju:http://acm.zju.edu.cn

  等等,還有許多我就不一一列舉了....

  先來說說OJ的用途,通常,在ACM的比賽中,參賽選手需要根據比賽的題目,送出該題目的程式設計代碼,然後評判端對送出的代碼進行評判并給出結論(這個結論可能包括正确,答案錯誤,逾時,編譯錯誤,記憶體超出等等)。

這裡有個需要說明下,在acm的比賽中,資料的輸出輸入平台是控制台(指令行).....

 例如一道最簡單經典例子:

 題目:     A+B Problem

          描述

                    計算 a+b

          輸入

                    兩個整數 a,b (0<=a,b<=10)

          輸出

                    輸出a+b的和

          輸入樣例

                    1 2      

          輸出樣例

                    3      

然後選手需要給出實作a+b功能的代碼,并正确的輸出到控制台。

如:

#include<stdio.h>

int main()

{

int a,b;

while(scanf("%d%d",&a,&b)!=EOF)

{

printf("%d/n",a+b);

}

return 0;

然後,我們可以手工對其正确性進行驗證,先編譯這段代碼,然後運作,在螢幕上輸入5 6,然後螢幕顯示11(這時可以再輸入多組資料進行驗證)

  而對于自動化的評判程式來說,顯然,OJ的核心就是評判端的設計。 接下來讓我們分析下一個簡易的評判端工作流程:

              接收送出的代碼

                     ||

              編譯代碼  = _編譯錯誤  = 傳回程式設計錯誤結果

                     ||

              運作編譯後的程式 

                     ||

              對輸出的結果進行判斷

 上面這個工作流程我省略了大部分的細節,隻是讓大家都先對整個流程有個整體的把握。

 接着我們再開始說說一個通用的oj一步一步是如何設計實作的。

  一.接收代碼

       這部分可以通過很多途徑,也并非本文的要點,在此忽略,抱歉抱歉。。。

  二.編譯代碼 

       也許習慣在windows下用IDE的童鞋們很少接觸指令行編譯這東西吧?

       沒錯,我們需要用到的就是指令行編譯,在指令行下調用編譯器的指令行編譯程式,讓它來完成編譯工作。

       舉個windows下的例子:我們用微軟的vc++的指令行編譯工具cl

       首先安裝好vc++6.0,注意,在安裝完成最後的時候,他會提示你是否要更改環境變量,記得把鈎鈎選上,不然,你得自己手動修改

       然後,你可以試試運作cmd打開控制台

       準備好一個c/c++程式,在控制台輸入“cl c:/test.c”

       這時你就會發現目錄裡多了test.obj和test.exe這兩個檔案.

       test.exe就是編譯好的檔案,如果你的代碼出現問題,cl會把錯誤提示在控制台上顯示出來

       你也可以編寫代碼來編譯這個test.c檔案

       如:

//指令行下編譯程式

//system函數已經被收錄在标準c庫中,可以直接調用

system("cl c:/test.c");  

三.運作程式

     這是一個簡易的OJ系統中的關鍵部分。

     首先,我們需要對這個運作的程式進行計時,若程式超出時間,必須能自動kill它。否則,評判機将可能因為運作程式死循環而停止工作下一步的工作或者同時運作過多死循環的程式而崩潰。。

     第二,我們需要把這個程式的輸出和輸入重定向到文本。

        輸入流:自動評判機是不會從鍵盤輸入資料到控制台的,是以從鍵盤的輸入需要重定向到文本(我們可以事先寫好這個文本的内容),這樣,就可以模拟手動從鍵盤向程式輸入資料了。

        輸出流:在自動評判的時候沒有人為介入,是以輸出到螢幕顯示并無意義,我們需要把原本輸出到螢幕的内容重定向輸出到文本。而且這樣可以對使用者的程式輸出流進行儲存,也友善接下來的答案評判處理

     鑒于這部分比較沉長~決定拿出來作為一個單獨的篇章來寫,有興趣的童鞋可以等一下下,我會很用力的寫好它。。

四.對輸出的結果進行判斷

      這裡需要用到第三步驟的輸出流重定向的檔案。。

      我們回頭看下第三步驟,重定向輸入輸出流到檔案,也就是說,我們的輸入檔案是事先根據題目準備好的。

     例如前面的 A+B Problem 題目 

      我們可以事先準備幾組測試資料,如

      1 2

      5 6

      8 9

     儲存在一個檔案中(例如:in.text)

     然後由in.text得到一個标準答案:

     3

     11

     17

     儲存在另一個檔案中(例如:out.text)

   現在,我們在第三步的時候,把in.text重定向到使用者送出代碼程式的輸入流,把輸出流重定向到useout.text檔案

   接下來,我們隻需要比較useout.text和out.text的差别,就可判斷出使用者送出的代碼是否正确的了。。^.^

   随手寫了一個簡單的評判比較函數,可以參考下

  int f_compare(char *usout,char *stout)

/*===========================================

檔案比較

參數:傳人兩個檔案的位址,usout和stout。

功能:判斷兩個檔案是否比對,正确放回1 錯誤傳回EOF

=============================================*/

{

int ch1,ch2;

FILE *p1,*p2;

p1=fopen(usout,"r");

p2=fopen(stout,"r");

do

{

ch2=fgetc(p2);

ch1=fgetc(p1);

if(ch1 != ch2) return EOF;

}

while(ch2!=EOF||ch1!=EOF);

fclose(p1);

fclose(p2);

return 1;

這樣,我們一個簡易的oj系統就可以完成了。。

接下來,我會把之前完成的windows版本的oj和linux版本的oj陸續釋出出來,并做盡可能詳細的解釋說明,與大家交流探讨

繼續閱讀