2009年3月22日 星期日

成果作品


四、成果作品



1.    貪吃蛇程式簡介

從加入電研社,學了程式設計之後,所寫得程式無非就是去解題目,講難聽一點,都不是為自己寫的。人都有虛榮心,我也不例外;當被認識的朋友知悉我有寫程式
的興趣之後,絕大多數人都會問說:「你會不會寫遊戲?」或是「你會不會寫外掛?」,寫外掛這種程式我確信以我現在這樣的程度我是寫不出來的,所以,我就一
直保持著好好寫一個遊戲的想法。在偶然的機會下,常逛 奇摩知識+ 的我,看到有人為發問kbhit() (註一)函式和getch()
(註二)函式的人解答,使我認識這兩個函式,於是,綜合以上的動機,和一個網友寫的「蛇王」參考之下,我便動手寫了我的貪吃蛇遊戲,一款為自己寫的貪吃蛇
遊戲。

在這樣的條件下寫出來的貪吃蛇遊戲,因為使用效果不佳的函式,造成畫面閃爍,整體給人的感覺就是──「粗糙」,在社團學長的幫助之下,將整個遊戲環境優
化,將這隻程式從見不得人的處境中解救出來。現在,我將開始依遊戲的進程,站在程式碼的觀點上介紹我最後修改的版本。

(註一)
kbhit()函式的用途是檢測目前是否有按下鍵盤上的按鍵,配合流程控制和迴圈使用可以在有按下按鈕才作輸入動作的功用,也就是平常程式會作它的事,當
按下按鈕時,它才會停下來,最普通應用是碼表。使用時需引入windows.h,這個函式庫只有windows支援。

(註二)
getch()含是的用途是讀取在輸入串流內所按按鈕的ASCII值,以及一些特殊按鈕的鍵碼。使用時需引入windows.h,這個函式庫只有
windows支援。



1-1.遊戲開場

style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/ZGzpM4Ne-8MtvNM0fQ__nQ?feat=embedwebsite"> src="http://lh3.ggpht.com/_--EOwdSZaB4/ScZWGuSOkMI/AAAAAAAAAWE/lvXxCfuD--0/s800/%E9%81%8A%E6%88%B2%E9%96%8B%E5%A0%B4.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品





文字基本上是以gotoxy()
(註三)函式來輸出的,這個上下左右進行選擇的點子是來自於手機的設定選單,在程式碼部份我採用非常有彈性的寫法,利用預先定義的
MAX_MAIN_MENU變數,設定選單中選項的數量,並將各個選項的資料(顯示文字、輸出位置)利用main_menu陣列儲存,在執行程式時,上下
移動選項時需要一個暫時的變數來儲存目前的游標位置,並且依此讀取預先存的位置,以變更輸出位置,我利用%(求餘數)來取代列舉法的寫作方式(註四),並
大大降低增加新選項的複雜度;同樣的,我在選擇左右時也採用同樣的寫法,避免太多重複的程式碼出現。



(註三)gotoxy()算是一個網路上常用的一個通用函式,但是想要在Dev-C++使用仍需要自訂,這個函式我是直接上網抓別人寫的,這個函式的功能
是將執行中的命令提示字元視窗的游標放到隨意的位置上,目前我只知道使用方法。這個自訂函式內的敘述需要引入windows.h,這個函式庫只有
windows支援。

(註四)所謂列舉法,就是為每個選項放一個if,當在該選項按下上下左右鍵時,改變其在視窗上顯示的東西,使用列舉法會造成程式碼大量重複,因為不同的地
方只在於位置、內容、以及所有可以挑選的選單細項。

cellpadding="2" cellspacing="2">





style="font-style: italic;">程式碼節錄462~506行

while(ca=getch())

