APCS 筆記 - HackMD

# APCS 筆記 這裡幫你們分幾個部分複習，因為是筆記，所以內容幾乎只講重點，如果有問題就馬上問我，自己google也行，**除了演算法和及資料結構的部分，其他的幾個你們都要很熟**，如果我用紅色字的部分是一定要知道的觀念，不能不知道。 ## 目錄 [TOC] ## 電腦科學基礎概念 * **電腦基礎運作原理** :::info **中央處理器(CPU**)：真正的大腦，所有的運算都透過它 **硬碟(ROM)**：資料真正儲存的地方，當你重新開機後資料還會存在。 **記憶體(RAM)**：資料暫存的地方，如果你沒儲存，關機後這存在這裡的資料就會被清除 ::: 假設你正在打做一份PowerPoint報告，你多增加了兩頁但你還沒按儲存時，此時這兩頁的資料就是存在RAM中的，所以一旦你沒有儲存就關掉，此時你RAM就會把你這兩頁給清除掉，但是當你按下儲存按鍵後，電腦就會把存在RAM中的資料寫入到ROM，達到真正保存的效果。 `(但是現在的程式都很聰明會自動幫你儲存，所以這種現象只有在以前比較容易看到) ` ~~`(你們也可以自己試看看不要儲存直接關機) `~~ > *那為何不直接存到ROM，還要裡要透過RAM呢?* > > 因為以前的電腦如果真的做儲存的動作，是很耗時間的，如果每次的修改都要存，如果一直存存改改的太沒效率了，所以如果有RAM先幫忙存，等到確定要保存下來的時候在寫入到ROM中，ROM的負擔就不會那麼大了 * **二進制與0,1** > 所有的電子設備中，每一個動作都是在做運算(就連滑鼠移動一下，電腦也要運算出現在滑鼠的位置座標，然後更新到你的螢幕，讓你看起來滑鼠像是移動了)，而且都是使用0與1做運算的。電腦也只看得懂二進制，但是人類習慣看的是十進制的數字，所以要透過進制轉換來溝通。 > 在所有進制轉換的考題中，不管題目要什麼幾進制轉幾進制，一律都先轉成十進制，教學可以去看我的PPT裡面，[這裡](https://www.slideshare.net/ShawnWu37/binary-234608474)可以看，有問題問我！ ## C語言-基礎概念 :::info 1. 程式『一定』都是由上執行到下的。 2. 程式語言是用英文與符號組成，但電腦看不懂人類語言，所以需要透過『編譯器』把人類看的程式語言轉成電腦看得懂的機器語言。 3. main是程式的起點，只要main執行完程式就結束！，所以任何想要執行的程式或者函數，都必須要在main裡面在程式結束前執行到。 4. main本身是一個函數(function)，所以main也叫main函數(main function) 6. main可以調用函數，讓其他函數被使用到，但不等於可以把其他函數寫在main裡面(切記這很重要！) 7. 每一行程式碼都要加 ; 句點 8. 區域變數與全域變數的差異一定要弄清楚 ![](https://i.imgur.com/hExABrk.jpg) 9. **大括號{}一定要對應好。** ::: ## Ｃ語言-基礎語法 * **printf()**用來輸出內容到螢幕，方便人類查看 * **scanf()**用來輸入內容到程式裡，好讓程式接收我們給的資料去相關的運送，使用時給予想要讀入的資料格式與變數位址 ![](https://i.imgur.com/mvXIKxP.jpg) printf()和sacnf()格式化輸出輸入： | 符號 | 代表 | | -------- | -------- | | %d | 輸出輸入10進制整數 | | %c | 輸出輸入字元 | | %s | 輸出輸入字串 | | %f | 輸出輸入浮點數(小數點) | * 常用的資料型態 | 資料型別 | 使用名稱 | 範例 | | -------- | -------- | -------- | | 整數 | int | int a = 32 | | 字元 | char | cahr a = 'a' | | 單倍精準俘點數 | float | float a = 16.4 | | 雙倍精準俘點數 | double | double a =76.1 | float與double都可以使用在小數點的計算，雙倍比單倍能存更多的小數點後的位數 * **變數一定要先宣告才能用** ![](https://i.imgur.com/M9Cxrul.jpg) * 運算子與運算元 | 運算子 | 運算內容 | 範例 | 優先順序 | | -------- | -------- | -------- | -------- | |＋ | 將兩數相加 | a+b | 由左至右 | |- | 將兩數相減 | a-b | 由左至右 | |＊ | 將兩數相乘 | a＊b | 由左至右 | |/ | 將兩數相除 | a/b | 由左至右 | |％ | 將兩數相除求餘數 | a%b | 由左至右 | ## Ｃ語言-邏輯判斷式 * 為了應付「如果OOO成立」就要…，「否則」就要...的需求，C語言提供了if..else條件式，語法如下： if(條件式) { 陳述句; } else { 陳述句; } 條件式運算結果為true(1)的話會執行if的{}中的陳述句，否則執行else的{}中的陳述句，如果條件式不成立時並不想作任何事，則else可以省略。 **if裡面的條件式如果為0(false)就不執行，如果是1(true)或大於1，就會執行** * 關係運算子 | | 符號 | 範例 | | -------- | -------- | -------- | | 等於 | == | if(a == b) | | 不等於 | != | if(a != b) | | 小於 | < | if(a > b) | | 大於 | > | if(a < b) | | 大於等於 | >= | if(a >= b) | | 小於等於 | <= | if(a <= b) | **一個=是賦值，兩個= (==)是關係判斷** * 邏輯運算子 | 運算子 | 運算內容 | 範例 | 範例結果 | | -------- | -------- | -------- |--------| | && | and(而且) | 3>2 && 2<1 | 0 | | II | or(或者) | 3>2 II 2>1 | 1 | | ! | not(非) | !(3>2) | 0 | * 運算子優先順序 | 順序 | 運算子 | 算術類型 | 結合順序 | | --------| -------- | -------- |--------| | 1 | ! |邏輯運算|由右至左| | 2 | ＊ / ％ |算術運算|由左至右| | 3 | ＋ - |算術運算|由左至右| | 4 | > < >= <= |關係運算|由左至右| | 5 | != == |關係運算|由左至右| | 6 | && |邏輯運算|由左至右| | 7 | II |邏輯運算|由左至右| | 8 | ＝ |賦值運算|由右至左| ## Ｃ語言-迴圈loop :::info 有時候，我們需要讓電腦重複執行某些指令，直到條件成立為止，這種語法稱為迴圈。在 C 語言中的迴圈敘述有三種，分別是 for、while、do-while。 ::: * **while** while (條件式) { 程式碼一; 程式碼二; } 上面的語法是當條件式成立時，程式會重複執行程式碼一，程式碼二，直到條件式不成立時，所以在while迴圈裡，都會設一個停止的條件，例如下面例子中，當i>10時就會停止迴圈，而記得要再回圈內更新i，才能使迴圈停止 while(i<10){ printf("Hello\n"); i++; } * **do-while** do { 程式碼一; 程式碼二; } while (條件式); while與do-while從意義上來看它們兩者完全一樣，唯一的不同是， while是先檢查條件是否成立，成立才執行下面的指令，而do-while是不論條件是成不成立，都會先執行一次那些程式碼，再去檢查條件是否成立。 do{ printf("Hello\n"); i++; }while(i<10){ * **for** for (起始值; 條件式; 更新值) { 程式碼一; 程式碼二; } 起始值是進入迴圈一開始會執行的動作，而更新值則是執行完每次的迴圈要執行的動作，以下面例子為例，程式執行的步驟如下： 1.設定變數 i=1; 2.檢查 i<10 是否成立，不成立則跳出迴圈 3.執行 printf("這是第%d次迴圈\n",i); 4.執行 i++; ( 即 i=i+1; ) 5.回到第2點繼續執行 6.迴圈結束 for(int i = 0; i<10; i++){ printf("這是第%d次迴圈\n",i); } - **多重迴圈** 多重迴圈表示迴圈內還有其他迴圈，例如下面的例子，是利用兩個for構成了雙重迴圈，外迴圈利用變數i作為迴圈條件變數並0由到9，迴圈執行一次，則累增加，內迴圈的條件變數是j。也是迴圈執行一次，由0到9，每次累增加，然而，外迴圈執行一次，則內迴圈必須0由到9執行10次迴圈實體。 for(int i = 0; i<10; i++){ for(int j = 0; j<10; j++){ printf("這是外迴圈的第%d次，內迴圈的第%d次\n", i, j); } } ## Ｃ語言-函式function :::info 在先前的程式中，絕大部分的程式的程式碼全都寫在主函式(Main function中)裡，在規模短小的程式這樣子做並沒有什麼不好，但隨著程式規模成長，這種模式就漸漸行不通了。這時候，我們會利用函式將程式碼分離開來，使用函式有以下的好處： * 減少撰寫重覆的程式碼 * 將程式碼以有意義的方式組織起來 * 在相同的流程下，可藉由參數調整程式的行為 * 藉由函式庫可組織和分享程式碼 ::: * **宣告函式** 回傳的資料型別函式名稱(要傳入的參數型別要傳入的參數名稱){ /／程式碼 return value; } 主要分成幾個部分： * 函式的名稱 * 函式的參數，相當於輸入 * 函式的回傳值 (return value)，相當於輸出 * 函式的本體 (程式碼 ``` int getMaxNumber(int arrayName[], int length){ int maxNumber = 0; for(int i = 0; i < length; i++){ if(arrayName[i] > maxNumber){ maxNumber = arrayName[i]; } return maxNumber; } ``` 在上面的函式中，可以透過傳入一個陣列就幫我找到陣列中的最大值，當有需要找最大值時就呼叫這個函式，就不用再寫重複的程式碼了。 * **函式遞迴(Recursion)** 遞迴的定義:一個函式呼叫自己本身.至少要定義2種條件： * 什麼情況下作遞迴（呼叫自己） * 什麼情況下作遞迴結束下面的例子是階乘在程式碼的實現： ``` int recursion(int n){ if(n==1){ return 1; } else{ return n * recursion(n-1); } } ``` **if(n==1)這行就是終止遞迴的條件** 假設呼叫recursion(5)，則實際情況是 ![](https://i.imgur.com/keIelBO.png) ## Ｃ語言-第一個資料結構(陣列) :::info 陣列是一種結構性的資料儲存空間，同一陣列裡的資料型別都是相同的，元素與元素之間的記憶位置是相鄰的，通常我們利用一個變數來代表整體的資料，舉例而言，我們可以把陣列想成一排置物櫃，而陣列裡的變數代表放在置物櫃的東西數量，例如：置物櫃[20]，我們可以想成置物櫃總共有二十格，假如我們想要知道第三間置物櫃有多少東西，只要把置物櫃[2]的值取出，便可知道住在第三格置物櫃的東西數量。 **C語言的陣列索引一定是從0的開始的**。 ::: 根據陣列的結構而言，可以把陣列分為(1)一維陣列、(2)二維陣列、(3)多維陣列。表示方法如下： * 資料型態　陣列名稱[陣列大小]； * 資料型態　陣列名稱[陣列大小][陣列大小]; ``` int number[10]; // 宣告 10 個元素的整數陣列 double score[10]; // 宣告 10 個元素的浮點數陣列 char ascii[10]; // 宣告 10 個元素的字元陣列 ``` 宣告陣列之後，陣列的元素值是未初始的，若想在宣告時初始陣列全部的元素值，可以如下： ``` int number[10] = {0}; double score[10] = {0.0}; char ascii[10] = {'\0'}; bool flag[10] = {false}; ``` 也可以在宣告陣列時初始所有的陣列值，例如： ``` int number[5] = {0, 1, 2, 3, 4}; double score[5] = {87.0, 78.0, 99.5, 69.5, 82.5}; char ascii[5] = {'A', 'B', 'C', 'D', 'E'}; bool flag[5] = {false, true, false, true, false}; ``` 要存取陣列中的元素值時，可以使用[]符號加上索引值，索引值由0開始，例如： ``` int number[5] = {0, 1, 2, 3, 4}; int first = number[0]; ``` ## 其他資料結構 * ### 堆疊 (stack) :::info **堆疊是一種遵循後進先出（Last In First Out，LIFO）的有序集合。在堆疊的世界裡，由於遵守後進先出原則。** ::: 在生活中有許多使用堆疊的案例：自助餐店的盤子的擺放就是個例子，當你把盤子從盤堆最上面拿起來一個盤子是從最上面開始拿，若是要把盤子放回去，一定是放到最上面的(~~但是不否認會有白目也會想辦法放到最下面~~)，下一個人拿到的就是你剛剛放回去的盤子，以資料的角度來說，比較晚加入的資料會比較早被取走，這就是stack的精神。 ![](https://i.imgur.com/abdRQ12.png) 下面為程式碼例子： ``` const int MAXSTACK = 100; /*定義最大堆疊容量*/ int stack[MAXSTACK]; //堆疊的陣列宣告 int top=-1; //堆疊的頂端 int main(int argc, char *argv[]) { int value; int i; printf("請依序輸入10筆資料:\n"); for(i=0;i<10;i++){ scanf("%d",&value); push(value); } printf("====================\n"); while(!isEmpty()){ printf("堆疊彈出的順序為:%d\n",pop()); } pop(); return 0; } /*判斷是否為空堆疊*/ int isEmpty(){ if(top==-1){ return 1; }else{ return 0; } } /*將指定的資料存入堆疊*/ void push(int data){ if(top>=MAXSTACK){ printf("堆疊已滿,無法再加入\n"); }else{ top++; stack[top]=data; } } /*從堆疊取出資料*/ int pop(){ int data; if(isEmpty()){ printf("堆疊已空\n"); }else{ data=stack[top]; top--; return data; } } ``` 而從stack取資料就是執行堆疊的pop()函式，存入資料就是執行push(element)方法。 **可以想看看為何pop()沒有傳入參數而push()一定要有!?** (因為pop一定是從最上面開始取資料，所以不需要有傳入什麼參數告訴函式怎麼做) * ### 佇列 (queues) :::info **跟堆疊相反，佇列是遵循先進先出先進先出(First-In-First-Out, FIFO)的集合，顧名思義是一種像排隊一樣的概念，人們一個接一個的從隊伍後面加入排隊，越晚進入就越晚被處理** ::: 佇列就是排隊的概念，一模一樣，以資料的角度來說，比較早加入的資料會比較早被取走，這就是queues的精神。 ![](https://i.imgur.com/boAypqP.png) 下面為程式碼範例： ``` const int MAXSTACK = 100; //定義最大佇列容量 int stack[MAXSTACK]; //佇列的陣列宣告 int head= 0; //佇列的最前面 int tail = -1; //佇列的最面 //判斷是否為空佇列 int isEmpty(){ if(tail<head){ return 1; }else{ return 0; } } //將指定的資料存入佇列 void push(int data){ if(head>=MAXSTACK){ printf("佇列已滿,無法再加入\n"); }else{ tail++; stack[tail]=data; } } /*從佇列取出資料*/ int pop(){ int data; if(isEmpty()){ printf("佇列已空\n"); }else{ data=stack[head]; head++; return data; } } int main(int argc, char *argv[]) { int value; int i; printf("請依序輸入5筆資料:\n"); for(i=0;i<5;i++){ scanf("%d",&value); push(value); } printf("====================\n"); while(!isEmpty()){ printf("佇列彈出的順序為:%d\n",pop()); } pop(); return 0; } ``` **基本上這兩個資料結構你們只要知道觀念就好，考試只會考你們這種資料結構的『觀念』(不太可能叫你們實作)，觀念懂了自然看得懂考試給的程式碼，試著閱讀一下程式碼就能理解其觀念**， ## 演算法我這裡取兩個比較常考的演算法 * ### 排序 (sort) 排序顧名思義就是按照規則排順序，最常見的有由大到小排序或小到大排序，這裡舉泡沫排序法作為例子： ``` void bubble_sort(int arr[], int n) { for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (arr[j] > arr[i]) { int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } } ``` 可以參考此[影片](https://www.youtube.com/watch?v=yoOyfEMo35Y)，有詳細講解。 **排序很重要，至少搞懂泡沫排序再去考試。** * ### 二分搜尋法(binary search) :::info **二分搜尋法的原理跟小時候大家玩「終極密碼」的流程十分類似，就是那個 1~99 要你猜數字的遊戲為了快一點猜到（或是讓敵人快一點猜到），有些人第一個數字會喊 50，為什麼呢？因為無論數字是小於 50 或是大於 50，剩下能猜的數字一定會砍一半，變成原本的 1/2假設下一次也繼續這樣砍對半，大概猜個七八次，就能「保證」一定猜得到。 所以二分搜尋法是用來搜尋『**已排序**』的一串資料。原理是將要搜尋的值，與所有資料的中間值(中位數)做比對，若搜尋值比中間值為大，那就可以知道，中間值以前的資料全都比搜尋值還小，所以我們就不需要再浪費時間搜尋這個範圍的值，接著，由於搜尋到資料的可能範圍僅剩下一半(中間值之前或之後)。我們運用同樣的方式，取出這個範圍資料的中間值與搜尋值做比對。再依據此中間值將資料分成兩半，直到找到搜尋值為止。 ** ::: 可以參考這[影片](https://www.youtube.com/watch?v=x1d1b6Rb--E)，他把二分搜尋做成動畫，理解原理後試著把程式碼與原理連結起來。下面是範例程式碼： ``` int binary_search(const int arr[], int start, int end, int khey) { if (start > end) return -1; int mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法 if (arr[mid] > khey) return binary_search(arr, start, mid - 1, khey); else if (arr[mid] < khey) return binary_search(arr, mid + 1, end, khey); else return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於 } ``` * **有關資料結構與演算法的部分，它們的『精神』你們一定要理解，雖然未必能夠實作得出來，但是當考試有給程式碼的時候，透過閱讀程式碼就足夠你們解題了！**