第0047期•2018.12.20 發行
ISSN 2077-8813

首頁 >專題報導

寫給國中生的NPSC解題思維

作者: 許凱平 / 計算機及資訊網路中心 作業管理組 副組長

國中生想要參與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陣列初始為 0index 是盒數,值為金額

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