{

  if(ca==-32)

  {

    ca=getch();

    if(ca==72 || ca==80)//上下

    {

     
font(main_menu[ia+1].sx-1,main_menu[ia+1].sy,-1);

     
cout<<' '<<main_menu[ia+1].sa;

     
font(leftsite,main_menu[ia+1].sy,-1);

     
cout<<"  ";

     
font(rightsite,main_menu[ia+1].sy,-1);

     
cout<<"  ";

     
if(ca==72)ia+=MAX_MAIN_MENU-3;

      else
ia+=MAX_MAIN_MENU-1;

      ia%=MAX_MAIN_MENU-2;

     
font(main_menu[ia+1].sx-1,main_menu[ia+1].sy,1);

     
cout<<' '<<main_menu[ia+1].sa;

     
font(leftsite,main_menu[ia+1].sy,2);

     
cout<<"←";

     
font(rightsite,main_menu[ia+1].sy,-1); style="font-family: Courier New;">
     
cout<<"→";
style="font-family: Courier New;">
     
font(79,24,-1);//把游標藏起來
style="font-family: Courier New;">
     
font(-1,-1,0);//清空顏色設定
style="font-family: Courier New;">
   
}


   
else if(ca==75 || ca==77)//左右
style="font-family: Courier New;">
   
{


     
if(ca==75)setting[ia]+=max[ia]-1;
style="font-family: Courier New;">
     
else
setting[ia]+=max[ia]+1;
style="font-family: Courier New;">
     
setting[ia]%=max[ia];
style="font-family: Courier New;">
     
font(sett_x_y[ia][0],sett_x_y[ia][1],-1);
style="font-family: Courier New;">
     
cout<<setting_text[ia][ setting[ia] ];
style="font-family: Courier New;">
   
}


  } style="font-family: Courier New;">
 
else if(ca==13)


  { style="font-family: Courier New;">
   
font(-1,-1,0);


   
gotoxy(leftsite,main_menu[ia+1].sy);
style="font-family: Courier New;">
   
cout<<"  ";
style="font-family: Courier New;">
   
gotoxy(rightsite,main_menu[ia+1].sy);
style="font-family: Courier New;">
   
cout<<"  ";
style="font-family: Courier New;">
   
return;


  } style="font-family: Courier New;">
 
font(79,24,-1);//把游標藏起來
style="font-family: Courier New;">
} style="font-family: Courier New;">


lang="EN-US">



1-2.遊戲畫面初始

      
 接下來就到了設定使用者設定的時候了,也就是設定遊戲模式、遊戲速度、遊戲地圖,其中,遊戲模式裡的食物模式(註五)是我自己想出來
的,遊戲地圖則是讀取障礙物地圖。設定完成之後就開始倒數,倒數完就開始生成遊戲盤面,盤面我是用兩個大陣列進行儲存,一個儲存文字版的,另一個是以整數
儲存蛇身的先後順序,兩個陣列配合,以show_color_board()函式顯示彩色盤面,在show_color_board()內是以自訂函式
font()來設定顏色及位置,在font()裡我有設定配色的代號,在程式中一律使用代號,以便以後更改配色。底下我還有輸出一個記分板,接著,就可以
開始遊戲了。



(註五)食物模式是我偶然之下想出來的,剛開始,我是想說一次一個食物會導致遊戲時間變很久,於是,我就想說乾脆把一開始的盤面全部都放食物好了,可是在
真正寫出程式以後,發現這樣根本不能玩,因為每一口吃到的都是食物,導致尾巴被固定,到最後死路一條,於是,我便改成亂數食物數量,而且還設定食物最多只
會有一半的盤面,這樣遊戲時間就會縮短許多。

 

style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/h9TIgcZJZFC0sbtdoioSpA?feat=embedwebsite"> src="http://lh5.ggpht.com/_--EOwdSZaB4/ScZVZJci4II/AAAAAAAAAVU/uMrMoAlAfD8/s800/%E9%A3%9F%E7%89%A9%E6%A8%A1%E5%BC%8F.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品



圖、食物模式(本圖經反白處理)


1-3.進行遊戲

這裡利用迴圈、流程控制、kbhit()函式和getch(),作成了在使用者按下按鈕時,程式才會作出適當反應,其他時候,蛇身會繼續向前直走,每一次
迴圈都用Sleep()函式進行暫留,暫留的時間長短由遊戲速度決定,蛇移動時是先檢查,如果可以移動的話把原本的頭部換成身體的符號、輸出一個新頭部、
然後決定尾部是否去掉,如果不用去掉代表吃到食物,就該城增加分數,如果沒吃到食物,就把最後一個身體符號去掉。

