2011年12月20日 星期二

C 語言入門 - 在線上批改系統練功

如何練習使用基本語法

  自己出個練習題試著寫寫看?寫完隨手測幾個數字發現正確無誤就好了嗎?這樣其實比較辛苦,不如我們找找網路上既有的練習題試試,說不定別人想到我們沒想到的巧妙題目,寫完了只要上傳程式碼還能自動判斷執行效率以及正確與否,多麼方便啊!這種網站去哪找?網路上現在不少,這裡介紹個我比較熟悉,也相當常見的網站。


UVa Online Judge

  台灣俗稱 ACM 的網站。由來是它收錄了不少 ACM ICPC 競賽的題目。詳細介紹留待之後的文章。網址如下:

http://uva.onlinejudge.org

  雖然是英文的,不過也有些好心人翻譯了不少題目出來。網址如下:

http://163.32.78.26/

  網站本身不太穩定,如果死掉了可以先用別人架的鏡像站。但是鏡像站的資料較古舊,有些比較新的翻譯可能沒更新到。但也已有相當數量的題目翻譯了。如果原網站沒問題,建議還是不要用鏡像站。以下是其中一個鏡像站:

http://w.csie.org/~b97115/luckycat/

  但是並非所有題目均有翻譯。翻譯的速度通常是跟不上寫的速度,也與各譯者擅長與不擅長有關,日後仍有必要直接閱讀英文題目。現階段主要是在這裡可以方便找到許多難度僅有一顆星的題目。未翻譯的題目中也有許多難度僅有一顆星的程度,但是並不好找,對初學者而言更無從著手。就以目前到這篇為止,也不足以解開所有一顆星程度的題目。文末會列出此時較適合寫的題目。

  首先我們連上 UVa 的網站,左上角登入欄的底下有個 Registre 的連結,點它。Username 是你的帳號,而 Name 是你的名字。如果你沒有使用過它的舊網站,也沒印象持有舊網站 ID 的話,在 Online Judge ID 填上 00000,否則填上舊網站 ID 則可以把舊帳號整合過來。Results Email 則可以自行選擇勾或不勾。勾的話你之後有上傳題目,它會把結果寄到你的信箱。沒有勾的話也能在網站上看到結果,所以不影響。如果不嫌它很煩的話建議是勾一下,好處是它若發現某道題目需要重新判定大家上傳的程式碼正確與否 (通常是測試不夠嚴謹以致於錯誤的程式碼被判成正確) 的話,在收信時會發現。

  之後請到信箱收認證信,收到後就完成註冊了。接下來在 UVa 登入後,就可以上傳你的程式碼了。請注意如果勾選 Remember me 再登入的話,以後有可能導致沒辦法連上。如果遇到這種情形,請開啟 Chrome 的無痕瀏覽,或 Firefox 的私密瀏覽試試,或是把瀏覽器的 cookie 清掉。

  目前能解的題目,有以下幾題:

10071
10300
11172
100
488

  未列出不代表不能解,這裡只是列出可解的幾道題。但是在開始寫之前,有幾個地方需要特別注意。

  這篇文章放在這個順位,理應存在相當多目前難以說明的東西,硬要作說明則會出現不少新東西要記,也有許多很難講明白的地方。這裡已經盡量講得淺白易懂,若一時記不完可以先大致看過,等到寫一寫出問題再回來查。


征服 UVa 的行前準備:了解線上批改系統

  首先我們必須了解它的基本規則。這類網站人稱 Online Judge,多譯作「線上批改系統」或類似的詞。通常會置有許多題目供人練習,題目會給詳盡的敘述,讓你知道你必須寫出具備什麼功能的程式。你的程式必須能夠接受題目所規定的指定格式的輸入,依題目指定的格式輸出結果。通常會有幾組作為範例的輸出輸入供參考,也可用作測試程式是否正常運行,且給出預期答案。

  線上批改系統之所以有「批改」二字,是因為你可以將你的程式碼上傳到該網站,它會為你測試你的程式。但是程式是無法判斷程式對錯的,又不可能進行人工檢測。因此,最常見的方法是,準備一定數量的測試用數據,稱為「測試數據」,又稱「測試資料」或簡稱「測資」,將你的程式編譯並執行後,餵入測試數據,看你的程式能否在可允許的時間內,產生正確的結果。

  線上批改系統會測試你的程式是否能正常編譯,運行過程有無不正常結束 (也就是當掉) 以及能否在時間內,對於給定的測試數據,將結果計算完畢並輸出。最後,如果前面都通過了,就會檢查你的結果是否正確。結果如下表:

