# 02-高雄市國民中學 Python 社團課前通告(2021/9/11)
1. 學校課程進入第三週，各校正在積極安排學生，一學期共要上課15次，每次兩小時，
2. 課程進度如下: 課程內容 ( 請各校各教師 因學生學習狀況適時調整)
課程內容: 包括Python語言和基礎程式設計
(上學期)
01. Python 語言介紹
02. Python程式發展工具
03. Python程式執行的方式
04. 認識Python基本語法
05. 資料型態
(下學期)
06. 運算
07. 指令
08. 函數
09. 初學解題
10. 陣列-容器類型資料
11. 列印文字圖形程式練習
12. 程式邏輯發展練習
3. 第二週我和國光中學 許瀚濃老師分別到國光中學(9/6)、茄定國中(9/10)、普門中學(9/10)去和學生見面說明國中階段學習程式語言的重要性並且鼓勵學生學習。希望每個學校都能安排時間以便溫教授和學生說明本計畫的意義。
4. 過去經會都有科丁高雄分會(每學期)撥款給各位講師，今年方式也許改變，但各位老師上課必須填寫，每次上課日誌，請款單下面有範例格式。
請款單下載網址: https://app.box.com/s/wc89qugqfxxasktmsx9azrtrbkan7s8c
5. 重複叮嚀每位同學都必須填寫社團學員報名表
https://forms.gle/qGwGCkRokerALDb47
6. 記得跟學生提醒要選兩位參加今年11月6號再復華中學舉辦的國中程式設計比賽，學生程度不是重點，參加的意義不在得獎，希望這個比賽未來成為高雄的特色之一。
7. 本週說明影音: https://vimeo.com/602949349/90739c54f7
國中程式設計 在 Re: [請益] 請問國中生程式設計競賽入門- 看板Soft_Job 的推薦與評價
※ 引述《peanut97 (丁丁)》之銘言：
: 遇到一個國三生，有輕微亞斯伯格症，對電腦、程式非常有興趣。
: 應該說，只讓電腦進入他的世界。
: 家人已經放棄讓他以課業升學。
: 他想要做一個瀏覽器、想要修改Android作業系統，喜歡Linux環境、
: 喜歡MAC。唯獨程式語言不太會。
: 我正在教他PHP網頁。
: 未來想幫助他往「程式設計競賽」方向走，但是程式設計競賽好像比較硬。
: 請問「程式設計競賽」，有沒有比較好入門的方向呢？
: 對未來要走軟體的國三生來說。
版上有許多大大與一些我十分敬佩的學長也有在逛這個版
如果有哪裡講錯麻煩站內信或推文指正一下 <(_ _)>
先從「程式設計競賽」這件事情開始談起好了
先來了解一下有哪些程式競賽、贏了程式設計競賽可以幹嘛
因為國中生可以比的實在是很少，所以以下我所提到的都是國高中生
大部分都是高中生才能夠參加
1. NPSC
https://contest.cc.ntu.edu.tw/npsc2015/schedule.asp
台大舉辦的比賽，每年一次，有分國中組跟高中組
分初賽跟決賽，初賽是線上賽，在家裡或是任何有電腦的地方都可以比
初賽過關之後比決賽，要去台大計算機中心比賽，有好吃的點心跟餐盒
題目的話可以自己上這個網站找一下歷屆題目
國中組的題目一般來說不會太難，有一些字串處理或是模擬題
難題大概是DFS（深度優先搜索）BFS（廣度優先搜索）跟最短路徑
（參加的年代有點久遠，所以我不太確定）
高中組的題目難度就高了許多，DFS, BFS, DP（動態規劃） 都是基本
可能會出現一些比較特別的演算法，或是網路流(flow)、計算幾何之類的題目
我參加 NPSC 是從國二到高二
我高二是大概五年前的事情，所以算是有一點遠了
但 NPSC 我覺得滿不錯的，而且是少數國中生也能參加的比賽
2. 北市賽（地區賽）
https://contest.tp.edu.tw/?id=1412135239
升上高中以後，多一個地區賽可以比，我比的是台北市資訊能力競賽
我們都簡稱北市賽，其他的我記得有中區跟南區，東部跟新北我就不是很確定了
北市賽有名額限制，如果同高中有太多人想參加，會先比個校內賽（學校自己辦）
獎項分成四種：一等獎*5、二等獎*5、三等獎*10跟入選獎
前十名（也就是一二等）可以參加全國賽
這我高一有比過，有分成筆試跟上機
比重好像是30%跟70%，這我不太確定
3. 全國賽
各區的前十名來比
這我沒參加過所以沒什麼可以講XD
全國賽的前十名可以保送TOI（等等會講）
4. 台北市軟體競賽
https://tpc.taivs.tp.edu.tw/
高中高職都可以比，組別也不同
高中組題目跟其他比賽大同小異
我高二有參加過，那時候是在松山工農比
5. TOI
TOI就是臺灣資訊奧林匹亞研習營Taiwan Olympiad in Informatics
https://toi.csie.ntnu.edu.tw/
聽到奧林匹亞就覺得很厲害，因為這真的很厲害
上面講過，全國賽前十名可以保送這個研習營
另外20個名額會再舉辦一個入營考招生
進去以後一共30人，我們稱之為第一階段，簡稱1!
1!會到師大住兩個禮拜培訓，每天都上一些資結/演算法的課
每個禮拜都會有一個小考試，會決定你能不能到第二階段（俗稱2!）
我高一的時候有進1!
在裡面生活滿愉快的，因為吃住都不用錢，而且學校那邊可以請公假
請兩個禮拜公假XDDD
1!的大約前12名可以進2!，然後再培訓兩個禮拜
最後取前4名，就是國手了，就可以參加 IOI 國際資訊奧林匹亞
https://toi.csie.ntnu.edu.tw/main_01.php?ID=17
每年舉辦的地方都不一樣，2014在台灣辦過
以上五個就是高中生基本上可以參加的競賽
其中最重要的當然就是TOI
為什麼呢？因為如果你夠強當上國手然後有拿牌，可以保送任一大學的資工系
你想去台清交成任何一間都可以
如果沒有前四名，但你進2!而且名次在滿前面，也可以靠推薦的方式去推資工系
這個推薦跟學測指考都沒什麼關係，是另外一個特別的管道
所以，如果你把資料結構/演算法練到超級猛但是國英數超級爛，還是可以進112資工
但這種人極少而且超極端XD
談完了資訊競賽有哪些，來談談這些比賽考什麼跟計分方式
每個比賽大概會有六題以上，基本上都用英文代號，也就是pA, pB, pC, pD, pE...
答對叫做AC(Accept)，答錯叫做WA(Wrong Answer)
超時叫做TLE(Time Limit Exceeded)，其他還有一些我就不再贅述
一般的比賽時間大概都三個小時起跳
每一題的得分是：答對時間 - WA次數*20，沒答對的話則這題不加分不扣分
比賽的時候會有即時計分版，選手也看的到；但比賽結束前一小時會封盤
現場比賽的話滿好玩的，只要答對一題就會送你一顆氣球
你看誰前面氣球多就知道誰最神XDD
考試類型的話就是大家所熟知的資料結構/演算法
https://www.csie.ntnu.edu.tw/~u91029/ 列出了許多有用的東西
通常會用一個很生活化的方式包裝題目，讓你覺得比較有趣
像是這一題：https://tioj.infor.org/problems/1026
其實就是考你二進位轉換，但把題目包裝過
有些題目很好玩包裝的很好，你拆一拆之後會恍然大悟：阿！原來是這個！
就是那個 moment，會讓你覺得超級有趣（至少我自己這樣覺得XD）
或是這一題，https://tioj.infor.org/problems/1143
說穿了就是 BFS
或這一題：https://zerojudge.tw/ShowProblem?problemid=b127
題目落落長，但看穿了其實就是費式數列
講了這麼多，終於可以回到正題
程式解題這件事情，你要引起他的興趣的話，我覺得可以從兩個方向
第一個就是從利誘下手，跟他說「你這個很強的話可以保送台大資工喔」
第二個就是讓他真的愛上這些解題的過程
怎麼做？先讓他解一題看看
你先去各個online judge看一些答對率比較高的題目
找一題自己覺得有趣的又不會太難的，然後叫他解解看
解完了就再找一題，盡量找一些有趣一點的，試著引起他的興趣
或是你可以直接拿一些經典題，一步一步引導他
例如說經典的背包問題：
你現在有一個容量是100公斤的背包
你有一堆物品，每一項都有一個價值V、重量W公斤
每一項物品都只有一個，也就是你只能選擇拿/不拿
你要怎麼選擇，才能讓你拿到的價值最高？
我有一個原則是：先求有，再求好
一個最簡單的想法是：我窮舉不就好了嗎？
如果有n個物品，一共有2^n種拿法，保證可以找到解答
這時候可以順便帶入時間複雜度的概念
問他說：那如果n是10000的話怎麼辦？2^10000電腦跑不動耶
那就要想有沒有更好的解法
一步步提示他，接著一起完成這一道題目
光是背包問題就有一堆可以繼續延伸
像是剛講的0/1背包、無限背包、二維背包等等
有興趣的可以參考背包問題九講：https://love-oriented.com/pack/
除了這個，也可以教他最短路徑
最短路徑就有幾種不同的演算法，每一種的思考方法都不太一樣
或若你覺得這些太難，就從排序法開始吧
泡沫排序、插入排序、快速排序、合併排序、桶子排序...
每一種都有各自的想法跟想解決的問題
二分搜也是一個很好的入門
你可以說：現在你有1000個數字，如果我要問你：500在不在裡面，你要怎麼做？
他可能會回答：就從第1個掃到第1000個阿
接著你問說：那如果我要問你很多次呢？500, 501.., 600, 700在不在裡面？
他可能會回答：跟剛才一樣，每次問都掃一次
你就問說：那有沒有更好的方法呢？假如我們排序以後，會變怎麼樣？
話說我覺得用終極密碼來講二分搜還不錯，兩個有異曲同工之妙XD
如果以上都太難，就從一些基本的字串處理之類的開始
可以參考acm的一星題：https://luckycat.kshs.kh.edu.tw/
或是一些online judge比較多人答對的題目
寫完之後切記，一定要上傳！
為什麼？因為答對會超有成就感！成就感也是很重要的一部分
藉由這種線上解題系統，就可以增加成就感，而且有些還有排名
讓你知道你這題時間第幾名、code的長度第幾名
有時候會為了縮code長度用一些奇淫技巧XD
一步步引導，從慢到快，從無限制到有限制
從這些過程試著引起他對程式解題的興趣
試圖讓他為「阿！原來可以這樣」的感覺感到興奮
一旦引起他的興趣，他應該會沉浸在這樣的世界裡面
像是有一題我就覺得超級有趣
https://tioj.infor.org/problems/1513
你有一個數列，除了一個數字以外兩兩成對，找出那個數字
數列長度<=100000，0<=數字<=2^31
例如說：1 2 3 2 1，答案就是3
0 0 0 777 0 0 0，答案就是777
這題就很適合先求有再求好
你可以 sort 之後比a[i]跟a[i+1]，但你發現這樣不夠快
你可以 map 存起來之後檢查，但你發現這樣記憶體耗太多
正解是什麼就留給大家思考，我自己是很愛這個簡單但神奇的解答
最後附上一篇強者我學長的文：Re: [討論] 所以練acm都底有啥好處？
https://www.ptt.cc/bbs/Programming/M.1411474900.A.746.html
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.216.67.187
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1451998694.A.9BA.html
... <看更多>