style="text-align: left; width: 100%; font-family: Courier New;"
border="1" cellpadding="2" cellspacing="2">


程式碼節錄175~249行

while(1)

{

  if(kbhit())//接收所按的按鍵

  {

    ca=getch();

    if(ca==13)

    {

     
while(kbhit())getch();

     
switch(pause_status())

      {

      case 1:

       
return 0;

      case 2:

       
admin=!admin;

       
break;

      case 3:

       
int choose1;

       
do

        {

         
//...pause...(省略)

       
}while(change_setting(choose1));

       
break;

      }

      clrscr();

     
show_color_board(board,va);

      show_score_board(3);

    }

    if(ca==-32)//因為方向鍵的鍵碼是兩個字元,以ASCII -32開始

    {

      ca=getch();

      if(ca==72
&& direction!=2)direction=8;//上

      else if(ca==80
&& direction!=8)direction=2;//下

      else if(ca==75
&& direction!=6)direction=4;//左

      else if(ca==77
&& direction!=4)direction=6;//右

    }

  }

  if(!food_count)

  {

    //...produce food... (省略)

  }

  int vc=move_head(&head,direction,board,va);

  step_count++;

  if(vc==0)break;

  else if(vc==1)

  {

    food_count--;

    score+=setting[1]+step_count/100;

    show_score_board(2);

  }

  else if(vc==2)move_tail(&tail,board,va);

 

  Sleep(velocity);

}





2.    猜數字遊戲

這個程式是我剛學程式沒多久寫的,那時候因為題目還沒有寫多少,很多寫法不是寫得很精練。這算是我第一次用時間函式和亂數函式寫的程式。程式碼第5行和第
6行定義的SIZE和iTIMES分別是數字數和可猜的次數,可以在編譯時變更。第19行的time_t是時間的專屬變數型態。第29行我原本是用int
型態讀,可是很多試玩的同學都會不小心打到其他東西,所以才改用字串讀整行。第56行是使用cmd的pause指令。第62行我採用自訂函式aa還取代輸
入和判斷的功能。第76行的CLK_TCK變數是在ctime函式庫裡預先定義下來的常數,代表一秒所執行的滴答數。接下來看到aa函式的定義,第95和
104行一樣是怕使用者打到非數字的文字,所以採字串讀整行的作法,用字串讀取是後來加進去的東西,為了遷就於舊有的程式碼,所以才又轉成數字陣列,有點
走冤枉路的感覺就是了。從剛開始寫程式時,我就非常強烈的要求排版,所以這個算是剛學沒多久寫的程式,我排版也排的一絲不苟,這個程式的缺點就是走冤枉路
和宣告太多全域變數。以下是實際執行時的圖案。

 

style="width: 100%; text-align: left; margin-left: auto; margin-right: auto;"
border="1" cellpadding="2" cellspacing="2">



style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/EfkZPJPIOjyAueEA8PI1Nw?feat=embedwebsite"> src="http://lh4.ggpht.com/_--EOwdSZaB4/ScZVn8vuZZI/AAAAAAAAAVc/uwEHuZt3JpU/s800/%E7%8C%9C%E6%95%B8%E5%AD%97-1.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品





style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/p1DvBYp9cFpX9Nx2H35jFw?feat=embedwebsite"> src="http://lh5.ggpht.com/_--EOwdSZaB4/ScZVx7IbMRI/AAAAAAAAAV8/ikawQNMBpzE/s800/%E7%8C%9C%E6%95%B8%E5%AD%97-2.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品







圖、猜數字遊戲執行畫面(本圖經反白處理)

 


3.    簡易檔案比較程式

這個程式原本是為我雙胞胎弟弟寫的,他原本是只有學Visual Basic
6.0,為了可以參加程式設計比賽,我便叫他去練習ACM,但是ACM沒有提供Visual Basic 6.0的Judge,
而且這種視窗化的語言一般來說很難利用程式自行檢查,所以,我就用亂數跑出一些測資,然後叫他用檔案I/O來輸出他的答案,然後我就可以用兩個輸出檔來進
行比較,這樣的話就可以知道程式有沒有Accept。