Accepted (AC) - 測試結果正確。
Presentation Error (PE) - 測試結果正確,但格式上稍有不符。
Wrong Answer (WA) - 測試結果不正確,缺漏或夾雜不相干的輸出,或格式嚴重不符。
Time Limit Exceeded (TLE) - 程式無法在允許的時間內完成計算。通常是沒寫法,也可能是方法不夠有效率。
Run-Time Error (RE) - 程式不正常結束。通常是當掉,像除以 0 或是拜訪不該拜訪的記憶體位址。
Compilation Error (CE) - 編譯錯誤。可能選錯語言,傳錯檔案,複製不完全,或你的程式碼根本有問題。

  它餵入測試數據的方法是,執行你的程式,將存放測試數據的檔案導入至輸入中,並將你所有的輸出導出至檔案,再對該檔案進行核對。

  大部份題目會有「多重輸入」。大致有三種形式,題目都會詳述。一種是會在一開始輸入一個數字,代表接下來你必須處理多少組輸入,這種相當容易,先讀完第一個數字就知道有幾組了。第二種是當特定的輸入出現,比如說輸入物品數是 0 或是 -1 的時候,代表的是輸入已結束。第三種較特別,就是它不會告訴你。你必須自行判斷輸入是否已結束。由於檔案不論再大,都一定有固定的大小。在讀到檔案尾的時候,scanf() 或其它讀入用的函數,會告訴你已經到檔案尾了。scanf() 是透過回傳 EOF (即 End-of-File) 來告訴你。所以我們可以寫成這樣:

while(scanf("%d", &n) != EOF)
{
}

  來做反覆的輸入。while 你可以將它看作是沒有 A 和 C 區段的 for。這樣一來,如果輸入還不是 EOF 就會繼續執行程式。若要在程式執行中手動模擬輸入結束,可以輸入 CTRL+Z。按了之後會顯示 ^Z,按下 ENTER 就相當於遇到 EOF 了。

  輸出是否正確,是在程式結束後,才進行判斷,因此留待最後一次輸出,和每讀入一組,便處理後輸出一組,最後得出的結果會完全相同。由於只看輸出,所以你在手動輸入時打入的東西,會確實出現在畫面上,實際上不存在最後的輸出結果中,這點也要注意。

  千萬不要輸出任何關於提示輸入的文字,或其它訊息。例如「please enter a number」之類的絕對不要。這夾雜在輸出中只會被認為你的輸出結果是錯誤的。

  請務必留意換行問題。每一行的「結束」之時,請一律輸出「\n」。這符號雖被稱為「換行符號」,實質的意義卻不是告知「我們需要新的一行」,而是宣告「目前這一行結束了」。請在每一行的結束之時確實輸出「\n」而不要只在需要新的一行時才輸出。

  請務必詳讀題目在輸出格式中,關於「空白行」的敘述。空白行即是什麼都沒有的一行。若是一行之中完全沒有任何東西,直接遇上「\n」的話,就代表它是個空白行。

  通常有以下幾種情形,一種是沒特別要求,這種別輸出多餘空白行即可。要是好心怕批改時搞混而每組之間多輸出一行空白行,也會被認定是錯誤。一種是每組數據「之後」空一個空白行。這意味著最後一組數據「之後」也要空一個空白行,所以一律多空一行即可。一種是每組數據「之間」空一個空白行,這比較麻煩。像是以 EOF 結束輸入的情形,我們不會知道有沒有下一組,所以不能隨意多輸出空白行。幸運的是,我們可以判斷這是不是第一組數據,如果不是的話,在輸出這組結果之前先輸出一個空白行即可。

  判斷方法相當容易。我們用個變數記錄現在是不是第一組數據。一開始還沒輸入時預先設定為「是」,在第一組處理完之後,將這個變數改為「不是」。至於如何使用變數記錄「是」與「不是」,我們可以用 0 或 1 代表。C 語言中 0 即代表「不是」,1 代表「是」。這樣我們就能夠判斷目前是不是第一組。

