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 結束輸入。如果程式沒問題,就先把它存檔,再用記事本把它打開,接下來就可以把它上傳測試了。

 

三、相關網站

接下來我們介紹幾個台灣的中譯站,相信對各位同學有很大的幫助:

 

上一頁

首頁

下一頁