PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 如何自學程式解題

看板Prob_Solve (計算數學 Problem Solving)作者Favonia (貓貓最乖了)時間13年前 (2011/06/16 21:29)推噓4(4推 0噓 11→)

留言15則, 4人參與討論串4/8 (看更多)

※ 引述《x000032001 (某數..失業中)》之銘言： : 原PO背景: 還沒上大學高職畢業想練功 : --- : 玩程式解題大概一年多了 : 覺得自己有瓶頸存在 : 遇到題目常常有完全沒頭緒的障礙 : 訓練programming的話是不是要繼續讀DS & algorithm的書好? : 充實多點理論再去寫題目的話才有幫助是這樣嗎? : 讀哪些書比較好呢? : 網站的話..我資質魯鈍看DJWS常常看不懂XD 警告：這是原 Po 七八年前的心得，如果有什麼新的東西還請版友補充。跟你分享一下當年自學的心得（當年的基礎混到現在也還能用，所以應該還有參考的價值）首先就是你可能要意識到常見的「解題」終究無法幫你學到更精妙的演算法。用數學做譬喻，這有點像是國中高中職故意出很刁鑽的數學應用題，但不論怎麼刁鑽，也不可能出現高等微積分的東西。常見的「解題」亦如此；無論題目如何包裝，如何拐彎抹角，大都出不了某個「基礎範圍」。如果你只是要學這個「基礎範圍」，解題可以磨練你解應用問題的技巧；若不是，恐怕到最後將迷失在一些瑣碎的技術上面。平常寫程式時，這個「基礎範圍」倒也滿夠用了。等等會回來講這問題。先來講入門書。在我個人有限的見識之下，真的沒有一本書或網站比 Introduction to Algorithms （當年看第二版）更適合當入門書。當時有中文翻譯，不過那本翻譯個人不推薦。先講中文米文的問題：平均來說，米文書的水準比中文書高很多，米文網站資源也比中文網站多非常非常多；而中文翻譯通常比較差（包括排版，如果你覺得排版賞心悅目很重要），搞不好比原文更難懂，慎之！我很感謝當年導師推薦給我 I2A；當時我米文非常差，前言耗費多時才讀完，但習慣以後速度也越來越快了。個人覺得花這時間非常非常值得。慢慢啃這本書所學到的知識，遠比同時間閱讀其他中文書學到更多。另外講一下許多演算法書的問題。很多書（尤其是中文書）看上去列舉了很多別人沒有提的奇妙演算法，但這些書的缺點就是沒辦法給你一個完整的概念。這有點像是學了各種奇招，卻沒有把一門武功從基礎扎扎實實的學好，終究底子不夠，無法融會貫通。徹底學好基礎後，這些奇招只要看到就能馬上納為自己功夫，沒什麼好羨慕的。見一個就學一個！而推薦 I2A 這本書，正是因為這本書雖然奇招不多，但可以給你非常好的基礎。一定還有其他書也有同樣的效果，只是我沒讀過而已。回來講通常「解題」所需要的「基礎範圍」。I2A 那本書最大缺憾就是網路流（network flows）的招數不夠多，遠不夠應付平時解題需要。說實在我到現在還不知道有哪本書清楚，完整又適合初學。Algorithms in C Part 5 (by Robert Sedgewick) 也許可以學到一些招數？Introduction to Graph Theory (by Douglas West) 這本書雖然是在講圖論，但也有一點演算法。或許到時候自己找國外課程網站的上課筆記比較快？這可能也要請版友補充了。兩本書在這： http://www.informit.com/store/product.aspx?isbn=0201316633 http://www.amazon.com/Introduction-Graph-Theory-Douglas-West/dp/0130144002 再來是題庫網站。我知道長久以來大家都喜歡寫 UVA 的 ACM 題庫。但這同樣有馬步都沒蹲好就一直想要打架的問題。ACM 題庫還有一個致命的缺點，就是你根本不知道你怎麼錯的。為此我推薦 USACO 網站： http://train.usaco.org/usacogate 這是米國用來訓練資訊競賽的東西。既然他們都公開了就拿來用。這網站不僅有演算法介紹，課程和題目按部就班，當你錯的時候也會給你測資，在初學時比常見的 ACM 題庫都還好。或許還有其他類似的網站，但我已經很久沒關心了... 如果你的野心不只「基礎範圍」，I2A 依然是我所見過最好的入門書。當然它還是缺少很多很經典的資料結構或演算法（如 splay tree, 雖然書裡面其實有跟讀者提名字），需要自己補起來，但讀完後應該是有辦法自己補起來的！總之不論你未來想往更深奧的演算法邁進，或是只是想應付解題，這本書應該都很適合當起點。或許也可以參考國內外大學教科書選哪本。就我所知好像也有人用 Algorithm Design (by Jon Kleinberg & Eva Tardos), 不過這本我沒讀過，無法向你推薦或反推薦。 : --- : 想自己寫一些實用的小程式會發現有點卡不知道怎麼設計 : 這個方面就是需要讀software engineering吧? : 是不是等大三大四再去接觸就可以了? : 懇請大家給我一些建議~"~ 個人覺得知識沒有「什麼時候再學」的問題，只要先學好基礎就行。相反的，如果你大學畢業後發現少了什麼，趕快補起來也很好呀。如果有時間有興趣就衝吧！我猜很多人會跟你說去學一些常見的設計模式（design patterns）自然就會知道常見的問題怎麼解決，但我個人其實更想推薦你從頭學程式語言的理論基礎。這將會徹底改變你對程式的看法！如同學好基礎後奇招無所畏懼一樣，那些設計的奇招也是見一招拆一招，甚至常常你自己可以想出更好的。我講的不是那種只教某種語言的普通課程，而是可以看透幾乎所有程式語言的方法！可惜台灣好像沒有很多師資，資源少到不知道該如何介紹才好。（也有可能是我見識淺薄，認識不夠多人，還請大家補充。）聽說中研院暑假有相關的研習營，也許可以去打聽一下。至於你講的軟體工程，跟程式語言有密切關係，但還包括很多額外的學問，像是怎麼跟人合作或是長期維護一個軟體之類的。不過我想，就你的目的而言可能都用不到？xDD 希望這篇文章對你有幫助！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.39

