# 南湖APCS

#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**

* 程式碼該怎麼寫？
* **step1. 讀資料**
看完題目可以知道
需要先讀取有幾筆資料(num)
以及陣列內容(arr[])

* **step2. 切割**
將陣列切割，從原本的8個->4個->2個->1個
雖然說是切割，但我們不需要創出新的陣列
只需要以==index==來判斷就行
這裡會需要使用到==遞迴==


        //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. 排序＆放回原本的陣列**
為什麼說放回原本的陣列？
因為在這裡我們要宣告新的陣列（比較方便）



        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++;
            }
        }

# 不要給我照抄 然後問我為什麼不行 請動腦
# 腦袋是個好東西 除非你沒有