---
# System prepended metadata

title: 南湖APCS

---

# 南湖APCS

```c
#include<stdio.h>
#include<stdlib.h>

/*
在這邊用struct宣告一個Card
裡面放color與number
*/

struct Card card[52];

char colors[5] = "HSDC";
int N;

void swap(struct Card *card1, struct Card *card2){
    // 交換兩張撲克牌
}

void randomShuffle(){
  int i = rand() % 52;
  int j = rand() % 52;
  // 呼叫swap函式
}


int main(){
    srand(4);
    // 用for迴圈塞入所有的52張牌
    // 從H1, H2, H3, ...H13, S1, S2, S3, ..., S13, ... 以此類推

    
    //接著用randomShuffle洗牌100次
    
    
    //讓使用者輸入要抽取前幾張牌
    //最後輸出抽出前N張牌的結果
}
```


## divide and conquer

* 定義
    將問題切成小問題後再解決
    再將結果合併求出原始問題的答案
    
* 步驟
    * step1. ==分解(divide)==
        將原問題分解為若干個規模較小
        與原問題形式相同的子問題
    * step2. ==解決(conquer)==
        若子問題規模較小且易於解決時
        則直接解
        否則，用遞迴解決各個子問題
    * step3. ==合併(merge)==
        將各子問題的解合併為原問題的解
        

### **Merge Sort**
![](https://i.imgur.com/B7LkUU0.png)

* 程式碼該怎麼寫？
    * **step1. 讀資料**
        看完題目可以知道
        需要先讀取有幾筆資料(num)
        以及陣列內容(arr[])
        
    * **step2. 切割**
        將陣列切割，從原本的8個->4個->2個->1個
        雖然說是切割，但我們不需要創出新的陣列
        只需要以==index==來判斷就行
        這裡會需要使用到==遞迴==
        
        ![](https://i.imgur.com/G9Lmaev.png)

        ``` c
        //index: 0 1 2 3 4 5 6 7
        //value: 5 3 8 6 2 7 1 4
        void merge_sort(int 陣列名稱, int 開始位置, int 結束位置){
        
            if(什麼條件下陣列會需要繼續切割?){
            
                int mid = ?;//拿到中間的index
                
                //將陣列切成兩部分
                merge_sort(陣列名稱, 前半部分的開始位置 , 前半部分的結束位置);
                merge_sort(陣列名稱, 後半部分的開始位置 , 後半部分的結束位置);
                
                //將切完的陣列合併
                merge(arr, head, mid, tail);
            }
        }
        ```
        
    * **step3. 排序＆放回原本的陣列**
        為什麼說放回原本的陣列？
        因為在這裡我們要宣告新的陣列（比較方便）
        
        ![](https://i.imgur.com/0zmFdOa.png)
        
        ![](https://i.imgur.com/ctLriBV.png)
        
        ``` c
        void merge(int 陣列名稱, int 開始位置, int 中間位置, int 結束位置){
            
            int 前半段陣列的長度 = ？;
            int 後半段陣列的長度 = ？;
            
            int 前半段陣列的複製品, 後半段陣列的複製品;
            
            //可以用for迴圈來做
            /*先將原本陣列 「複製到」 新的陣列
            （前半段陣列的複製品、後半段陣列的複製品）*/
            
            //可以用for也可以用while
            /*這裡要有「兩個」變數（i, j）來記兩個陣列(front, back)的目前位置
             類似下面的程式碼
             但是有些條件要想一下*/
            if(front[i]<back[j]){
                arr[開始位置+現在做了幾次] = front[i];
                i++;
            }
            else{
                arr[開始位置+現在做了幾次] = back[j];
                j++;
            }
        }
        ```
        
# 不要給我照抄 然後問我為什麼不行 請動腦
# 腦袋是個好東西 除非你沒有