---
# System prepended metadata

title: APCS 筆記

---

# APCS 筆記

<i class="fa fa-book fa-fw"></i> 這裡幫你們分幾個部分複習，因為是筆記，所以內容幾乎只講重點，如果有問題就馬上問我，自己google也行，**除了演算法和及資料結構的部分，其他的幾個你們都要很熟**，如果我用<font color="#f00">紅色字的部分是一定要知道的觀念，不能不知道</font>。

## 目錄
 [TOC]


## 電腦科學基礎概念

* **電腦基礎運作原理**
    :::info
    **中央處理器(CPU**)：真正的大腦，所有的運算都透過它
    **硬碟(ROM)**：資料真正儲存的地方，當你重新開機後資料還會存在。
    **記憶體(RAM)**：資料暫存的地方，如果你沒儲存，關機後這存在這裡的資料就會被清除
    :::
    
    
    假設你正在打做一份PowerPoint報告，你多增加了兩頁但你還沒按儲存時，此時這兩頁的資料就是存在RAM中的，所以一旦你沒有儲存就關掉，此時你RAM就會把你這兩頁給清除掉，但是當你按下儲存按鍵後，電腦就會把存在RAM中的資料寫入到ROM，達到真正保存的效果。
   <font color="#078c66">`(但是現在的程式都很聰明會自動幫你儲存，所以這種現象只有在以前比較容易看到) `</font>
      ~~<font color="#078c66">`(你們也可以自己試看看不要儲存直接關機) `</font>~~
   
    > *那為何不直接存到ROM，還要裡要透過RAM呢?*
    > 
    > <font color="#050505">因為以前的電腦如果真的做儲存的動作，是很耗時間的，如果每次的修改都要存，如果一直存存改改的太沒效率了，所以如果有RAM先幫忙存，等到確定要保存下來的時候在寫入到ROM中，ROM的負擔就不會那麼大了</font>
    