後來,在我弟改學C++之後,這個程式也暫時變成無用武之地,後來,在我二年級在社團當幹部,開始帶學弟之後,就開始又重新用到這個程式,因為ACM如果
程式有錯的話,不會告訴你錯在哪,於是,當學弟解題目時得到Wrong
Answer而來求助於我時,我就會利用這程式來找出兩個人程式執行結果的差異處。

因為主要判斷的檔案是解題目的輸出檔,所以我的程式是用逐行比較的方式寫的,有不同則會輸出不同的行數,兩個檔案的行數不同時也會顯示。這個程式的執行畫
面如下圖

 

style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/iVBU_Dbrbk8301-NlUj9bQ?feat=embedwebsite"> src="http://lh6.ggpht.com/_--EOwdSZaB4/ScZWp4IghhI/AAAAAAAAAXE/xX-NXSG76v8/s800/%E6%AA%94%E6%A1%88%E6%AF%94%E8%BC%83%E7%A8%8B%E5%BC%8F.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品



圖、檔案比較程式(本圖經反白處理)

 


4.    質數輸出程式

這個程式是為了解題目準備的,在遇到題目需要一些質數,且所需數量不多時,直接列舉會比執行時再跑一遍快多了,程式執行完會先輸出質數數量,然後質數會直
接輸出在記事本裡,為了能直接貼進程式碼裡,質數中間均是以逗號分隔。求質數的方法是先開根號,然後以不大於開根號的質數去除,這樣就可以用很快的速度確
認其是不是質數。

 

style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/QyK_APOb3HnseuyzrPMSww?feat=embedwebsite"> src="http://lh4.ggpht.com/_--EOwdSZaB4/ScZWWK21nnI/AAAAAAAAAWk/5sCnJz-0xs4/s800/%E8%B3%AA%E6%95%B8%E8%BC%B8%E5%87%BA.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品



圖、質數輸出程式所輸出的檔案


 

5.讀鍵盤鍵碼的程式(程式碼如下)

style="text-align: left; width: 100%; font-family: Courier New;"
border="1" cellpadding="2" cellspacing="2">


#include<iostream>

#include<conio.h>

using namespace std;



int main()

{

  char ca;

  while(ca=getch())cout<<ca<<" =
"<<(int)ca<<endl;

  system("pause");

}







這個程式是我在測試getch()函式時所寫的程式,為了以後使用方便,我便順手把它做成鍵碼表。

 

style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/l6T7o2m1fdVeU-QICQu5nA?feat=embedwebsite"> src="http://lh4.ggpht.com/_--EOwdSZaB4/ScZTRLz97uI/AAAAAAAAATM/s57nnBQC8cA/s800/%E5%B0%8F%E9%8D%B5%E7%9B%A4.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品



圖、鍵盤

 


style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/iyuII6gYDADhPwadPXo-oQ?feat=embedwebsite"> src="http://lh3.ggpht.com/_--EOwdSZaB4/ScZTvhLqZCI/AAAAAAAAATU/m-mcSsZxV-w/s800/%E9%8D%B5%E7%9B%A4%E9%8D%B5%E7%A2%BC.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品



圖、鍵盤鍵碼表


圖的鍵盤鍵碼表是用我的程式所讀到的,其中綠色字和紫色字都是讀到雙字元,而且雙字元內的第一個字元都是 -32。



 

6.隨意更改命令提示字元游標位置(程式碼如下)

style="text-align: left; width: 100%; font-family: Courier New;"
border="1" cellpadding="2" cellspacing="2">


#include<iostream>

#include<windows.h>

using namespace std;



HANDLE hOuput;

COORD scrn;

 

void gotoxy(int xpos, int ypos)

{

  scrn.X = xpos; scrn.Y = ypos;

  SetConsoleCursorPosition(hOuput,scrn);

}



int main()

{

  hOuput = GetStdHandle(STD_OUTPUT_HANDLE);

  int a,b;

  while(cin>>a>>b)gotoxy(a,b);

  system("pause");

}







style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/YAUAMdU8LG_JZzGKuqgWsA?feat=embedwebsite"> src="http://lh4.ggpht.com/_--EOwdSZaB4/ScZVNQ-oGdI/AAAAAAAAAU0/l5xfI9_ED6M/s800/gotoxy%E6%B8%AC%E8%A9%A6.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品





