---
title: APCS 大學程式能力檢定考前衝刺
---
<center>

# **APCS 大學程式能力檢定考前衝刺**

</center>

<br>
<p style="text-align: right">
"如你根本並無招式，<br>
敵人如何來破你的招式？"<br>-- <a href = "https://zh.wikipedia.org/zh-tw/風清揚">風清揚</a><br>笑傲江湖第十回傳劍
</p>
<p style="text-align: right">
''Why do we fall sir?<br>So that we can learn to pick ourselves up.''<br>-- Alfred Pennyworth<br><a href = "https://www.imdb.com/title/tt0372784/">Batman Begins</a> (2005)
</p>

## 課前訊息

### 主講者
- 盧政良 (Zheng-Liang Lu, Arthur)
- 電子信箱：[e-mail]

### 預備知識
- 具備基本程式語言能力，如：迴圈 (循環)、陣列、遞迴等。
- 可參考我其他的課程內容：[APCS Python 101](https://hackmd.io/@arthurzllu/HJNXq84SO)、[APCS: C++ Programming](https://www.csie.ntu.edu.tw/~d00922011/cpp.html)、[Java Programming](https://www.csie.ntu.edu.tw/~d00922011/java.html)。
- [資訊科學的高中數學](https://hackmd.io/@arthurzllu/r1yS6hxqc)
- 由於 APCS 考試中觀念題以 C 語言出題，故在應考前務必了解 [APCS 考試指定程式語言對照表](https://hackmd.io/@arthurzllu/HJEpmDdt2)。

### 工作環境
- [建置虛擬主機練習環境之說明文件](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2019/08/APCS_practice.pdf)
- [下載 VirtualBox](https://www.virtualbox.org/wiki/Downloads)
- [下載官方指定環境 iso](https://drive.google.com/uc?id=1uQrzIYiW0GA9ZwHY_Rrnqp9qKzV4Eewd&export=download)

<center><img src = "https://hackmd.io/_uploads/Bkmzns0q3.png" width = 400px/></center>

### 電子郵件通訊禮節
- 電子郵件的標題 (Title) 需要註明**班別**與**中文姓名**，並加上**信件主旨**，如：APCS-nnn 金城武 作業繳交。
- 利用電子郵件提問時，務必提供完整的訊息，諸如：問題敘述、曾經嘗試但是失敗的方案、可能的猜想等等。任何有助於了解問題的材料皆可附上，如程式碼、錯誤訊息的截圖。

### 常用指令

    # C 的編譯指令
    gcc -g -O2 -std=gnu99 -static -lm -o a.out <your_source_code>
    # C 的執行指令
    ./a.out
    
    # C++ 的編譯指令
    g++ -g -O2 -std=gnu++11 -static -lm -o a.out <your_source_code>
    # C++ 的執行指令
    ./a.out
    
    # Java 的編譯指令
    javac <your_source_code>
    # Java 的執行指令
    java -client -Xss8m -Xmx1024m <basename_of_source_code>
    
    # Python 的編譯指令
    python3 a.py

### 課程錄影
- 本課程除非經授課老師同意，學生<b><font color = "red">不</font></b>得擅自進行課程錄音與錄影。

## 課程架構

<!-- ### 時間表
 -->

- 課前問卷：https://forms.gle/WmRrsxHwn5f62JM8A
- 課程投影片：TBA
- APCS 官方範例題：https://apcs.csie.ntnu.edu.tw/index.php/questionstypes/previousexam/
- 考試形式與時程：https://apcs.csie.ntnu.edu.tw/index.php/info/
- 可能會用到的範例程式：https://ideone.com/arthurzllu/niu-sample-codes

### 流程控制 (Flow Controls)
- 有條件的敘述 (conditional statements) / 分支 (branching)
- if-else if-else
- switch-case-default
- 迴圈 (loops)
- while / do-while loops
- for loops
- 多層迴圈的結構
- 演算法分析 (analysis of algorithms)
- [隨堂測驗](https://forms.gle/m1McXKt6j1R55AKCA)

### 陣列 (Arrays)
- 基本語法
- 陣列的第一個元素為何從 0 開始? 這得從記憶體 (memory) 配置說起
- 二維陣列
- 動態配置與堆積 (heap)
- 指標 (pointer) 與陣列

### 函式與遞迴 (Functions and Recursion)
- 函式定義
- 函式堆疊 (function stack)
- http://www.pythontutor.com/visualize.html
- 遞迴演算法 (recursive algorithms)

### 常見的演算法與工具
- 好用的標頭檔：bits/stdc++.h
- 詳細的引用清單：https://gcc.gnu.org/onlinedocs/gcc-4.8.5/libstdc++/api/a01235_source.html

...
#include <bits/stdc++.h>
...

- 排序 (sort)
- 二元搜尋法 (binary search)
- 前綴和 (prefix sum)
- 二元樹 (binary tree) 的走訪 (traversal) <font size = -1>[pdf](https://algs4.cs.princeton.edu/lectures/keynote/32BinarySearchTrees.pdf)</font>
- 在[無向圖](https://algs4.cs.princeton.edu/lectures/keynote/41UndirectedGraphs.pdf)與[有向圖](https://algs4.cs.princeton.edu/lectures/keynote/42DirectedGraphs.pdf)上做搜尋
- 深度優先搜尋演算法 (DFS)
- 寬度優先搜尋演算法 (BFS)
- 動態規劃 (dynamic programming, DP) <font size = -1>[pdf](https://www.csie.ntu.edu.tw/~yvchen/f107-ada/doc/181011_DynamicProgramming2.pdf)</font>
- 貪心演算法 (greedy algorithms) <font size = -1>[pdf](https://www.csie.ntu.edu.tw/~yvchen/f107-ada/doc/181018_Greedy1.pdf)</font>

## 補充材料

### 書籍
- 劉邦鋒，[由重構學習 C++ 程式設計](https://gpi.culture.tw/books/1011200237)，2023
- 劉邦鋒，[由片語學習 C 程式設計](https://sites.google.com/view/c-programming-2ed/home)，2019
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, [Introduction to Algorithms](https://a.co/d/cIL3YvL), 4/e, 2022
- Robert Sedgewick and Kevin Wayne, <a href = "https://algs4.cs.princeton.edu/lectures/">Algorithms</a>, 4/e, 2011

### Standard Template Library (STL)
- Arthur O'Dwyer, [Mastering the C++17 STL: Make full use of the standard library components in C++17](https://www.amazon.com/Mastering-17-STL-standard-components/dp/178712682X), 2017

### 大學課程
- Jim Huang, [「你所不知道的 C 語言」系列講座](https://hackmd.io/@sysprog/HJpiYaZfl), Department of Computer Science and Information Engineering, National Cheng Kung University
- Zheng-Liang Lu, [Algorithms Lab](https://hackmd.io/@arthurzllu/SkZBc7GoI), Department of Computer Science and Information Engineering, National Taiwan University

### 教學平台 / 題庫
- 吳邦一 (Bangye Wu), [FB社團：APCS實作題檢測](https://www.facebook.com/groups/359446638362710)
- [影片解說](https://www.youtube.com/playlist?list=PLpmg1QLbgMuRQXHRkX9iDHyAVIW1D6OJF)、[講義分享](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m?fbclid=IwAR0c68kZKUqUvBVNTUCK4rBLRZNYzo5OUknK33Jujc7baGnJ5YaD9TX5HnU)
- 高中生程式解題系統：https://zerojudge.tw/
- 可以利用搜尋關鍵字 APCS 找到 2016 年以來的歷屆試題。
- 1 到 3 級分題目清單：https://docs.google.com/spreadsheets/d/1m3PsJACKsJfFxSsRz2xE5zsaqTc6iBwp6l2Ml0tokBc/edit?usp=sharing
- LeetCode: https://leetcode.com/
- CodeWars: https://www.codewars.com/

### 跟課堂有關的電影/影集
- [Imitation Game (2014)](https://www.imdb.com/title/tt2084970/)
- [DeepMind: AlphaGo (2017)](https://www.imdb.com/title/tt6700846/)
- New Mind, [Computing Technology](https://youtube.com/playlist?list=PLC7a8fNahjQ8IkiD5f7blIYrro9oeIfJU), 2023

### 與程式設計相關的遊戲
- [Human Resource Machine](https://store.steampowered.com/app/375820/Human_Resource_Machine/)
- [7 Billion Humans](https://store.steampowered.com/app/792100/7_Billion_Humans/)
- [Turing Complete](https://store.steampowered.com/app/1444480/Turing_Complete/)
- [while True: learn()](https://store.steampowered.com/app/619150/while_True_learn/)
- [A=B](https://store.steampowered.com/app/1720850/AB/)
- [Virtual Circuit Board](https://store.steampowered.com/app/1885690/Virtual_Circuit_Board/)