* **二進制與0,1**

    > 所有的電子設備中，每一個動作都是在做運算(就連滑鼠移動一下，電腦也要運算出現在滑鼠的位置座標，然後更新到你的螢幕，讓你看起來滑鼠像是移動了)，而且都是使用0與1做運算的。電腦也只看得懂二進制，但是人類習慣看的是十進制的數字，所以要透過進制轉換來溝通。
    > 
    <font color="#1a09d9">在所有進制轉換的考題中，不管題目要什麼幾進制轉幾進制，一律都先轉成十進制</font>，教學可以去看我的PPT裡面，[這裡](https://www.slideshare.net/ShawnWu37/binary-234608474)可以看，有問題問我！
    



## C語言-基礎概念

:::info
1. 程式『一定』都是由上執行到下的。
2. 程式語言是用英文與符號組成，但電腦看不懂人類語言，所以需要透過『編譯器』把人類看的程式語言轉成電腦看得懂的機器語言。
3.  <font color="#f03c3c">main是程式的起點，只要main執行完 程式就結束！</font>，所以任何想要執行的程式或者函數，都必須要在main裡面在程式結束前執行到。
4. main本身是一個函數(function)，所以main也叫main函數(main function)
6.  <font color="#f03c3c">main可以調用函數，讓其他函數被使用到，但不等於可以把其他函數寫在main裡面(切記 這很重要！)</font>
7.  每一行程式碼都要加 ; 句點

8. 區域變數與全域變數的差異一定要弄清楚
![](https://i.imgur.com/hExABrk.jpg)

9. **<font color="#f03c3c">大括號{}一定要對應好。</font>**

:::


## Ｃ語言-基礎語法
* <font color="#f03c3c">**printf()**</font>用來輸出內容到螢幕，方便人類查看
* <font color="#f03c3c">**scanf()**</font>用來輸入內容到程式裡，好讓程式接收我們給的資料去相關的運送，使用時給予想要讀入的資料格式與變數位址
    ![](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都可以使用在小數點的計算，雙倍比單倍能存更多的小數點後的位數
    

* <font color="#f03c3c">**變數一定要先宣告才能用**</font>
    ![](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可以省略。
    <font color="#f03c3c">**if裡面的條件式如果為0(false)就不執行，如果是1(true)或大於1，就會執行**</font>
    
*  關係運算子
    

    |  | 符號   | 範例     |
    | -------- | -------- | -------- |
    |   等於     |   ==   | if(a == b)     |
    |   不等於    |   !=   | if(a != b)     |
    |   小於     |   <   | if(a > b)     |
    |   大於     |   >   | if(a < b)     |
    |   大於等於  |   >=   | if(a >= b)     |
    |   小於等於  |   <=   | if(a <= b)     |
    <font color="#f03c3c">**一個=是賦值，兩個= (==)是關係判斷**</font>
    
*  邏輯運算子
     | 運算子    | 運算內容   | 範例           | 範例結果 |
     | -------- | -------- | --------       |--------|
     | &&       | and(而且) | 3>2 && 2<1     | 0     |
     | II       | or(或者)  | 3>2 II 2>1     | 1     |
     | !       | not(非)    | !(3>2)         | 0     |


*  運算子優先順序
     | 順序     | 運算子   | 算術類型  | 結合順序 |
     | --------| -------- | -------- |--------|
     | 1       | !            |邏輯運算|<font color="#0000">由右至左</font>| 
     | 2       | ＊  /  ％     |算術運算|<font color="#f03c3c">由左至右</font>|
     | 3       | ＋   -        |算術運算|<font color="#f03c3c">由左至右</font>|
     | 4       | >  <  >=  <=  |關係運算|<font color="#f03c3c">由左至右</font>|
     | 5       | !=    ==      |關係運算|<font color="#f03c3c">由左至右</font>|
     | 6       | &&            |邏輯運算|<font color="#f03c3c">由左至右</font>|
     | 7       | II            |邏輯運算|<font color="#f03c3c">由左至右</font>|
     | 8       | ＝            |賦值運算|<font color="#0000">由右至左</font>|
     

## Ｃ語言-迴圈loop
:::info
<font size=4>有時候，我們需要讓電腦重複執行某些指令，直到條件成立為止，這種語法稱為迴圈。
在 C 語言中的迴圈敘述有三種，分別是 for、while、do-while。</font>
:::

* **while**
    
        while (條件式) {
         程式碼一;
         程式碼二;
        }
    上面的語法是當條件式成立時，程式會重複執行程式碼一，程式碼二，直到條件式不成立時，所以在while迴圈裡，都會設一個停止的條件，例如下面例子中，當i>10時就會停止迴圈，而記得要再回圈內更新i，才能使迴圈停止

      while(i<10){
       printf("Hello\n");
       i++;
      }
      
* **do-while**
    
        do {
         程式碼一;
         程式碼二;
        } while (條件式);
    <font color="#f03c3c">while與do-while從意義上來看它們兩者完全一樣</font>，唯一的不同是， while是先檢查條件是否成立，成立才執行下面的指令，而do-while是不論條件是成不成立，都會先執行一次那些程式碼，再去檢查條件是否成立。

        do{
            printf("Hello\n");
            i++;
        }while(i<10){
        
* **for**
    
        for (起始值; 條件式; 更新值) {
            程式碼一;
            程式碼二;
        }
    起始值是進入迴圈一開始會執行的動作，而更新值則是執行完每次的迴圈要執行的動作，以下面例子為例，程式執行的步驟如下：
    
    <font color="#228B22">1.設定變數 i=1;</font>
    <font color="#228B22">2.檢查 i<10 是否成立，不成立則跳出迴圈</font>
    <font color="#228B22">3.執行 printf("這是第%d次迴圈\n",i);</font>
    <font color="#228B22">4.執行 i++; ( 即 i=i+1; )</font>
    <font color="#228B22">5.回到第2點繼續執行</font>
    <font color="#228B22">6.迴圈結束</font>
 
        for(int i = 0; i<10; i++){
            printf("這是第%d次迴圈\n",i);
        }
        
    - <font color="#f03c3c">**多重迴圈**</font>
    多重迴圈表示迴圈內還有其他迴圈，例如下面的例子，是利用兩個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
<font size=4>在先前的程式中，絕大部分的程式的程式碼全都寫在主函式(Main function中)裡，在規模短小的程式這樣子做並沒有什麼不好，但隨著程式規模成長，這種模式就漸漸行不通了。這時候，我們會利用函式將程式
碼分離開來，使用函式有以下的好處：</font>

* <font color="#228B22">減少撰寫重覆的程式碼</font>
* <font color="#228B22">將程式碼以有意義的方式組織起來</font>
* <font color="#228B22">在相同的流程下，可藉由參數調整程式的行為</font>
* <font color="#228B22">藉由函式庫可組織和分享程式碼</font>
:::

* **宣告函式**

        回傳的資料型別 函式名稱(要傳入的參數型別 要傳入的參數名稱){
            /／程式碼
            
            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
<font size=4>陣列是一種結構性的資料儲存空間，同一陣列裡的資料型別都是相同的，元素與元素之間的記憶位置是相鄰的，通常我們利用一個變數來代表整體的資料，舉例而言，我們可以把陣列想成一排置物櫃，而陣列裡的變數代表放在置物櫃的東西數量，例如：置物櫃[20]，我們可以想成置物櫃總共有二十格，假如我們想要知道第三間置物櫃有多少東西，只要把置物櫃[2]的值取出，便可知道住在第三格置物櫃的東西數量。
<font color="#f03c3c">**C語言的陣列索引一定是從0的開始的**</font><font size=4>。
:::




根據陣列的結構而言，可以把陣列分為(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
**<font size=4>堆疊是一種遵循後進先出（Last In First Out，LIFO）的有序集合。在堆疊的世界裡，由於遵守後進先出原則。</font>**
:::


在生活中有許多使用堆疊的案例：自助餐店的盤子的擺放就是個例子，
當你把盤子從盤堆最上面拿起來一個盤子是從最上面開始拿，若是要把盤子放回去，一定是放到最上面的<font size=1>(~~但是不否認會有白目也會想辦法放到最下面~~)</font>，
下一個人拿到的就是你剛剛放回去的盤子，<font color="#f03c3c">以資料的角度來說，比較晚加入的資料會比較早被取走，這就是stack的精神</font>。

![](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)方法。
<font color="#11a88f">**可以想看看為何pop()沒有傳入參數而push()一定要有!?**</font>
<font color="#11a88f" size=1>(因為pop一定是從最上面開始取資料，所以不需要有傳入什麼參數告訴函式怎麼做)</font>




* ### 佇列 (queues)
:::info
**<font size=4>跟堆疊相反， 佇列是遵循先進先出先進先出(First-In-First-Out, FIFO)的集合，顧名思義是一種像排隊一樣的概念，人們一個接一個的從隊伍後面加入排隊，越晚進入就越晚被處理</font>**
:::

<font size=4 color="#f03c3c">佇列就是排隊的概念，一模一樣，以資料的角度來說，比較早加入的資料會比較早被取走，這就是queues的精神。</font>

![](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;
}
```


<font size=4 color="#f03c3c">**基本上這兩個資料結構你們只要知道觀念就好，考試只會考你們這種資料結構的『觀念』(不太可能叫你們實作)，觀念懂了自然看得懂考試給的程式碼，試著閱讀一下程式碼就能理解其觀念**</font>，

## 演算法
我這裡取兩個比較常考的演算法

* ### 排序 (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)，有詳細講解。
    <font size=4 color="#f03c3c">**排序很重要，至少搞懂泡沫排序再去考試。**</font>

* ### 二分搜尋法(binary search)
:::info
**<font size=4>二分搜尋法的原理跟小時候大家玩「終極密碼」的流程十分類似，就是那個 1~99 要你猜數字的遊戲為了快一點猜到（或是讓敵人快一點猜到），有些人第一個數字會喊 50，為什麼呢？因為無論數字是小於 50 或是大於 50，剩下能猜的數字一定會砍一半，變成原本的 1/2假設下一次也繼續這樣砍對半，大概猜個七八次，就能「保證」一定猜得到。
<font size=4 color="#f03c3c">所以二分搜尋法是用來搜尋『**已排序**』的一串資料。</font>原理是將要搜尋的值，與所有資料的中間值(中位數)做比對，若搜尋值比中間值為大，那就可以知道，中間值以前的資料全都比搜尋值還小，所以我們就不需要再浪費時間搜尋這個範圍的值，接著，由於搜尋到資料的可能範圍僅剩下一半(中間值之前或之後)。我們運用同樣的方式，取出這個範圍資料的中間值與搜尋值做比對。再依據此中間值將資料分成兩半，直到找到搜尋值為止。
</font>**
:::

可以參考這[影片](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;        //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}
```



* <font size=4 color="#f03c3c">**有關資料結構與演算法的部分，它們的『精神』你們一定要理解，雖然未必能夠實作得出來，但是當考試有給程式碼的時候，透過閱讀程式碼就足夠你們解題了！**</font>