這個程式是我用來測試gotoxy()函式所寫的程式,程式裡迴圈每讀取兩個數字之後,就馬上執行gotoxy()函式還進行游標換位,圖為實際執行之結
果。

 

7.打愛的鼓勵的程式(程式碼如下)

style="text-align: left; width: 100%; font-family: Courier New;"
border="1" cellpadding="2" cellspacing="2">


#include<iostream>

#include<windows.h>

#define SPEED 60

using namespace std;



int main()

{

  int ia[11]={6,6,3,3,6,2,2,2,6,3,0};//6 3 2

  for(int i=0;i<10;i++)ia[i]*=SPEED;

  Sleep(1000);

  for(int i=0;i<11;i++)

  {

    cout<<"\a";

    Sleep(ia[i]);

  }

  system("pause");

}







  
 這個程式是在社團課時學弟問我的問題,那一次是教跳脫字元,然後那個學弟在試著輸出"\a"之後,就在嘗試使用跳脫字元這個來打節
拍,他原本是用好幾千萬次的迴圈來造成延遲的效果,然後整個程式碼弄得很複雜,然後就跑來問我要怎麼改。我就將延遲用的迴圈全部改成windows.h函
式庫裡面的Sleep()函式,Sleep()函式裡面可以放入一個整數,代表延遲的毫秒數。在反覆嘗試之後,終於把最適合的間隔調了出來,我和那個學弟
寫出這個程式之後都覺得這個程式蠻有趣的,但是在調間隔時間時很麻煩就是了。

 



8.kbhit()函式應用-碼表(程式碼如下)

style="text-align: left; width: 100%; font-family: Courier New;"
border="1" cellpadding="2" cellspacing="2">


#include<iostream>

#include<windows.h>

#include<conio.h>

using namespace std;



int main()

{

  long long la=0;

  bool ba=true;

  while(ba)

  {

    Sleep(100);

    cout.precision(1);

    cout.setf(ios::fixed,ios::floatfield);

  
 cout<<(la++)/10.0<<endl;

    if(kbhit() && cin.get())

    {

     
cout<<"1)繼續 2)歸零 3)結束\n -> ";

      int ia;

     
cin>>ia;cin.get();

      switch(ia)

      {

       
case 2:

         
la=0; break;

       
case 3:

         
ba=false; break;

      }

    }

  }

system("pause");

}







kbhit()函式的功用是檢測是否有按下鍵盤上的按鍵,和迴圈、選擇結構配合之後,便可以很容易的寫出碼表程式,平常時間程式會一直增加時間的計數器,
等到你按下任意鍵之後,程式就會停下來問你要作啥事。計時的功能我是用Sleep()函式進行延遲的,每次延遲0.1秒。

 

9. SetColor()測試程式

 

style="width: auto; text-align: left; margin-left: auto; margin-right: auto;">


href="http://picasaweb.google.com/lh/photo/H94xWEJA5Ut1I5wqj0sPQw?feat=embedwebsite"> src="http://lh5.ggpht.com/_--EOwdSZaB4/ScZlTQLRY9I/AAAAAAAAAYY/AoD_yGn0wX8/s800/%E9%A1%8F%E8%89%B2%E6%8E%A7%E5%88%B6.jpg">


style="font-size: 11px; text-align: right; font-family: arial,sans-serif;">寄
件者 href="http://picasaweb.google.com/taichunmin/oDJBsH?feat=embedwebsite">成
果作品



圖、SetColor( )顏色控制




在原本C++的輸出視窗(也就是命令提示字元)是黑底白字的,但是,只要適當地使用這個SetColor()函式,把文字想改得顏色傳給第一個參數,背景
色傳給第二個參數,就可以把輸出的東西變得美美的。我的貪吃蛇就有特地花時間弄這個東西,要不然黑白遊戲就跟黑白電影一樣會越來越少人想玩。

style="text-align: left; width: 100%; font-family: Courier New;"
border="1" cellpadding="2" cellspacing="2">


#include<iostream>

