作者： 許凱平 / 計算機及資訊網路中心 作業管理組 副組長
國中生想要參與NPSC程式競賽，除了程式語言的學習外，就是解題能力的培養了。從歷年的題目來看，NPSC中有一部分題目大約相當於國中數學的應用題，如果能夠掌握這一部分的題目，加上初等的程式設計能力，手腳快一點將基本題做完，就有機會跨過初賽的門檻。
前言
近年來程式設計的相關工作，無論是國內或國外，都有相當程度的成長。2014年美國總統歐巴馬呼籲大家學寫程式，也帶起大家對於程式設計教育的注目。國內雖然沒有總統帶頭寫程式，但早從1998年開始，台大計中與資訊學會便以高中生為對象，舉辦網際網路程式設計全國大賽(National Problem Solving Contest on Internet, NPSC)，讓有志於程式設計專業的學生，在進入大學前也有一展長才的舞台。2000年又增設了國中組的比賽，筆者也在這一年擔任國中組的出題與裁判的工作。
受限於經費與場地的限制，NPSC只能容納25~28隊進入決賽。國中組的第一屆報名隊伍只有23隊，所以報名就直接進決賽了。2001年因為報名隊伍超過25隊，所以要進決賽就要先通過初賽的考驗。為了增進比賽的趣味性，題目通常會有一個童話般的情境，選手們首先要耐著性子把冗長的題目敘述看完，才能進一步進行解題。
出題原則
1.題目的難易度：讓參賽的同學，只要有能會輸出輸入與流程控制，就能至少答對一題；能夠使用迴圈/陣列/會使用函數與遞迴可能就可以答對2~3題；能運用一些基本的演算法(二分搜尋、深度/廣度優先搜尋)，就可以答對3~5題。
2.題目所需的數學：儘量控制在國中生可以理解的範圍內，避免有同學因為看不懂題目而無法作答。
基本解題策略
窮舉法：例如利用迴圈將所有可能的解代入，驗證是否成立。
查表法：建立輸入/輸出對應表，以減少計算的時間。
歸納法：找出輸入/輸出的對應關係。
以一個簡單的例子來說
“啟煌得到了全國最佳球員的榮譽，想要買餅給大家一起同樂，一人一盒。雙和餅舖是新北市有名的餅店，定價一盒一百元。老闆娘淑玲是啟煌的忠實球迷，為了慶祝他得到的殊榮，決定給他買十送一的優惠。啟煌統計了一下，一共要送給n個人，請幫他計算他至少要付出多少錢才能買到足夠的餅送大家？[1]”
窮舉法一：
這個題目很簡單就可以從付的錢算出可以拿到的盒數。
100元à 1盒
200元à 2盒
….
900 元 à 9盒
1000元 à 11盒(10+1贈送的一盒)
1100元 à 12盒(10+1+1)
…
1900元 à 20盒(10+1+9)
2000 元 à22盒(10+1)*2
公式：100元一盒加上每1000元會多送的一盒
盒數(m) =付的錢(s)/100 + 付的錢(s)/1,000
m = s/100+s/1000
用窮舉法的話，就可以從100元開始算，每次加100元，看看得到盒數m是否大於或等於n，然後就可以結束，輸出金額。測試OK後就可以先上傳看看，如果這個題目正好是簽到題，應該就可以通過測試。
窮舉法二：
當然這樣的算法會隨著n變大，讓計算時間變長，得到TLE。稍微改善一下，因為原本沒有買一送一的狀況就可以拿到(s/100)盒，也就是說從s=n*100開始，每次減少100，一直到拿到的m小於n再停下來即可知道可付出的最小金額。
例如要拿到25盒
2500元 à 27 盒
2400元 à 26 盒
2300元 à 25 盒
2200元 à 24 盒 ß 小於25 盒，所以我們知道至少要2200元
查表法：
假設想不到更快的窮舉法二，我們可以利用窮舉法一建立從盒數反查金額的陣列。先將S陣列初始為 0，index 是盒數，值為金額
S[index] = value;
|
100元à 1盒
|
S[1] = 100
|
|
200元à 2盒
|
S[2] = 200
|
|
….
|
|
|
900 元 à 9盒
|
S[9]=900
|
|
1000元 à 11盒
|
S[11]=1000
|
|
1100元 à 12盒
|
S[12]=1100
|
|
…
|
|
|
1900元 à 20盒
|
S[20]=1900
|
|
2000 元 à22盒
|
S[22]=2000
|
|
…
|
|
使用上就是直接查陣列，但是如果數值為0的會就往後找，找到第一個有值的金額就對了。
歸納法
{1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,22,…}
我們可以更進一步地利用窮舉法一所產生的數列，找出規律。
當然有些聰明的同學可能很快就想到，可以想成11盒一組賣1000元，先算需要幾組，再補買缺的幾盒即可。
m = (n/11) *1000 + (n%11)*100
當然如果可以找出數學公式，就不用怕TLE了。如何從數列找出公式？可以參考線上數列大全，列如餅乾餅乾更多的餅乾就是A001972。當然可以先猜猜看可能的公式，再看看有沒有差別，再進行調整。當然運用試算表(Excel)進行推論也是個方便的方式
結語
npsc2013 國中組初賽 B 餅乾餅乾更多的餅乾、104年國中教育會考數學非選擇題買宣紙練習書法都是類似的題目。簡單的解題策略就是先用窮舉的方式出算前面的幾組解，再進行建表或歸納出其規律性，找出可能的公式加以驗證。
參考資料
[1] 台中女中程式解題系統，基礎題庫 a009：團購力量大 http://tcgs.tc.edu.tw:1218/ShowProblem?problemid=a009
[2] 104年國中教育會考數學：https://cap.nace.edu.tw/exam/104/104P_Math.pdf
[3] A001972，線上數列大全：http://oeis.org/A001972