解題分享
推薦大家看 Polya 寫的怎樣解題
Polya’s First Principle: Understand the problem
- 容易理解的題目，例如：https://projecteuler.net/problem=370
- 不太容易理解的題目，例如：https://projecteuler.net/problem=367
Polya’s Second Principle: Devise a plan
訂定解題計劃。
- Guess and check
- 數學靈感極佳的人可以嘗試
- Look for a pattern
- 我的愛招。
- 例子：https://projecteuler.net/problem=386。對於小數字情況利用有效率的演算法生出解答試圖找出規律。
- 很多題目知其然不知所以然的就這樣解決了。
- Make an orderly list
- Draw a picture
- 圖片提供直觀的論證
- 例子：https://projecteuler.net/problem=395
- Eliminate possibilities
- Solve a simpler problem
- 暴力法可以解決 small dataset，借此生成小數據測試資料。接著利用小數據測試資料提出有效率的演算法。
- 例子：https://projecteuler.net/problem=386。暴力法笨歸笨但還是有找出正確答案的能力（只是時間花很久而已）
- Use symmetry
- 計算數對個數常用伎倆。
- 特殊一點的用法有計算互質數對 (a, b)，接著再計算 (na, nb) 個數。
- Use a model
- 許多機率困難題目必須使用機率模型來處理，例如 Monte Carlo method，Markov chain
- Consider special cases
- Work backwards
- Use direct reasoning
- 直接坦過去。
- 例子：https://projecteuler.net/problem=218
- Use a formula
- 某些數論冷門題必須用冷門公式解答。
- 例子：https://projecteuler.net/problem=412
- Solve an equation
- 數論題目多屬於此類。有時候我們必須快速列舉畢氏三角形整數邊長，有時候我們必須計算 Totient Summatory Function 諸如此類。
- 例子：https://projecteuler.net/problem=446。直接沒有繞圈餘地。
- Be ingenious
Polya’s Third Principle: Carry out the plan
能夠紙筆計算的題目並不多，多數題目必須寫程式來縮短紙筆計算時間。熟悉並且熟練 C/C++/Java/Python 或是其他程式語言很重要。
實作上 C/C++ 必須留意常發生的 pointer/overflow 等問題。至於 Python 常犯的錯誤就是 list 沒有 deep copy。
Polya’s Fourth Principle: Look back
這點十分重要，解完題目一定要詳閱討論串。我看到許多人解完 ProjectEuler #1，用 O(n) 解完 ProjectEuler #1，便興匆匆貼上程式碼沒有仔細去看 O(1) 解法的妙味，ProjectEuler #1 不是獨立題目不是免洗筷解完就丟，後面許多題目都會利用規則性來快速計算個數（可能搭配排容原理或是有排容原理內含的定理），總之妙味無窮。