#include<windows.h>//需要使用到此標頭檔

using namespace std;

void SetColor(int f=0,int b=15)

{

  //f 和 b 參數傳遞形式 i*8+j

  //其中i為亮暗的差別,j為顏色

  // 黑 藍 綠 青 紅 紫 黃 白

  unsigned short ForeColor=f+16*b;

  HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE); //本例以輸出為例

  SetConsoleTextAttribute(hCon,ForeColor);

}

int main()

{

  system("title 顏色控制碼");

  SetColor();//復原

  for(int i=0;i<2000;i++)printf(" ");

  system("cls");

  for(int i=0;i<16;i++)

  {

     SetColor(i,15);

     cout<<"△▲☆★◆◇
SetColor("<<i<<",0)"<<'\t';

     SetColor(0,i);

     cout<<"△▲☆★◆◇
SetColor(0,"<<i<<")"<<endl;

  }

  SetColor();//復原

  system("pause");

}




2009年2月14日 星期六

Lcs 改用 Lis 的作法

取自http://chieh-min.blogspot.com/2009/01/lcs-lis.html
把他轉成LIS 是因為要追求O(nlogn)的速度

作法:
設有序列A,B。
記序列A中各個元素在B 中的位子(降序排列)
然後按在A中的位置依序列出
出按後求A的最長遞增子序列

例如:有A={a,b,a,c,x},B={b,a,a,b,c,a}
則有 a = {6,3,2} , b = {4,1} , c = {5} , x = / ;(注意降序排列)
然後按A中的次序排出
{ a(6,3,2) , b(4,1) , a(6,3,2) , c(5) , x( ) } = { 6,3,2,4,1,6,3,2,5 };
對此序列求最長遞增子序列即可~~

2009年2月13日 星期五

各位acmer學累的時候不妨來看看

從大陸的某個論壇引用的,所以有一些不太一樣的詞請見諒。
1.題庫與網站資源
題庫-在線提交系統(Online Judge)簡介
下面是幾個比較大的在線提交系統(Online Judge)裡面有大量歷年的競賽題目,一般都是註冊一個ID,然後用自己熟悉的語言(如Pascal/C/C++/Java)寫好原始碼上傳即可,通常 網站會即時返回信息告訴你是否正確。 系統裡有一套標準的輸入輸出數據(對外保密,而且通常數據很多很怪),你的程式的輸出和標準輸出完全符合即可。
常見的返回信息有AC(Accepted,通過)、WA(Wrong Answer,輸出有錯誤)、TLE(Time Limit Exceeded,超時)、MLE(Memory Limit Exceeded,內存溢出)、RE(Runtime Error,發生實時錯誤)等,只有AC了才算做對一題。
這裡只是一個簡要介紹,請大家在做題時先看看各網站上的FAQ,Enjoy it!

北京大學Online Judge(POJ)
<http://acm.pku.edu.cn/JudgeOnline/>
建立較晚,但題目加得很快,現在題數和ZOJ不相上下,特點是舉行在線比賽比較多,數據比ZOJ上的要弱,有時候同樣的題同樣的程序,在ZOJ上WA,在 POJ上就能AC。 不過感覺比pku的題目要難很多。這個題庫的一大特點就是Online Judge功能強大,其實pku現在已經是中國最好的ACM網站。

浙江大學Online Judge(ZOJ)
<http://acm.zju.edu.cn>
國內最早也是最有名氣的OJ,有很多高手在上面做題。打開速度快。

西班牙Valladolid大學Online Judge(UVA)
<http://acm.uva.es/>
世界上最大最有名的OJ,題目巨多而且巨雜,數據也很刁鑽,全世界的頂尖高手都在上面。據說如果你能在UVA上AC一千道題以上,就儘管向IBM、微軟什麼的發簡歷吧,絕對不會讓你失望的。

俄羅斯Ural立大學Online Judge(URAL)
<http://acm.timus.ru/>
也是一個老牌的OJ,題目不多,但題題經典,我在高中的時候就在這上面做題的。

