---
title: insideAPCS Day 6~10
tags: insideAPCS
---

# insideAPCS Day 6~10

[ToC]

### Day 6 APCS 考試內容 Overview

APCS 分為兩個大部分，觀念題和實作題。觀念題以選擇題為主，旨在測試考生對於程式語言的觀念是否正確。除了考對於邏輯應用及操控記憶體的正確性，電腦科學概論知識也常會出現在考題內，此外也會以C語言寫出範例程式考基礎程式相關知識及演算法等高階題目。

在 [APCS 官網](https://zh.wikipedia.org/wiki/%E5%9C%A8%E7%BA%BF%E8%AF%84%E6%B5%8B%E7%B3%BB%E7%BB%9F)上公布的觀念題範圍如下：

> - 程式設計基本觀念 (basic programming concepts)
> - 資料型態 (data types)
> - 常數 (constants)
> - 變數 (variables)
> - 視域 (scope)：全域 (global) / 區域 (local)
> - 控制結構 (control structures)
> - 迴路結構 (loop structures)
> - 函式 (functions)
> - 遞迴 (recursion)
> - 陣列與結構 (arrays and structures)
> - 基礎資料結構 (basic data structures)
> - 佇列 (queues)
> - 堆疊 (stacks)
> - 基礎演算法 (basic algorithms)
> - 排序 (sorting)
> - 搜尋 (searching)

實作題則是在為期兩個半小時的時間中出四個上機考題目，每一題都有不同的輸入及要求的輸出，而我們的工作就是要寫出能夠寫出能夠正確輸出的完整程式或是函式。

而在這邊的上機考指的是會有一個[線上解題系統（Online Judge）](https://zh.wikipedia.org/wiki/%E5%9C%A8%E7%BA%BF%E8%AF%84%E6%B5%8B%E7%B3%BB%E7%BB%9F)測試考生寫出來的程式是否能夠達到題目要求，並按照題目敘述給分。在 APCS 中總共會有四題，每題 100 分，但每一題都會有不同難度給分的機制，因此並不是很難的題目就不會去寫。

在 [APCS 官網](https://zh.wikipedia.org/wiki/%E5%9C%A8%E7%BA%BF%E8%AF%84%E6%B5%8B%E7%B3%BB%E7%BB%9F)上公布的實作題範圍如下：

> - 輸入與輸出 (input and output)
> - 算術運算 (arithmetic operation)
邏輯運算 (logical operation)
位元運算 (bitwise operation)
> - 條件判斷與迴路 (conditional expressions and loop)
> - 陣列與結構 (arrays and structures)
> - 字元 (character)
字串 (string)
> - 函數呼叫與遞迴 (function call and recursion)
> - 基礎資料結構 (basic data structures)
> - 佇列 (queues)
> - 堆疊 (stacks)
> - 樹狀圖 (tree)
> - 圖形 (graph)
> - 基礎演算法 (basic algorithms)
> - 排序 (sorting)
> - 搜尋 (searching)
> - 貪心法則 (greedy method)
> - 動態規劃 (dynamic programming)

雖然分為兩個不同題型，但考的內容大同小異，都是考有關程式設計的能力，但因為實作題的範圍遠大於觀念題，因此實作題的難度往往難於觀念題，也幾乎不會出現實作題的分數大於觀念題的情況。


在準備方法上，大部分都會直接學習 C/C++，並在練習程式的過程慢慢加上不同技巧，步驟幾乎可以從上面的實作題範圍慢慢練習下來。但由於這樣講太籠統，因此在未來幾篇會大致介紹在 APCS 中會遇到的問題，並提供大致上的學習方向及資源。

### Day 7 Re: 從零開始的競程生活

> 長話短說，請直接[點我](https://github.com/goodjack/awesome-cs-training)進入新世界。

-----

任何事情要從完全沒有概念開始是非常困難的，尤其是初次接觸程式這方面的新手，看到要面對一行又一行的文字簡直如讀天書，明明想要理解卻不知從何下手，很容易就因此放棄。

為了保持動力，這時候我們就需要一個契機讓我們想要繼續學習下去。以我的案例來說，因為在校內就有很多同學也在學習程式競賽，因此就算氣餒也會想要跟上他們。但很明顯這種情況只會發生在極少數的學校，能夠在一開始就接觸到這種學習群體的機會也很困難，因此主動為自己生出學習動機是必要的。

因此在這裡我想要先列出幾個不同方式能夠增加自己的學習動力：

1. **拉一位同學下海 / 抱大神的大腿不放**

這是我在當時度過困難期的方法。我有一位一樣會寫程式的同班同學，但他在之前就有學習 C 語言的經驗，加上他的學習能力也比我好，因此當我遇到不會的問題時第一個想法就是問他，硬是巴著他，就算他覺得很煩也要嘗試弄到懂。

當然在這部分可以不只有一位，也是有很多同儕和學長姐能夠切磋一起成長，不要因為怕麻煩到對方就不敢請教，因為要嘗試把別人教會也是在寫程式時要學會的技能（如除錯等）。有時就是不想要麻煩別人，但自己又沒有能力用上網查詢的方始弄懂，真的會煩到快往生。


而當有同學不會時也可以幫助他試著釐清問題。不要永遠認為某個地方已經完全搞懂了，當他提出問題大部分都是因為他想的比較深，遇到一個說不通的地方想要搞清楚，而正常我都不會想到那麼深而一起陷入困境。而在得到答案的瞬間，又會發現自己成長了許多。

2. **嘗試加入各種學習群體，把自己泡在裡面**

若是在 Google 上搜尋 APCS，會發現坊間會有很多線上/實體課程可以參加。這種課程非常適合剛起步的學生，因為會有人手把手拉著你往上爬，在對的時機點提供你資源，在各個角度切入感覺都很適合。但很神奇的是，在我認識的朋友當中，**沒有任何人**是透過這樣的管道學習的。

或許多少會有採樣偏差，但幾乎所有人都是透過互相教學/在網路上找資料一路學上來的，就算是有上過課也都是在國中以前的事情。或許在高中可以跳脫「所有東西都要老師教才能學」的思考框架，透過自己思考而學會的東西才是自己的。<!--其實這句話是講給自己聽的嗚嗚嗚-->

據我所知，資訊方面的學習群體幾乎都在 Facebook 及 Telegram，FB 社團有不少人在討論，也有很多熱心的朋友及老師會耐心的回答，基本上你想到的問題都有人問過了。加入不說話也無妨，但在社群的耳濡目染下，相信會更有動力繼續學習。

3. **找到有脈絡的學習教材，並不要放棄學習**

不論是跟著校內學長姐做的 PPT 學習，還是自己在網路上找到的優質資源，只要決定好就不要去懷疑他，這種猶豫只會阻止自己持續學習。當時我是透過資訊之芽的語法班及算法班的講義、題目一路練上來的，常常會覺得這個太難了吧，真的有必要學嗎一路找理由，總是拿石頭砸自己的腳，但事實上最好的資源/最好學的方法都擺在眼前了，只是自己的腳在抗拒往前進。

由自己創造這種動力的必要性並不只是在學習的一開始，在進到每一個階段也是如此。從開始接觸語法，寫出第一個"Hello, world!"程式後，會出現更多沒有理解過的東西。當自己爬得越高時，前方高牆只會再次顯現他的高大，階梯也會變得越來越難爬。而若是在這時候往回看，只會覺得之前走過的路對現在的挑戰來說只是小菜一碟罷了。

今年才準備要升上大一的我，面對到的狀況也和之前無異，不過學習的內容從單純的語法和演算法增廣到不同領域而已。所有資料都由許多非常好心的大哥哥大姊姊幫各位整理好了，不只是高中生，事實上對於所有剛進入資訊領域的同學也非常適合，強烈推薦。

- [**從零開始的演算法競賽入門教學**](https://emanlaicepsa.github.io/)
- [**以台灣高中生為出發點的資訊培訓相關資源彙整 <-- Click me**](https://github.com/goodjack/awesome-cs-training)

但當然，要靠自己跨出第一步是最需要勇氣的。若是覺得孤單也請不要吝嗇地向身邊的大神同學們取暖><

### Day 8 程式自學方式

昨天主要描述在心理層面應該要注意的事情，今天則是從實際層面上細數在自學並準備 APCS 時會碰到什麼東西及要怎麼克服。以下列出五點：

1. **擁有基本電腦基礎知識**

在 APCS 中實作題是大家最需要準備的部分，但在練習寫程式的路上其實會忽略很多在這其中學不到的電腦基礎知識。可以參考大一的計算機概論等書籍即可，因為實際上並不會考很深的知識，因此建議只要認真翻過一兩遍就足夠了，同時也可以很快速地架構出從資工到電機的各種領域藍圖。

2. **熟悉 Linux 作業系統**

在 APCS 考試時間使用的作業系統，不是常見的 Windows 或是 Mac，而是一種名為 Linux 的作業系統。這是一種自由且開放原始碼的類 UNIX 作業系統，同時也是不用購買就可以使用的作業系統。若是熟悉 UNIX 指令集在檔案管理上一定會比其他方式方便許多。若是沒有用過 Linux 作業系統，在考試的當下可能沒辦法順暢的使用電腦，甚至不知道該怎麼操作。若是想要體驗或是使用，可以試試看[將 Linux 裝在虛擬作業系統上](https://apcs.csie.ntnu.edu.tw/index.php/info/environment/)。

3. **找到適當的自學方式**

每個人習慣的學習方式不盡相同，大多數人都習慣藉由聽課(+筆記)的方式學習東西，而有些人也習慣用閱讀文章或課本的方式學習。而在現在 2021 年，各種地方都有不同的優質學習資源可以選擇。不管是影片還是文章，在學習語法的範圍都可以照自己習慣的方式學習。但在學習的後期（也就是學習演算法）會比較推薦用像是讀教科書的方式認真讀文章。

4. **使用線上評測系統解題**

在後期為了要測試自己是不是真的學會，我們會利用線上評測系統 (Online Judge. OJ) 來測試自己寫的程式是否正確。目前在台灣最大宗的 OJ 是 高中生程式解題系統([zerojudge.tw](zerojudge.tw))，若沒有其他推薦可以優先考慮試試看，在上面同時也有學長姐合力完成的 APCS 實作考古題可以練習。

5. **學會如何搜尋解決方法**

當遇到大大小小的問題時，我們總是會利用各種搜尋引擎尋找解答，因此非常建議學會進階搜尋語法。事實上在寫程式的時候，若不是在寫程式，大部分的時間都會在網路上遊走，能夠提高不少效率。此外英文的資源也遠比中文資源豐富，習慣閱讀英文也是很重要的（但和學校的英文扯不太上關係QQ）。

-----

自學程式在現今變得越來越簡單，但學習動機總是太容易失去而散慢。或許除了上面的五點外，也可以適時設大小里程碑給自己會更容易學習。根據 [emanlaicepsa](https://emanlaicepsa.github.io) 的文章內所述，要從頭到 APCS 實作五級分只需要花費 125 小時即可，或許你學習的時間能夠比我短上許多喔。

### Day 9 如何消滅/駕馭臭蟲

不管在哪個階段，在寫程式時總是會遇到大大小小的問題，不是程式不照著你的想法走，就是他連動都不想動。在今天我想要分享幾個辦法讓各位遇到臭蟲時要如何解決，以及要如何減少臭蟲出現的機會。

1. 黃色小鴨除錯法 (Rubber Duck Debugging)

小時候我寫專題用的程式時，Debug 的時間總是比寫出來的時間長，因此我常常在爸爸回家的時候拿電腦去問他。很好笑的事，幾乎每次拿去問時，都是我講到一半就發現自己錯在哪裡，又自己一個人躲回房間，殊不知他完全沒有在聽 ~~(不要打我)~~。而某天之後他半開玩笑的拿了一隻 Yahoo! 的紫色鴨鴨給我，和我說只要遇到問題可以講給他聽。~~之後就被我丟到浴室了~~


以上都是真人真事，但我那時候還不知道真的有人為這種除錯的方法命名，而且還真的叫做[黃色小鴨除錯法](https://zh.wikipedia.org/wiki/%E5%B0%8F%E9%BB%84%E9%B8%AD%E8%B0%83%E8%AF%95%E6%B3%95)。這不但是最簡潔有力，不需要任何工具，且可以在任何時候在腦袋思考的除錯法，也是個人認為效率最高的除錯法，多多做這種練習能夠讓程式組織能力加強許多。

2. Print 大法

當黃色小鴨法也沒有用，或是腦袋已經撐不住時可以嘗試直接把有疑慮的地方印出來，使用正確的測試資料，再這樣的方式一定會找到問題的根源。在眾多編輯器中也有偵錯器能夠一步一步印出程式運行的步驟，在各種 C++ 的 IDE (APCS 內裝的) 也都有支援，若有需要也可以學習怎麼使用偵錯器，但同時也不要因為過於方便而太依賴它，有時反而會沒辦法將問題聚焦導致更難找到問題。

3. 善用 const

變數有很多不同的功用，而在不同程式語言中也會有不同的修飾方法讓每個變數的定位更明顯。而在 C 語言中的 const 則是有防止傳遞的函數參數不被修改的功用。不僅是變數，函式也可以用 const 去不讓此函式有改到任何變數的可能性，如此一來一遇到變數上的問題，本應該從頭到尾看一遍的程式就會變得簡單很多。

4. 排版很重要

排版就像是剛學寫字的小孩一樣，是在初學程式時很常遇到的問題之一。若是沒有良好的排版習慣，不僅別人在看程式時會耗費很多時間在本不需要浪費的時間上外，自己也很容易被自己~~潦草~~的程式搞得團團轉。雖然至今仍然有許多人對排版的最佳方法爭論至今，但寫出乾淨且易讀的程式前，學習利用排版增加可讀性是必要的。

6. 有意義的命名變數

在許多程式競賽中，題目就會將預設的變數取為 a, b, N, M, K 等單一字母，雖然這部分是題目定好的，但在自己創造變數時要注意不要變數無意義的取名。不僅影響可讀性（別人會看不出在做什麼）外，這些無厘頭的命名方式也會讓自己的腦袋中裝一些本來不需要裝的東西，導致思考速度下降。

-----

在進階的程式設計中，還有很多技巧能夠讓錯誤出現的頻率降低，像是不要同時存在多個可修改的 pointer 指向同個位置或是 self explanation 和 function 不要寫太大等等 (感謝隊友 [bogay](https://ithelp.ithome.com.tw/users/20141989/ironman/4830), [JacobLinCool](https://ithelp.ithome.com.tw/users/20141410/ironman/4827) 補充)，都會在程式實戰中慢慢體會到並吸收，若是沒有嘗試過以上的方法，的不妨試試看適不適合自己喔。

### Day 10 手把手帶你從OJ練題 (Zero Judge)

相信很多新手在第一次聽到老手建議去不同的線上評測平台「刷題目」時，總會一頭霧水的不知道要怎麼練習，因此想各位展示要如何從 0 到 1 在 Online Judge 上寫出第一個題目！

本來想要用在ZeroJudge的第一個題目當作示範，但想到本系列文章是 APCS，因此題目決定是目前在 ZeroJudge 公布的最後一次實作題的第一題「[g275: 1. 七言對聯](https://zerojudge.tw/ShowProblem?problemid=g275)」。(感謝 [cthbst](https://zerojudge.tw/UserStatistic?id=19791) 提供測試資料及上傳 ZOJ)


1. 先讀懂題目

每一個題目基本上會有「題目敘述」、「輸入輸出說明」、「範例測試資料」及「配分機制」四大部分，但當看到任何一個題目時，不要先看輸入或輸出，雖然可以藉由輸入輸出猜出原題目的題意，但不要本末倒置變成會錯題意的窘境。

> **題目敘述**
> 中文依照發音方式可以分為平聲與仄聲，假設我們把平聲標記為 0 而仄聲標記為 1
> 一個七言對聯包含兩個句子，每個句子包含恰好七個字
>
> 七言對聯有三個限制：
> A: 二四不同二六同：每一句第二、四個字必須不同平仄，而第二、六個字必須相同平仄
> B: 仄起平收：第一句的結尾必須為仄聲，第二句的結尾必須為平聲
> C: 上下相對：第一、二句的第二、四、六個字平仄必須不同
>
> 給你 n 組對聯，分別用0, 1 代表平仄，請輸出它違反了哪幾條規則
> 若以上規則皆無違反，請輸出None

~~是個只要有國文平仄基礎就能懂的題目呢~~

2. 確認輸入輸出

在輸入及輸出部分，不同題目會有不同的形態，有時需要特別注意。在這題的輸入輸出都很容易理解，若有解釋不清楚的部分可以參考題目給的範例輸入/輸出。

> **輸入說明**
> 輸入一個正整數 n (1≤n≤30) 代表對聯數量，接下來有 2n 行，每行有 7 個數字，數字不是 0 就是 1

> **輸出說明**
> 對於每個對聯，輸出一行表示它違反了哪些規則，若三個規則都遵守則輸出 None

3. 透過給分機制當作參考想出解法

在比較困難的題目中，題目會給出一些
因為本題沒有任何的給分機制，所以沒有任何的參考。但因為這題的解法夠直覺也夠簡單，因此只需要照著題目實作，分別判斷 ABC 三個條件，在全符合的時候輸出 ```None```，而當有任何一個部分不符合時則是印出不符合的字母（記得每做一次都要換行）。

4. 準備好寫程式的環境(IDE, 編輯器+編譯器...)

雖然我現在的電腦沒有裝任何 Linux 的虛擬機器，如果想要熟悉考試環境的話建議還是建議多使用熟悉喔。我自己的開發環境比較習慣使用 Terminal，而編輯器則是 vim 和 VSCode 為主。~~秀出桌面好害羞(/////~~


5. 解題！

在確定是否合法的部分，我分別寫了三個不同函式去判定 ABC 分別是否合法。

bool isA(const int c[2][7]) {
	for(int i = 0; i < 2; ++i)
		if(c[i][1] == c[i][3] || c[i][1] != c[i][5]) return false;
	return true;
}

bool isB(const int c[2][7]){
	return (c[0][6] == 1 && c[1][6] == 0);
}

bool isC(const int c[2][7]){
	for(int i = 1; i <= 5; i += 2)
		if(c[0][i] == c[1][i]) return false;
	return true;
}

在主程式的部分則是依照提議創出能夠容納兩個平仄的二維 int 矩陣 (也可以用bool)，並創造出三個 bool 分別儲存三個規定的合法性，再依照題意輸出，最後整個程式再用輸入筆數 (n) 包起來。

int main(){
	int n;
	cin >> n;
	while(n--){
		int couplet[2][7];
		for(int i = 0; i < 2; ++i)
			for(int j = 0; j < 7; ++j)
				cin >> couplet[i][j];
		bool a = isA(couplet), b = isB(couplet), c = isC(couplet);
		if(a && b && c)
			cout << "None\n";
		else
			cout << (a?"":"A") << (b?"":"B") << (c?"":"C") << "\n";
	}

	return 0;
}

6. 利用測試資料測試 & 繳交

除了題目給的測試資料外，也要根據題目給的範圍創造出有可能會需要檢查的測試資料。

SkyHong$ ./deafult.out
2
0 1 1 0 0 0 1
1 0 1 1 0 1 1
0 1 0 0 0 0 1
0 0 0 0 0 1 1

AB
ABC

確定沒錯後上傳到 Zero Judge，最後 Accept 了！


-----

當題目寫完後，可以把自己寫的程式整理起來，或是可以放在自己的部落格，再放上寫題目時遇到的瓶頸、學到的東西和要注意的地方。當寫題目的量一點一點的變多時，成就感也會越來越高，也會越來越有自信喔！加油！