int first;
first = 1;
while(scanf("%d", &n) != EOF)
{
    ....
    if(first != 1)
    {
        ....
    }
    first = 0;
}

  如此一來,在第一組時 first 的值會是 1。第二組開始就會是 0。

  如果空白行多了或少了,幾乎都會被判成 Wrong Answer。在得到 WA 的結果時,不妨先檢查看看換行是否正確。

  當輸出要求在一行中輸出多個數字並以空白隔開時,請詳細按照敘述去做,別空太多格或是完全不空格,也別在一開始或最後一個數字之後,輸出空格。雖然最後一個空白是看不到的,但它實際存在,批改系統是能夠判斷出來的。

  請不要在程式中保留 while(1); 之類的程式碼。前面說過這方便我們觀察程式輸出結果,因為它「會讓程式無法自行結束」。前面提到有一種錯誤是「在允許的時間內無法處理完所有數據,輸出結果並結束程式」,也就是 TLE,如果放了 while(1); 且執行到了的話肯定是「無法在允許時間內結束程式」,因為它根本不可能「自行結束」。我們知道處理完了,所以看完結果後會手動結束它,但是批改系統可不知道。它可是一板一眼不知變通的。

  儘管我們學習的是 C 語言,但目前上傳時,最好在語言部份選擇 C++。UVa 上面使用的是 ANSI C,這版本的編譯器相當嚴格,容易出現編譯錯誤。

  這樣一來,我們對批改系統有了初步的認識,也擁有了解決批改系統上的基本題的能力。雖然我們連程式的基本語法都還沒有學全,但從此時開始練習,有助於增進對這些基本語法中的基本更加了解與熟練,之後學習其它語法會更加輕鬆,也能更快上手。語法是累積的,而不是分開單獨存在的,從根本開始練習有助於學習更進一步的東西。

  請記得保留你每一題的程式碼。若是使用公用電腦,可以使用 E-mail 夾帶程式碼的檔案,寄給自己。未來會有諸多好處。程式碼通常也不大,就算完成了數千道題,每題都寫到檔案大小 10K (這需要 10240 個字) 也不到 100MB。一部小說通常也不到 10 MB以上的,不用擔心硬碟沒地方放遊戲或其它東西。定期把執行檔清理掉即可,留著程式碼的話執行檔要生幾份有幾份。

  保留程式碼的用意並非要你用在相似題上。請紮紮實實地從頭完成你的每一道題目,而不要剪剪貼貼的,自己思考整個程式的架構與方法,並自己親手打上每一個字。這對於寫程式的經驗絕對是有益無害的。你會對語法更加了解,對程式的運作以及之後學到的每個方法更加熟悉,儘管這比較花時間。

  即使請教他人也不要流於抄襲,在聽完高人指點與精闢分析之後,試著自己從頭思考一遍,親手實作一次,盡量不要參閱程式碼。程式碼建議在解決之後再作參考,看看是否有更好的寫法。在自己親手實作前便參考的話,容易受制於殘存的印象,而只是試著「重現」,並非自行思考每一步的意義並寫出來。這樣會比較辛苦,但是完成後會直接刻在內心,日後更能運用自如。

  題目也不要寫過就算了,之後想到或知道更好的做法,或是有別的想法,都可以多寫幾次試試看。題數也並非絕對重要,要在寫的過程慢慢累積經驗,多嘗試多學習。能從寫題目中獲得多少才是最重要的。