NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » 一般 » 綜合討論區
 給新手的程式設計學習參考

作者 主題: 給新手的程式設計學習參考  (閱讀 44653 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
給新手的程式設計學習參考
« 於: 三月 21, 2010, 11:05:36 pm »

這陣子有滿多人討論到如何學習程式設計,
以及提升自己的程式設計功力的問題,
雖然我不是高手或神人,
不過接觸了這麼多年的競賽題目,
心中還是有一些心得和想法,
希望分享給將來想挑戰程式設計比賽的人,
當作一個學習途徑的參考....

再次強調, 下面的學習方式是以參加程式解題競賽為主,
並非全面瞭解程式設計的所有內涵,
畢竟資訊這領域不斷會有新的東西出來,
也是永遠都學不完的....


1.熟練C/C++基本語法:

到書店找一本你覺得看起來最舒服的書,
不用特地找網友推薦的聖經本,
因為它太過於詳細,
除非你的消化能力非常好,
不然看不到1/3就可能會想放棄了....

基本語法, 只要懂標準輸入輸出、變數宣告,
if-else、switch、while(do-while)、for等流程控制語法,
基本上就差不多了....
再來就是學習陣列、字串、struct的使用,
以及簡單的排序法,
進階一點就再學自定函數、遞迴函數等,
這階段主要是學習程式的語法,
讓你的想法可以很快地化成程式碼,
不用想要去解很難的題目....

如果問我有什麼推薦的書籍或網站,
書的話我會推薦子由的「深度學習C++」,
http://www.math.ncu.edu.tw/~ziyou/c++/
初學可以只讀前八章, 甚至第五章的指標可以先跳過,
因為如果只是要解題, 有很多不用指標的寫法,
所以不用多花時間在上面, 將來有需要再回來用....

網站的話, 推薦「Sagit's C++程式設計」,
http://www.tcgs.tc.edu.tw/~sagit/cpp/
雖然它很精簡, 很多語法都沒有提到,
不過正因為如此, 所以很適合給入門者使用,
也可以依照上面的課程進度再回頭看書上的說明....
主要只要看左邊基礎課程1-8、10這幾頁,
還有右邊進階課程的1-8頁....
« 上次編輯: 三月 22, 2010, 12:17:53 am 由 sagit »
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #1 於: 三月 21, 2010, 11:19:19 pm »

2.進入線上程式解題系統練習

學程式絕對不只是要用"看"的就能學會,
自己去實際寫程式才會有成長,
而特別是 debug 的技巧是書上不會教的....
因為沒有人會有那個耐心幫你檢查所有的程式是不是有 bug,
所以找一個可以自動 Judge 的系統是很重要的....

新手的話, 強烈推薦「台中女中程式解題系統」,
http://www.tcgs.tc.edu.tw:1218/
這個網站上的題目是依照程式語法的進度而編排,
讓你學到某種程度, 就有對應的題目可以練習,
而且基礎及初級題庫裡的題目都是不需要處理連續輸入的,
大大降低了初學者進入的門檻。

如果這個網站上的題目大部分都寫過了,
則可以再去找其他解題網站練習,
像是高中生程式解題系統 http://zerojudge.tw/ ,
或是 建中資訊 TOIJ http://tioj.redirectme.net:8080/JudgeOnline/ 等。
« 上次編輯: 十月 26, 2011, 01:53:47 pm 由 sagit »
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #2 於: 三月 21, 2010, 11:43:00 pm »

3.開始學習資料結構、演算法

基本題解到一個程度, 就會發現學的東西不夠用,
這時候就要進入下一個階段,
開始學習資料結構和演算法了....

這部分一樣是去書店找一本你看得順眼的書,
如果不知道買哪一本,
我是推薦蔡明志的「資料結構--使用C (第二版)」
http://www.books.com.tw/exep/prod/booksfile.php?item=0010388749
以及胡昭民的「圖解資料結構」
http://www.books.com.tw/exep/prod/booksfile.php?item=0010427602
這兩本選一本就行了, 主要是看它的觀念,
程式碼可以不用去看....
另外, 樹的章節裡面, 只要看到二元樹(包括二元搜尋樹、Heap)就夠了,
後面AVL-Tree、2-3-4 Tree、B-Tree等可以不用看,
(對程式解題幫助不大, 將來上大學再學就行了)
而二元樹的實作, 可以用陣列來模擬....

演算法的書, 我推薦蔡宗翰的「演算法:使用C++虛擬碼」,
http://www.books.com.tw/exep/prod/booksfile.php?item=0010268484
如果你有在書店裡翻過其他中文的演算法的書,
會發現大部分的章節都跟資料結構的重覆很多,
而這本書主要是以解題策略出發,
各個擊破法Divide-and-Conquer、動態規劃(DP)、貪婪演算法(Greedy)、
回溯(Backtracking)、分支界限法(Branch-and-Bound)等,
看過一遍會有個概念, 而且也提到同一個問題用不同策略解題的比較....

看完這兩本書, 接下來可以去「DJWS的網路日誌」找有興趣的文章來看,
http://www.csie.ntnu.edu.tw/~u91029/
畢竟上面兩本書都不是最詳盡的, 還是有許多沒提到的東西....

而最後就是找有演算法聖經本的Introduction to Algorithms來看,
這本有許多是前面兩本書沒提到的東西,
雖然是原文書, 不過前面的觀念如果有吸收了,
閱讀上應該不會造成太大的困難才是.....
« 上次編輯: 三月 22, 2010, 12:17:12 am 由 sagit »
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #3 於: 三月 22, 2010, 12:05:42 am »

4.使用進階的線上程式解題系統

第二段提到高中生程式解題系統(ZeroJudge),
雖然裡面的題目比較簡單, 可以很容易建立自信心,
但是老實說對於某個程度以上的使用者來說,
學習成長的幫助不大, 這時候可以改到其他網站練習....

第一推薦的就是 USACO Training,
http://train.usaco.org/usacogate
它是美國用來訓練資訊奧林匹亞選手的網站,
進度由淺入深, 所以非常適合用來讓自己慢慢成長....
當然全英文的網站對高中生來說或許會有些排斥,
不過已經有一些熱心的網友把題目翻譯成中文, (雖然是簡體字)
http://www.nocow.cn/index.php/USACO_Training
http://www.wzoi.org/usaco/
前者還有題目的解法可供參考....

第二推薦, 就是最多人用過, 俗稱 ACM 的 UVa Online Judge,
http://uva.onlinejudge.org/
而「Lucky貓的ACM園地」有提供一些題目的中譯還有難易度分級,
http://luckycat.kshs.kh.edu.tw/
可以搭配使用....
如果想一步一步慢慢學習,
其實 UVa Online Judge 也提供了類似 USACO Training 的題目單,
登入後按左邊的「Browse Problems」,
選擇最後一個「AOAPC I: Beginning Algorithm Contests (Rujia Liu)」,
就可以看到依進度排下來的題目單....

最後一個, 則是建中校友建立的TIOJ,
http://tioj.redirectme.net:8080/JudgeOnline/
一樣是中文的網站, 對高中生來說應該比較有親和力,
裡面的題目平均來說比ZeroJudge來得難,
而這個網站也是許多國內程式解題的高手聚集的地方....
« 上次編輯: 三月 22, 2010, 12:19:49 am 由 sagit »
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #4 於: 三月 22, 2010, 12:13:46 am »

5.學海無涯

不知道這串文章怎麼結尾,
就以這句標題做結束吧....
初學者最容易犯的一個毛病,
就是只挑簡單題來做,
於是看似做過的題目很多,
但程度一直沒有進步....

我建議如果基本的資料結構和演算法學得差不多了,
可以挑一些比較有程度的題目來做,
像是NPSC高中組、全國資訊能力競賽、TOI初選,
畢竟會來這個網站的, 主要也是志在參加這些比賽,
就整個年度的題目拿來做, 看是不是都可以解個八成左右,
(NPSC高中組有某幾次除外)
這樣相信你已經有相當的程度了....
而解題時, 不用太拒泥在所謂的正解或假解上,
只要是能在時間內解決題目, 而且答案正確, 就是一個好解....
特別是全國資訊能力競賽、TOI初選等是以各別測資計分的,
一個寫得快的假解可以過四個測資拿到16分,
而一個正解可能要寫很久, 也可能要 debug 很久,
花了那麼多的心力, 還不見得全部的測資都能過,
如果是你, 你要寫哪一個?
當然, 如果心有餘力, 而且正解很實用,
不是那種也許你解完這一題, 這輩子就不會再用到的演算法,
我是覺得多學一些東西是可以讓自己更加成長的....

最後, 歡迎各位不吝提供你寶貴的學習經驗,
給以後有想要朝這個方向努力的人,
有一個可以導引或參考的目標, 以上.....
« 上次編輯: 三月 22, 2010, 12:53:02 am 由 sagit »
記錄

yuscvscv

  • 初級會員
  • **
  • 文章數: 30
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #5 於: 三月 22, 2010, 12:24:36 pm »

特別是全國資訊能力競賽、TOI初選等是以各別測資計分的,
一個寫得快的假解可以過四個測資拿到16分,
而一個正解可能要寫很久, 也可能要 debug 很久,
花了那麼多的心力, 還不見得全部的測資都能過,
如果是你, 你要寫哪一個?

TOI進培訓營的之後的模擬考,測資都頗有水準(不會像入營考都亂搞,NPC問題也可以greedy過),配分也比較有區分正解假解。
前5筆15分,後2筆10分。

這時候正解假解的優劣就會出來了。

況且有些時候通過只是題目測資剛好弱弱,但誰也不能保證比賽時出現的題目測資有多強,

但是正解與假解之間的時間和取捨是頗重要的就是,

不過也不能說正解不重要。


尤其到大學的ICPC/高中的NPSC,在這種只有對與錯的題目,

我覺得對正解的要求度相當高,頂多不知道正解寫個假解試試看,

否則基本上假解很難過,
(今年NPSC高中組決賽的大風吹除外,出題者說他們用random的,加cut可以亂喇過,根據真強者表示,正解在NPSC賽程之內絕對寫不完XD)


總之,如果在初選水準的比賽,可能會比較要求穩定度,(全國賽和TOI入營考)
但進階一點還是很要求正解的。


不過說真的,很多算法大概就是某種題目用一次,但走競賽就是這樣,
誰也不能保證未來的比賽會出現什麼題目,只能不斷充實自己。

//之前有聽說ICPC某區域賽有考到 超大數的傅立葉轉換運算= =

記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #6 於: 三月 22, 2010, 02:46:34 pm »

樓上說的我大部分都很認同,
只是我這一系列文章是給"新手"看的,
對於新手, 我是覺得與其每一題都要求正題,
不如把自己會的東西拿來活用,
像是最短路徑問題,
就可以用Floyd-Warshall、Dijkstra、SPFA加上各種優化去試看看,
會比鑽研一些罕見的演算法來得有用多了.....

當然, 如果已經脫離了新手的程度,
進入到可以被稱為強者的境界了,
而且是以參加這些比賽為樂,
當然可以以正解為目標,
甚至也可以自己去想有沒有更快的寫法,
畢竟這些演算法也是前人想出來的....
主要就是看自己的程度到哪邊,
以及自己有多少時間去做一個取捨吧....
記錄

suhorng

  • 初級會員
  • **
  • 文章數: 26
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #7 於: 三月 22, 2010, 04:17:40 pm »

推:D
老師說的真棒!!
記錄

yuscvscv

  • 初級會員
  • **
  • 文章數: 30
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #8 於: 三月 22, 2010, 05:37:17 pm »

原來如此~


推+1!
記錄

chienyu11026

  • 新手
  • *
  • 文章數: 1
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #9 於: 十二月 22, 2010, 07:07:03 pm »

那請問深度學習c++後面的章節要學到什麼階段才去看呢?
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #10 於: 十二月 22, 2010, 09:34:26 pm »

那請問深度學習c++後面的章節要學到什麼階段才去看呢?

等你想徹底了解C++這個語言的時候,
再去看就行了....

以解題來說, 主要還是基本語法和陣列的操作,
還有幾個STL容器的使用,
物件導向的特性或是樣本的使用並不是一定要會....
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 給新手的程式設計學習參考
« 回覆 #11 於: 十二月 22, 2010, 09:41:53 pm »

stl的東西
只要code複雜度不高
建議還是自己寫 . (尤其是stack)

不然有機會 常數 跟 logN差不多
有機會被測資卡掉唷 . .
記錄

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
Re: 給新手的程式設計學習參考
« 回覆 #12 於: 八月 26, 2014, 04:56:08 pm »

sagit老師太棒了,今年才知道有這個好所在
另 green judge 也很棒,初、中程式 學習 C++ 的最佳網站
我想按讚,數量就一個int吧 2^32-1
記錄
+ NPSC補完計劃 » 一般 » 綜合討論區
 給新手的程式設計學習參考