主旨:希望能幫助到大家在APCS中取得好成績
編者:高雄中學程式設計社 J.T.
本講義參照:https://github.com/sparanoid/chinese-copywriting-guidelines
APCS為Advanced Placement Computer Science的英文縮寫,是指「大學程式設計先修檢測」。其檢測模式乃參考美國大學先修課程(Advanced Placement,AP),與各大學合作命題,並確定檢定用題目經過信效度考驗,以確保檢定結果之公信力。
APCS成績除了是申請入學APCS組必要成績外,也是多校特殊選才等多元入學管道重要參考資料。APCS檢測每年舉辦三次,檢測日程預訂在1月、6月及10月,實際日期以公告為準。
其中測驗分為觀念題及實作題,公布成績時會有原始分數跟級分數(一至五級分)。
1.程式設計觀念題:為選擇題測驗,總共包含50道試題,並且藉由試題區塊配置成兩份測驗題本,每份測驗題本共有25道試題。
2.程式設計實作題:為非選擇題測驗,總共包含4個題組試題,每個題組各有10-20組測試資料
https://apcs.csie.ntnu.edu.tw/index.php/apcs-introduction/
1.保送TOI初選:APCS實作三級分以上,可跳過TOI海選,直接進入初選。
2.檢測自己學習狀況,APCS難度適中,是很好的檢測項目。
3.大學端採計
複習所學過的基礎知識,就這樣,沒了…
1.單向選擇結構 if statement
若符合條件,則執行敘述。
2.雙向選擇結構 if…else statement
若符合條件,則執行敘述1,若不符合,則執行敘述2。
3.多向選擇結構 if…else if…else statement
若符合條件1,則執行敘述1,若不符合條件1,則檢查條件2,若符合,則執行敘述2,以此類推。
4.多向選擇結構 switch case
"case:"後接敘述。
*如果用switch,不加break的話就無法跳脫程式,要多注意。
條件運算子 ? : (也稱為三元運算子)
會評估布林運算式,並根據布林運算式是否評估為"或"
傳回兩個運算式其中之一的結果 true / false
啊也可以推廣成多向選擇結構窩~
1.while迴圈 while loop
若符合條件,執行括號中程式碼
最好設定終止條件(條件式中設定或是用break)
2.for迴圈 for loop
第一項是初始設定,第二項是條件,第三項是更新。
初始設定只進行一次(也可不設定),接著丟入條件判斷,若符合,在執行完敘述後再進行更新,更新後再丟回條件判斷。
注意:要用分號區隔
對於一個有範圍的集合而言,如果再去說明迴圈的範圍,就很多此一舉
所以,C++11中引入了基於範圍的for迴圈。
for迴圈後的括號由冒號“:”分為兩部分:
編譯器選項要至少C11以上窩(默認是C98啦)
-std=c++11
-std=c++14
-std=c++17
1.陣列 array
陣列是從"0"開始存取,舉以下為例,格子為0~9,共10格。
除了平常的一維陣列,也可以開二維甚至三維的多維陣列
以下為初始化的參考寫法:
1.zerojudge a.005
https://zerojudge.tw/ShowProblem?problemid=a005
2.zerojudge a.024
https://zerojudge.tw/ShowProblem?problemid=a024
3.zerojudge a.053
https://zerojudge.tw/ShowProblem?problemid=a053
取址符號 &
指派運算子 =
提領運算子 *
請設計一個函式使a,b兩數互換。
這樣對嗎?
奇怪明明swap就進行交換了啊,怎麼輸出會不變?
這時就要談到我們的取址符號及提領運算子了!
取址符號(&
):存取該變數的記憶體位址(address)。
提領運算子(*
):取該記憶體位址的值。
以分房間為例,假設101號房內有一名男性。
若不加符號直接複製主函式變數的值後傳遞,那副函式的變數值就是「男」。(傳值 pass by value)
若使用取址符號及提領運算子,則&
儲存到的是"101",*
則是找到在房間裡的人。(傳址 pass by address)
拿以上的寫法做例子、副函式取 x, y 時是「傳值」,不會影響本來 a, b 的值。
此時,要利用取址符號及提領運算子做「傳址」,是直接修改記憶體空間。
那剛才的程式碼應該怎麼改呢?
若如上述以int *x來做宣告,則此時作為指標宣告(pointer)。
上述兩者可用於int, float, double等資料型態。
提醒:
swap有在algorithm的內建函式庫裡,直接用就好,沒事不要自己寫。
就是你我熟知的=
指派運算子(=
):要相同型態才能指派(int=int,float=float,…)
運算子(+
,-
):
可以對地址增減一個整數
addr±i意思是增加/減少i個單位的資料型態。
運算子([]
):
arr[i]等同於*(arr+i)。
當我們把陣列當成數值,做賦值當我們把陣列當成數值,做賦值、運算、比較關係等運算時,其實隱含了陣列和指標的轉換。
設定空指標可以用:
在C/C++裡我們會傳遞陣列的起始位置到函式裡
備註:如果真的有需要,也可直接開全域數陣列,就不用一直傳來傳去。
其實常用的內建sort及reverse(標頭檔須包含algorithm)都有用到指標的概念歐。
sort(array_begin,array_end,tmp);
範例:
reverse(array_begin,array_end);
範例:
其中的(arr,arr+n);就是利用指標的概念讀取陣列的記憶體位址後作加減平移。
因為之前已提過多維陣列,此處就簡略帶過
其實多維陣列的概念很簡單,舉二維陣列而言,上述arr2[10][10]可視為是10個10格的陣列。
一個char變數就是儲存ASCII碼裡的一個整數編號(0~127)<其中分成可顯示以及不可顯示兩類
(1)半形字(可顯示):
ASCII編碼中的32~126是可顯示的半形字,在C++中以char輸出就會輸出半形字。
(2)控制字元(不可顯示):
編號0~31、127一個整數編號會對應到一個控制字元,例如:0對應到"\0"代表空字元"NULL",10對應到"\n"代表換行字元(ENTER)。
注意:當輸入文字含有空格時,會視為輸入結束,若要包含輸入包含空格的句子,可使用cin.getline(chartype,streamsize),還要注意的一點是使用cin.getline時必須多開一格,最後一格是"\0"代表輸入結束。
string是一種很方便的變數類型,可以用string建立一個字元陣列,不同於char的是string不用估算字元數量,但是跟char一樣的問題是遇到"\0"會視為輸入結束,所以當我們需要儲存含有空格的字串時可以使用getline(cin,stringtype)來儲存。
以下範例會以儲存考試成績來說明,以下為範例:
A班有三位學生,座號1~3分別是Amy,Ben,Carol,某次考試考了三科,分別是國文、數學及英文,讓我們試著用結構來記錄他們的考試成績吧!
注意:使用struct宣告時一定要在大括號後加;
才能宣告
以下為完整原始碼
input:
Amy 50 60 70
Ben 90 95 100
Carol 40 35 30
output:
1.Amy:50,60,70
2.Ben:90,95,100
3.Carol:40,35,30
如果想知道一個字的ASCII碼可以用(int)來轉換,反之,如果想知道一個數字對應的文字也可以用(char)轉換,範例如下:
1.zerojudge a.009
https://zerojudge.tw/ShowProblem?problemid=a009
2.zerojudge a.022
https://zerojudge.tw/ShowProblem?problemid=a022
3.自己寫一個ROT13解碼器
About ROT13:https://zh.wikipedia.org/wiki/ROT13
4.zerojudge d.091
https://zerojudge.tw/ShowProblem?problemid=d091
漸進符號 (big o):
大O符號在分析演算法效率的時候非常有用,若假設現有一個規模為的問題需要花費時間如以下函式:
則我們可以說
或
因為在n值夠大時,最高次項對數值的影響遠超過其他各項,故可忽略其他項。
而漸進符號可以幫助我們估算程式執行時的複雜度(空間及時間複雜度)。
空間複雜度(Space Complexity):
簡單的來說就是,電腦執行演算法所需要耗費的空間記憶體。
舉以下兩段程式碼為例:
不管n值為多少都不會影響記憶體空間,此時空間複雜度為。
n值的大小會影響到記憶體空間,此時空間複雜度為。
時間複雜度(Time complexity):
時間複雜度描述該演算法的執行時間,以下範例:
該範例為一迴圈,時間複雜度為。
該範例為雙重迴圈,時間複雜度為。
以下為一段二分搜尋的程式碼,在後面幾章會再做詳細介紹,此處因為二分搜尋的概念就是每次折半搜尋所以時間複雜度為。
經由上述3-2及3-3的內容,其實不難發現,有時候時間複雜度跟空間複雜可以互相轉換,但並非每次都可以,以上述二分搜尋為例,時間複雜度為,但是空間複雜度為。若以APCS及程式競賽為例,往往是比較在乎時間複雜度,因為如果時間複雜度太大可能造成TLE(執行時間過長)。基本上空間是不太會超過題目限制,除非是開了過大的陣列或是忘記歸還記憶體。
函式的用處就是在我們重複執行某項指令時非常好用的東西,或是將常用到的指令做成函式,下次就可以直接使用。
以下舉一些常見函式,例如:
sort(),reverse(),max(),min(),find(),swap()…(存放在algorithm函式庫中)
pow(),sqrt(),rand(),time()…(存放在cmath函式庫中)
在使用前須包含對應的標頭檔,但是要去記個別函式對應到的函式庫是一件很麻煩的事,所以也可以直接使用我們的「萬能標頭檔」。
通常主流的OJ都是支持的,例如:ZeroJudge,Codeforces…
但是還是有一些OJ例如:Greenjudge是不支持的喔。
其中還有要注意的一點是,因為萬能標頭檔包含很多函式庫,所以編譯時間會比較長!
當然,內建函式不一定能滿足所有狀況,有的時候可能要自己刻一個自訂函式,而自訂函式也分為回傳值跟不回傳值,而傳值的函式也分為各種變數型態,例如:bool,int,long long…
函式還有其他各種好處:
注意:函式一旦執行到return,就會立刻回傳,略過之後所有程式碼。
其中傳值的函式有一項重要的應用就是遞迴,以下舉費氏數列作為例子:
1.zerojudge a.044
https://zerojudge.tw/ShowProblem?problemid=a044
先備知識:什麼是STL
STL就是標準模板庫(Standard Template Library),是一個C++軟體庫,裡面存放了很多常用的東西,其中包含4個組件,分別為演算法、容器、函式、疊代器。
詳見:STL
vector可以視為一個動態陣列,有以下幾個常用基本功能:
函式 | 功能 |
---|---|
size | 回傳向量(vector)內元素的數量 |
front | 取得向量(vector)中的第一個元素 |
back | 取得向量(vector)中的最後一個元素 |
push_back | 從向量(vector)後端推入元素 |
pop_back | 從向量(vector)後端移除元素 |
insert | 從指定位子插入元素 |
erase | 從指定位子移除元素 |
clear | 清空向量(vector) |
以下範例: |
1.優點
2.缺點
stack是一種先進後出 FILO(First In, Last Out)的資料結構,就像是堆東西一樣,由下往上堆,要拿取時只能從上往下拿。
堆疊(stack)有以下幾個常用基本功能:
函式 | 功能 |
---|---|
top | 回傳堆疊(stack)頂端的元素 |
push | 加入一個元素到堆疊(stack)裡 |
pop | 從堆疊(stack)頂端移除元素 |
以下範例: |
1.優點:
2.缺點:
queue是一種先進先出 FIFO(First In, First Out)的資料結構,就像排隊一樣,先排隊的就先出去。
堆疊(stack)有以下幾個常用基本功能:
函式 | 功能 |
---|---|
front | 取得佇列(queue)中的第一個元素 |
back | 取得佇列(queue)中的最後一個元素 |
push | 從佇列(queue)後端推入元素 |
pop | 從佇列(queue)前端移除元素 |
以下範例: |
1.優點
2.缺點
本章會簡單敘述關於樹狀結構的概念以及樹狀結構的應用。
一、關於樹的名詞介紹:
二、以下為樹的定義:
如同上面所述,二元樹的定義就是所有子樹的子節點都不超過2,完美二元樹的定義就是每個階層都被填滿,現在假設有一深度為的完美二元樹,則會有以下性質:
每個節點有0或2個子節點。也稱作嚴格二元樹、正規二元樹。
最後一階層之外的階層都必須填滿,而最後一階層的節點必須由左至右填入。
都所有節點都只有同一邊的子節點的時候,就稱為歪斜二元樹。
二元搜尋樹又稱有序二元樹或排序二元樹,在各種資料結構中的優勢就是它在尋找或是插入時的時間複雜度較低,為,那什麼是二元搜尋樹呢?
二元搜尋樹具有以下性質:
將第一個值作為根節點,接下來輸入的值大於根節點則進入右子樹,反之則進入左子樹,重複進行這個步驟就可以得到二元搜尋樹。