On Problem Solving 如何解題

新手上路,總是一開始不知道程式該從哪裡開始下手

所以這篇就來介紹一下遇到一個問題時該如何理清思緒、動手撰寫程式囉~

Type 1. 模擬題

通常這種題目的描述會給定一情境模擬,然後要求輸出最終或是進行過程中的狀態

解題思路,如果對程式碼不熟悉的話請先跳脫程式碼的世界,來以口語化的方式表達

先思考假如現在不需要撰寫程式,而是以人腦進行操作的時候,你想到了哪些東西

通常分為兩部份:

一個是你記得的東西,這相當於記憶體,也就是你需要用哪些變數在記這些東西.也可能是目前的狀態、屬性、資料等等

另一個是狀態轉移的過程,而這就是要填上的程式碼.先把狀態轉移的過程以口語的方式記下來,然後再將它們轉為程式碼.

這裡同時要注意到先做了什麼再做了什麼,因為這有關程式碼的順序.另外每個小步驟都要記下來,因為電腦只會照code來操事,一點小細節都不能漏掉

口語的方式轉成code的一些提示:

1. 因為現在怎麼怎麼樣,所以我要怎麼操作 (if 判斷式)
2. 我在這裡要一直做一件事直到... (while or for loop) *這裡通常會用在輸入資料上,但也可能用在其它地方
3. 目前的狀態值要更動成... (statement) 請根據情況編寫適當語句更動變數值
4. 限制條件,所以在什麼什麼情況下我不能動作 (if 判斷式)

檢測狀態移轉是否正確,可以把每個操作過程都輸出來看看

以上技巧應該足夠應付一般模擬題的題目

例題: http://uva.onlinejudge.org/external/1/118.html

思考:

首先給定版面大小,所以我需要先記下來長寬 (兩變數)

再來有初始位置及行進方向 (需要三個變數)

依指示行進機器人,我在移動機器人時需要看我走的方向、轉邊的方向 (所以這些也要納入考慮)

如果我面向某一方,我要轉向時會變向哪一方 (if 判斷,然後發現我們需要更動方向紀錄)

走了之後我會移動到新的座標值 (statement)

但是如果那裡有機器人走丟了,我不能走到那 (if 判斷,並且發現需要變數記錄這個點有機器人走丟)

看看指示結束了沒,如果還沒就再來一次 (while loop)

最後輸出最終狀態

Type 2. 數學題

這部份和模擬題很像,不過題幹內容會偏數學 (因為內容相似所以不再重複)

另外一種題目就是真的會考驗你的數學知識

若對撰寫code有困難,請先自己動手算一下並得出結果確認無誤,假裝你沒有要寫程式,只是很簡單的在算數學而已

通常數學題也不會太過刁鑽,但如果解不出來的話可能就是你那個部份沒學過 (總是不能三角函數都沒學過就來用正餘弦定理嘛)

這時候最好先閱讀相關資料再動手

接著,檢視這些算式,思考這些數字是如何得到的 (題目輸入,或是變數間的關係得到?)

有了算式之後寫成 code 就容易了

如果有問題的話可以把中間過程抓出來看看有沒有錯

例題: http://uva.onlinejudge.org/external/12/1225.html

這題思路,若是手算,就是分別算出個位數、十位數各出現 0-9 有幾次

有了算式,直接改成敍述式即可

Type 3. 尋找規律題

這種題目會給定輸入,通常是尺寸大小或是物體個數等等,然後要求求出有幾種解法、幾種方式、多少數量等等

這些題目有一些一開始並非很容易就可以想出模擬的過程

這時候可以先從小規模的數據開始,可能是製表或是其它方式記錄輸出值

可能的規律來源是來自較小數據的結果,或是和數據本身之間即有關係式 (可以直接從輸入,透過一多項式得到答案)

例題: http://uva.onlinejudge.org/external/106/10696.html

開始代入不同的 N 值,發現 N < 101 時都是 91, 而 N >= 101 時皆為直接減去 10

於是本題即解出

---

初學時常見的題型大概就是這些了,其它比較進階的問題礙於篇幅就不在這裡介紹了 (其實是因為自己懶XD)

其它種類的問題嘛...就改天有機會再寫上來好了XD

祝大家解題愉快:)