ACM Online Judge
一、ACM Online Judge ─ http://acm.uva.es/problemset/
ACM International Collegiate Programming Contest 是個國際型的程式競賽,而 http://acm.uva.es/problemset/ 這個網站提供了許多的題目,可以讓使用者註冊,並且在線上測試結果。首先我們先註冊一個帳號,在網頁中間的地方找到 Register as a new member ,依照畫面的指示即可完成註冊。
接下來可以在它的下方找到題庫列表 Problem Set volumes,題庫分成兩個部分,一部分是 100-899,另一部分是 10000-10599,兩個部分的題目都有難易不同的題目,我們可以按編號右邊的 events 查看每個題目被解出來的次數排行榜,通常被解出來的次數越多的,題目就越簡單,各位同學可以先挑簡單的來做,等到程式夠熟練了,再向比較難的題目挑戰。
看完題目後,可以用 email 的方式把你的程式碼寄給主機測試,方法請參考 How to write/submit programs 這個網頁,另外它也提供從網頁上傳程式的功能 http://acm.uva.es/problemset/submit.php,各位同學可以多加利用。上傳之後,可以到 The Online Judge status 查看執行的結果,如果出現 Accepted 就代表這道題目解出來了。
最後可以按 Statistics for a single author 查看自己解出來的題數,以及按 The Authors Ranklist 查看使用者的排行榜。
接下來我們就來看幾題簡單的題目。
二、#100 ─ The 3n+1 problem
說明:有一種數列型態如下:3、10、5、16、8、4、2、1,它的最後一項一定是 1,而第一項由使用者自行給予,它的規則是,如果這一項是奇數,則它的下一項為這一項的三倍加一,如果這一項是偶數,則它的下一項是這一項的一半,如此重覆下去,直到 1 為止。現在輸入一個整數 N ,計算以 N 為首的數列長度為 L,例如 N=3 時,L=8。
輸入:系統會連續輸入,每行輸入兩個數字 i、j ( 0 < i、j < 1,000,000 ),我們要計算以從 i 到 j 之間所有整數開頭的數列中,最大的數列長度 m (注意,i 不一定大於 j)。
輸出:根據系統每行輸入的 i、j,求出最大數列長度 m 後,依照原來的順序每行輸出 i、j、m 等三個整數。
ACM 的題目通常會要求連續輸入,我們可以用 scanf() 的傳回值得知是否輸入完畢,scanf() 會傳回成功讀取的變數個數,所以我們的程式會寫成:
#include <stdio.h>
void main()
{
int i, j;
while(scanf("%d %d",&i,&j)==2) {
...
}
}
雖然題目中說到整數的範圍是 0 到 1,000,000,而 Turbo C++ 的整數範圍是 -32768 到 32767,但是 ACM 的 Judge 系統是用 Linux 上的 gcc 編譯,它是 32 位元的整數,所以符合這個範圍,因此我們不必將 int 改為 long 或更大的數。
接下來,我們假設有一個函數 M(n) 可以計算以 n 為首的數列長度,因此我們的程式可以寫成:
#include <stdio.h>
int M(int n)
{
return 0;
}
void main()
{
int i, j, k, l, m;
while(scanf("%d %d",&i,&j)==2) {
printf("%d %d ", i, j);
m=0;
if(i>j) {
k=i;
i=j;
j=k;
}
for(k=i; k<=j; k++) {
l=M(k);
if(l>m) m=l;
}
printf("%d\n", m);
}
}
上面的 m 是用來記錄數列長度中最大的那一個的值。接下來,我們看到 M(n) 函數的寫法:
int M(int n)
{
int l=1;
while(n>1) {
if( (n%2) == 0 ) n/=2;
else n=n*3+1;
l++;
}
return l;
}
寫完之後可以按 Ctrl+F9 執行,輸入完測試值之後,可以按 Ctrl+Z 結束輸入。如果程式沒問題,就先把它存檔,再用記事本把它打開,接下來就可以把它上傳測試了。
三、相關網站
接下來我們介紹幾個台灣的中譯站,相信對各位同學有很大的幫助: