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

"如你根本並無招式，
敵人如何來破你的招式？"
-- 風清揚
笑傲江湖第十回傳劍

''Why do we fall sir?
So that we can learn to pick ourselves up.''
-- Alfred Pennyworth
Batman Begins (2005)

課前訊息

主講者

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

預備知識

• 具備基本程式語言能力，如：迴圈 (循環)、陣列、遞迴等。
  • 可參考我其他的課程內容：APCS Python 101、APCS: C++ Programming、Java Programming。
• 資訊科學的高中數學
• 由於 APCS 考試中觀念題以 C 語言出題，故在應考前務必了解 APCS 考試指定程式語言對照表。 2025-03-31 公告未來觀念題的出題可選擇 C, C++ 和 Python 三種不同語言的題目，詳見官方公告。

工作環境

• 建置虛擬主機練習環境之說明文件
  • 下載 VirtualBox
  • 下載官方指定環境 iso

電子郵件通訊禮節

• 電子郵件的標題 (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

課程錄影

• 本課程除非經授課老師同意，學生不得擅自進行課程錄音與錄影。

課程架構

• 課前問卷：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)
  • 隨堂測驗

陣列 (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) pdf
• 在無向圖與有向圖上做搜尋
  • 深度優先搜尋演算法 (DFS)
  • 寬度優先搜尋演算法 (BFS)
• 動態規劃 (dynamic programming, DP) pdf
• 貪心演算法 (greedy algorithms) pdf

補充材料

書籍

• 劉邦鋒，由重構學習 C++ 程式設計，2023
  
• 劉邦鋒，由片語學習 C 程式設計，2019
  
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4/e, 2022
  
• Robert Sedgewick and Kevin Wayne, Algorithms, 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, 2017
  

大學課程

• Jim Huang, 「你所不知道的 C 語言」系列講座, Department of Computer Science and Information Engineering, National Cheng Kung University
• Zheng-Liang Lu, Algorithms Lab, Department of Computer Science and Information Engineering, National Taiwan University

教學平台 / 題庫

• 吳邦一 (Bangye Wu), FB社團：APCS實作題檢測
  • 影片解說、講義分享
• 高中生程式解題系統：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)
  
  
• DeepMind: AlphaGo (2017)
  
  
• New Mind, Computing Technology, 2023
  

與程式設計相關的遊戲

• Human Resource Machine
  
  
• 7 Billion Humans
  
  
• Turing Complete
  
  
• while True: learn()
  
  
• A=B
  
  
• Virtual Circuit Board