推

x000032001

06/16 22:14, , 1^F

06/16 22:14, 1^F

要省錢可以買二手的！然後一定還有其他好書啦，所以應該沒到聖經這麼誇張。另外我更新了一部份文章。

推

danielsig727

06/17 15:13, , 2^F

06/17 15:13, 2^F

→

danielsig727

06/17 15:15, , 3^F

06/17 15:15, 3^F

→

danielsig727

06/17 15:15, , 4^F

06/17 15:15, 4^F

→

danielsig727

06/17 15:16, , 5^F

06/17 15:16, 5^F

喔太好了有人出現了 xDDD 聽說這本網路流內容夠多，可以問一下是怎麼回事嗎？ xD

→

danielsig727

06/18 00:15, , 6^F

06/18 00:15, 6^F

→

danielsig727

06/18 00:16, , 7^F

06/18 00:16, 7^F

→

danielsig727

06/18 00:17, , 8^F

06/18 00:17, 8^F

→

danielsig727

06/18 00:18, , 9^F

06/18 00:18, 9^F

光看目錄好像看不太出來。有講 Dinic 演算法或是 blocking flow 嗎？我模糊的印象中 I2A 沒有講這個。blocking flow 配合好的資料結構可以進化成非常快的演算法，個人覺得值得一提。那個「好的資料結構」是 dynamic tree, I2A 中好像只有提到名字 xD 關鍵章節 ==> 7.3 Choosing Good Augmenting Paths （剛才偷偷翻一下，有特別講 scaling, 但還是沒講 blocking flow. 我覺得 scaling 不夠「基本」入門書不講就算了，但解題有用！xDD 印象中 I2A 好像沒有。） ※ 編輯: Favonia 來自: 140.112.30.39 (06/18 02:20)

推

a127a127

06/18 20:24, , 10^F

06/18 20:24, 10^F

→

DJWS

06/19 15:15, , 11^F

06/19 15:15, 11^F

→

DJWS

06/19 15:16, , 12^F

06/19 15:16, 12^F