俄羅斯薩拉托夫國立大學(Saratov State University)(SGU)
<http://acm.sgu.ru/>
SGU 是俄羅斯薩拉托夫國立大學(Saratov State University)用於培養ACM選手的訓練網站。 這個網站的建成時期較晚,但隨著比賽的舉行以及新題目的加入,這個題庫的題目也日漸豐富。這個題庫的一大特點就是Online Judge功能強大,它不僅使你避開了多數據處理的繁瑣操作,還能告訴你程序錯在了第幾個數據。這一點雖然與ACM的Judge有些出入,但是卻方便了調 試程序。 與UVA相比,這裡的題目在時間空間上要求都比較嚴格,而且更多的考察選手對算法的掌握情況,所以特別推薦衝擊NOI的選手也來做一做。

UsacoGate Online Judge(USACO)
<http://ace.delos.com/usacogate>
全美計算機奧林匹克競賽(USACO)的訓練網站,特點是做完一關才能繼續往下做,與前面的OJ不同的是測試數據可以看到,並且做對後可以看標準解答,所 以如果大家剛開始的時候在上面那些OJ上總WA卻找不到原因的話,可以試著來這裡做做,看看測試數據一般是從什麼地方陰你的。


網站資源:
http://www.608088.com acm很不錯的網站(資料很多),教育網也可以很快打開.

比如:
acm算法介紹算法模版 http://www.608088.com/category-5-1.html
各大OJ解題報告 http://www.608088.com/category-4-1.html

注意:還有一種非常重要的網站資源───用百度搜索你在oj上不懂的題目(例如:pku 1015),就可以看到了。也可以直接打「ACM」等等。有點看運氣,但是其實也有搜索技巧在裡面。

2 學習資料說明
入門其實有兩種方法:
1自己看競賽書,看別人的程序等等。
2上題庫(如:pku和zju)做題。
第一種可以較為系統的學到東西,但是時間久了就會無聊,而且長久實踐不足,編程能力永遠得不到真正的提高。
第二種雖然看著自己AC很興奮,看著自己的帳號排名提高很開心,但是學習不繫統,對較深的知識學習不足,總停留在做簡單題的份上。
最好的方法就是兩種方法相結合。作為入門者還是要以多看簡單競賽書多看題目和程序為主(例如:《信息奧賽輔導教材》、《基本算法稿》、《06暑假培訓》和 《基本算法C++》,都在「初級入門學習」文件夾中),這個學習時間佔70%,同時也要有30%的時間上題庫做題。 畢竟理論學習要和實踐相結合。


3 一些話
真的很不確定這些資料可以起到多大的作用,但是唯一確定的就是自己當年如果有這些東西,那將是多麼~~~事實上這些資料確實對過去新加入的ACMer有很大的幫助。願它對每個看到這份資料的人都能充分起到作用!
ACM是什麼,ACM學習過程中會有什麼感觸。得到不同結果的人會說不同的話。但是唯一一樣的就是:無悔!
關於ACM的介紹還有入門的東西可以在「初級入門學習」文件夾中的「ACM入門進階.rar」找到部分的答案,在百度和google搜索也可以。這裡就 不在多說。大學中可以學的東西很多很廣,計算機專業包括的東西也一樣。具體怎麼樣,大家只要走進西門兩家書店便一目瞭然。如果說程序語言是計算機專業的基 礎,那麼ACM充當這個基礎的角色一點都不過份。ACM中可以學到的是對程序設計語言的深入理解和應用,同時培養出來的是建模和轉化模型的能力,也是解決 問題的能力。這些是優秀計算機人應有的基本。

有人說:「如果再來一次大學,我會在大一大二瘋狂搞ACM,參加省賽,參加區賽,參加世界賽,然後大三開始做項目~~」問題是你參加了世界賽就算 不拿獎你也有資格可以去微軟和google了。ACM是大學生四大競賽之首,沒有水分,完全考平時做題思考積累的實力拚搏。 這幾年國內ACM的發展太快,難度增大,牛人更牛更多,競爭更加悲慘。華師在兩年前參加ACM的人不到10個,現在不下200人。 華師的發展只是全國其他高校延後了幾年時間的一個縮影。但是這是社會進步帶來的我們不得不面對的結果。 例如前面幾屆的師範專業老師就會有到了學校要面對比他厲害十倍的學生的尷尬場面。非師專業也有面試網易騰訊等公司時因為寫不出算法而與高新offer無緣 的情況。這裡更想說的是ACM的好處,而不是讓大家在壓力下不得不學它,要知道許許多多的計算機領域幾乎與ACM無關(例如網頁製作,flash等)以上 這些話是回答那些說ACM沒用的人的,不包括對其充滿熱情的人。
其實ACM的公平不但體現在競賽現場上(通過測試數據就算贏,不管你程序怎麼寫),而且還體現在學習的過程上。這點需要詳細說明一下。
1:學習的方法幾乎一樣入了門之後大家都是在題庫上拚命做題。 全世界沒有一個人例外。
2:自學是唯一的方法。 ACM不是看懂的,也不是聽懂的,而是練懂的。 懂的唯一方法就是要多練多寫。 在賽場上無數悔恨的根源就是平時訓練做題時對沒有完全理解的知識抱有幻想。 台上一分鍾台下十年功!
3:大家平時的生活都是:
<http://acm.pku.edu.cn/JudgeOnline/> 、 <http://acm.zju.edu.cn/>、
<http://acm.uva.es/>。

Fd: Why do you want to give up?

今天我和老師在討論說要去3月資訊奧林匹亞初試的名單
老師說可能就依照這次馬拉松的成績來選
然後我和家齊基本上是保障名額
然後帶一個一年級的去 至於人選就由我來挑選
不過 我看家齊這次比賽感覺很不認真 都沒在用心
所以就騙他說 老師說「你這次考太差了 說不定不給你去比了」
沒想到他居然說「我本來就不想再去比了」
我「....為什麼........」
家齊「每次去都解不大出來...」
難道是之前學科能力競賽沒得名讓你喪失動力?
其實說真的 我一開始寫程式的動力 就是因為不想輸給你
每次看到你ACM的題數追了上來 就更賣力的練習和解題目
去年校內馬拉松 也是不想輸給你才奮力解完20題(去年20題對我來說還算是一個不小的挑戰)
而在過程中 我也越寫越有心得 越寫越有興趣
真的是找到了我自己的興趣
之前 學科能力競賽彰雲嘉區的第一名 對我自己是一個相當大的激勵
而到了全國賽和NPSC的慘敗 更讓我瞭解到應該加強的目標在哪
而你 或許沒有經歷到這些 因為得不到肯定而有點灰心
但 我相信寫程式應該不只是為了比賽吧
更重要的是 自己的執著
不好 可以再努力
怕題目解不出來
那就繼續學 繼續練
或許就被我們不小心矇進了選訓營也說不定阿
就算可能進不了 那我們也看到了全國頂尖的高手是如何解題的阿
而且 不去試試看怎麼知道能不能成功呢?
總之 如果你對寫程式沒什麼興趣了 那我也沒什麼話好說了
反之 我還是希望你能繼續當我的對手
督促我們一起進步.....OK?
可惡...早知道第四題就讓你慢慢去想= =

老實說 我在聽到他不想去的時候
還蠻震驚的
可是 淞任居然沒進 有一點點失望

作啥事都要有人一起競爭
才做的快
想當初 你們兩個跟我說你們有先看時
我就在暗中觀察
你們之間的競爭應該算是我把你們湊成一對的
可是 從注意到你們的差距越來越明顯時
我已經無法介入了
他心中或許已經有了無法彌平的自卑吧
我想 你可以去找一些你們兩個人都沒解過的題目
印下來一起討論 像當初奇怪的河內塔
和這一次的旋轉矩形
你們不應該悶著各自解

你們不像我
當初沒有人可以跟我討論
所以我現在注意一年級學弟時
也刻意弄了一個小團體
就是 皓銓 淞任 豪傑
希望他們遇到題目時可以一起討論
所以我通常都是一起教過來敎

你在跟家齊討論題目時
耐心要多一點 就算你已經想通了
你也要把他引導到懂
就像當初
你上來5樓問我旋轉矩形的時候一樣
我已經懂了 可是我還是會說到讓你懂為止

話說回來
你難得上來問我題目時
心中難得的感動一下
只不過你平常時對我的那一種敷衍
就真的讓我受不了了