###### tags: `資訊科技`
# 程式設計(使用C++)

[銜接課程題單](https://hackmd.io/@cube/Hk1YqttAL)
## 零、評量方式
1. 上課基本練習
2. [SoloLearn C++ Tutorial (XP/4) ](https://www.sololearn.com/)

:star: 本單元結束後1週登記成績。

:lollipop: 全部學完可拿到[證書](https://i.imgur.com/0yAAPlB.jpg) ，若拿到 2 張證書有小獎 。

3. [TOI線上練習賽](https://toi-reg.csie.ntnu.edu.tw/)(Bonus)
- 上學期10、11、12月，下學期3、4、5月，最後一週。
- 星期一08:00 ～ 星期五20:00。
- 90分鐘。
- 教師代碼：12
- [證書](https://drive.google.com/open?id=1DcgDKn1R33kOPc_HazdIyQDgyYxSCPlZ)。

## 一、基本使用
### 1. 編輯軟體
+ [Code::Blocks / codeblocks-17.12mingw-setup.exe](http://www.codeblocks.org/)
+ [Dev-C++](http://orwelldevcpp.blogspot.com/2015/04/dev-c-511-released.html)
+ Google文件
- 學習歷程檔案之課程學習成果
- [Code Block-Google Docs add-on](https://gsuite.google.com/marketplace/app/code_blocks/100740430168)
+ [HackMD-Markdown共筆平台](https://hackmd.io/)
- 學習歷程檔案之課程學習成果
- [從無到有學習HackMD](https://www.youtube.com/watch?v=r5FOR-YU33c&t=1s)
- [用Markdown做筆記](http://moocs.nccu.edu.tw/media/17832)
- [Markdown教學](https://dotblogs.com.tw/chris_coding/2017/03/30/102046)
- [表格生成器：Markdown Tables Generator](http://www.tablesgenerator.com/markdown_tables)
- [功能介紹](https://hackmd.io/features-tw)
+ 學習歷程檔案之課程學習成果
- [大學選才與高中育才輔助系統](https://collego.ceec.edu.tw/)
- 最後一週上課結束前如果認證完成，學期總成績加分。
- 上傳的PDF大小限制為2MB，圖片如果太大，可用小畫家將解析度調小。
- HackMD筆記可下載成HTML(選單／下載 / HTML)，再以[PDF24 Tools](https://tools.pdf24.org/zh/)轉成PDF。如果要將PDF插入到Word中，可用同一網站將PDF轉圖像再插入。

### 2. 變數型態
| 常用型態 | 意義 | 範圍 |
|:-------|:---------- |:-------|
| int | 整數 |-2147483648~2147483647||
| long long int | 長整數 |-2^63^ ~ 2^63^-1||
| float | 單精度浮點數(小數) |±1.5x10^−45^ ~ ±3.4x10^38^|
| double | 雙精度浮點數(小數) |±5.0×10^−324^ ~ ±1.7×10^308^|
| char | 字元 | 'A'|
| string | 字串 | "Hello"|
| bool | 布林 | true、false|

### 3. 變數宣告

int math=80;             // 資料型態 變數名稱;
double pi=3.14159265359; // 資料型態 變數名稱=初值;
int sum,ave,rank;        // 資料型態 變數名稱1,變數名稱2,變數名稱3...;

:::info
EX_01：輸入三角形三邊長，以[海龍公式](http://www2.chsh.chc.edu.tw/bee/1050206/heron%20formula.pdf)求三角形面積。
:mega: 先輸出s看看是否正確。
　　(1) 先乘除後加減
　　(2) 整數除法、浮點數除法：5/2、5.0/2
　　(3) 資料型態轉換： a=4, b=5, c=6, s=7.5

:::

#include <iostream>
.......                    // 含入 cmath 標頭檔，才可使用sqrt

using namespace std;
int main()
{
    /* 
     int a;
     int b;
     int c;
     cin >> a;
     cin >> b;
     cin >> c;
     cout << a;
     cout << b;
     cout << c;
    */
    
    ........               // 宣告 a,b,c 三邊長變數為整數型態
    double s, area;

    ........               // 以cout輸出提示字串
    ........               // 以cin輸入邊長變數。cin >> a,b,c; 是錯誤的語法
    ........               // 輸出a,b,c，看看輸入是否正確
    
    s = ........           // 分子要加()，且把型態轉成double
    area = ........        // sqrt開根號，乘號不可以省略
    cout << "三角形面積為 " << area << endl; 

    // a=3,b=4,c=5,area=6
    // a=4,b=5,c=6,area=9.92157
    return 0;
}

## 二、運算子
### 1. 算數運算子
| 算數運算子 | 意義 | 備註|
|:-------- |:------ |:-------|
| + | 加 | |
| - | 減 | |
| * | 乘 | |
| / | 除 | |
| % | 取餘數 | |
| ++ | 遞增 | i++ 即 i=i+1|
| \-\- | 遞減 | i\-\- 即 i=i-1|

int a=1,b;
b=a++;    // b=++a;
cout << a << " " << b;
/*
 b=a++;
 b=a;
 a++;
 
 b=++a;
 a++;
 b=a;
*/

### 2. 關係運算子
| 關係運算子 | 意義 | 備註|
|:-------- |:------ |:-------|
| == | 等於 | =是指派，==是判斷是否相等 |
| != | 不等於 |
| > | 大於 |
| >= | 大於等於 |
| < | 小於 |
| <= | 小於等於 |

### 3. 邏輯運算子
| 邏輯運算子 | 意義 | 備註|
|:-------- |:------ |:-------|
| && | and |
| \|\| | or |
| ! | not |

## 三、選擇

### 1. if 條件式語法

if(條件)
{
    條件「成立」時的程式碼
}

### 2. if~else 語法：

if(條件)
{
    條件「成立」時的程式碼
}
else
{
    條件「不成立」時的程式碼
}

:mega: [常用運算子的優先順序](https://itw01.com/V2HWOE4.html)

:mega: if()後不能加「;」

:mega: 養成縮排的好習慣：大括號 { } 內的程式碼以Tab鍵向右縮排，可以增加程式碼的可讀性，並方便除錯。

:::info
EX_02：承EX_01，先判斷三邊長是否可以構成三角形。如果可以，求三角形面積；如果不行，輸出錯誤。

Tip：每邊長要大於0，且任兩邊之和要大於第三邊。
:::

int main()
{
    ........                                           // 宣告 a,b,c 三邊長變數為整數型態
    double s, area;

    cout << "請輸入三邊長：";
    cin >> a >> b >> c;

    if (a > 0 && ........ && a + b > c && ........)  // if else 後不可加分號
    {
        s = ........
        area = ........
        cout << "三角形面積為 " << area << endl;
    }
    else                                               // 不用加分號
    {
        cout << "不能構成三角形";    
    }
    
    // -1 5 5
    // 1 3 1
    return 0;
}

### 3. 巢狀 if 語法

if(條件1)
{
    if(條件2)
    {
        條件1「成立」，且條件2「成立」時的程式碼
    }
    else
    {
        條件1「成立」，且條件2「不成立」時的程式碼
    }
}
else
{
    條件1「不成立」時程式碼
}

:mega: if或else的大括號{ }內，都可再增加條件式。

:::info
EX_03：驗證登入帳號、密碼。
:::

int main()
{
    int a;
    cin >> a;
    cout << a+10;
    
    string b;
    cin >> b;
    cout << b;
    cout << b+10;
    cout << b+"10";
    return 0;
}

int main()
{
    string user,pwd;

    cout << "請輸入帳號：";
    cin >> user;
    ........   // 讓使用者輸入密碼
    ........

    ........   // 如果帳號正確 而且 密碼正確
    {
        cout << "Welcome";
    }
    ........   // if 條件不成立
    {
        cout << "帳號或密碼輸入錯誤";
    }

    return 0;
}

int main()
{
    string user,pwd;

    cout << "請輸入帳號：";
    cin >> user;
    ........      // 讓使用者輸入密碼
    ........

    if (user=="admin" && ........)
    {
        cout << "Welcome";
    }
    else
    {
        ........  // 不等於!=
        {
            cout << "帳號錯誤";
        }
        ........
        {
            cout << "密碼錯誤";
        }
    }
    // Q：帳號、密碼都錯時會顯示？如何顯示帳號錯誤，密碼錯誤？

    return 0;
}    

### 4. 多重選擇 if~else if~else 語法

if(條件1)
{
    條件1「成立」時程式碼區塊
}
else if(條件2)
{
    條件1「不成立」，且條件2「成立」時的程式碼
}
else if(條件3)
{
    條件1、2「不成立」，且條件3「成立」時的程式碼
}
....
else
{
    上述條件都「不成立」時的程式碼
}

:mega: else if()可視需要增加。

:::info
EX_04：將成績轉換成等級制。
80以上 A，70 ~ 80 B，60 ~ 70 C，60以下 D，其它「錯誤」。
:::

int main()
{
    int score;

    cout << "請輸入成績：";
    cin >> score;

    if (score >= 80)
    {
        cout << "A";
    }
    ........         // 70~80，70<=score<80 是錯誤的語法
    {
        ........
    }
    ........         // 60~70
    {
        ........
    }
    ........         // 0~60
    {
        ........
    }
    else
    {
        cout << "輸入錯誤！";
    }

    return 0;
}    

int main()
{
    int score;

    cout << "請輸入成績：";
    cin >> score;

    if ........      // 成績大於100 或者 小於0
    {
        cout << "輸入錯誤！";
    }
    else
    {
        if (score>=80)
        {
            cout << "A";
        }
        ........     // 70~80
        {
            ........
        }
        ........     // 60~70
        {
            ........
        }
        ........     // 0~60
        {
            ........
        }
    }

    return 0;
}

## 四、迴圈
### 1. for 迴圈語法

for(變數初值;條件判斷;改變量)
{
    程式碼
}

:::info
EX_05_1：印出 10 個 "hello"。

:mega: 除錯練習
(1) 設中斷點
(2) Debug (F8)
(3) Debugging windows/Watches
(4) Next line (F7)
(5) Stop debugger
Q2：i=i+3，會印出幾個hello，最後 i 會顯示多少？
:::

int main()
{
    int i;                  // 區域變數 vs. 區塊變數 for (int i=1;i<=10;i++)    
    for (i=1;i<=10;i=i+1)   // 讓 i 從 1~10。for()後面不可加分號
    {                        
        cout << "hello ";
    }                       
    cout << i;              // Q1：i 會顯示多少？
}

/*
i=i+1
i+=1
i++
*/

:::info
EX_05_2：計算 n! (先完成1+2+...+n)
:::

int main()
{
    int n,sum=....;         // sum 初值設為 0

    cout << "請輸入n：";
    cin >> n;

    for ........            // 讓 i 從 1~n
    {
        ........            // 每次迴圈 sum=sum+i
    }                       // 複合指定運算子 +=
    cout << sum;

    return 0;
}

### 2. 巢狀迴圈語法

for(變數1初值;條件1判斷;改變量)
{
    for(變數2初值;條件2判斷;改變量)
    {
        程式碼
    }
}

:::info
EX_06_1：印出n列的直角三角形。

:::

int main()
{
    int n;
    cout << "請輸入n：" ;
    cin >> n ;

    for ........          // 總共n列
    {
        for ........      // 星號的數量和列編號有關
        {
            cout << "*";
        }
        ........          // 印完一列要換行
    }

    return 0;
}

:::info
EX_06_2：調整EX_06_1，印出金字塔形狀。


:::

int main()
{
    int n;
    cout << "請輸入n：";
    cin >> n;

    for ........                      // 總共n列
    {
        for ........                  // 每列印星號之前先印「空白」
        {
            cout << " ";
        }

        for (int j=1;j<= .... ;j++)   // 星號的數量和列編號有關(1,3,5,7,9...)
        {
            cout << "*";
        }
        ........                      // 印完一列要換行
    }

    return 0;
}

:::info
EX_06_3：調整EX_06_2，加上樹幹變成聖誕樹。([等差數列第n項公式](https://www.liveism.com/live-concept.php?q=%E7%AD%89%E5%B7%AE%E6%95%B8%E5%88%97%E7%AC%ACn%E9%A0%85%E5%85%AC%E5%BC%8F%E7%9A%84%E6%8E%A8%E5%B0%8E))

:::

:::info
EX_06 (Bonus)：3層聖誕樹。


[:grimacing: 偷看解答](http://cs.cysh.cy.edu.tw/computer_concept_108/christmas_tree.html)

:::

### 3. while 迴圈語法

while(條件判斷)    // 條件為「真」的時候繼續執行
{
    程式碼
}

for (int i=1;i<=5;i++)
{
    cout << "hello ";
}
cout << endl;

int i=1;
while (i<=5)
{
    cout << "hello ";
    i++;
}

:::info
EX_07：while 存錢買手機。
:::

int main()
{
    int i=1, ......... ;

    while ........         // 錢沒存夠
    {
        cout << "請輸入第 " << i << " 個月的存款： ";
        cin >> money;
        ........          // 把 money 加到 sum
        ........          // i+1
    }
    cout << "存了 " << .... << " 個月，總共 " << sum;

    return 0;
}

break：強制跳出「整個」迴圈
continue：強制跳出「此次」 迴圈，繼續進入下一次圈

:::info
EX_08：sqrt()實作。
:::

int main()
{
    int n;
    bool sol=false;

    cin >> n;

    for ........         // 只需檢測到 n/2
    {
        if ........      // 如果i的平方等於n
        {
            cout << i;
            ........     // sol 設為 true，表示找到根
            ........     // 跳出迴圈
        }
    }

    if ........          // 沒有解，! -> not
    {
        cout << "只能求完全平方數的平方根！";
    }

    return 0;
}    

Q：4不行？

:::info
EX_08 除錯練習。
:::

<pre style="color:#f7f7f7;font-size:xx-small;">
#include <iostream>
using namespace std;
int main()
{
int n;
bool sol=false;
cin >> n;

for(int i=1;i<=n/2;i++)
{
if(i*i=n)
{
cout << i;
sol=true;
break;
}

if(!sol)
{
cout << "只能求完全平方數的平方根！";
}
}

return 0;
}
</pre>

:::info
EX_09：sqrt()實作 (以二分搜尋法實作)

:mega:　(1) [printf](https://openhome.cc/Gossip/CGossip/PrintfScanf.html)
　 　 (2) [科學記號表示法](http://notepad.yehyeh.net/Content/CPP/CH01/03DataType/1.php)
:::

int main()
{
    double n,lower,upper,mid;
    // Q2
 
    cin >> n;
    lower = 1;
    upper = n;
    mid = n/2;
                                // mid*mid!=n？ 當mid*mid和n的誤差 > 10^-13(數學寫法)時，就繼續逼進。(mid^2-n要取絕對值，需含入標頭檔cmath)
    while ........              // 上下界限的差 > 10^-13，就繼續逼進
    {
        mid = ........          // mid 為上下界限的中間
        printf("%.13f\n",mid);  // 把每次的mid都印出來看看，需含入標頭檔 cstdio
        // Q2

        if ( mid*mid > n )      // 如果中間數的平方 > n，解在lower~mid間
            ........            // 將上限調為 mid
        else if ........        // 如果中間數的平方 < n，解在mid~upper間
            ........            // 將下限調為 mid
        else
            break;
    }
    printf("經過了 %d 次運算，根號 %f 為 %.13f\n", cnt,n,mid);
    
    return 0;
}

Q：新增一個整數變數cnt，記錄總共做了幾次運算得解。

### 4. do..while 迴圈語法

do
{
    程式碼
}while(條件判斷);  // 條件為「真」的時候繼續執行

:mega: do while()後要加分號！

:::info
EX_10：sqrt()實作 ([以牛頓法實作](http://mathcenter.ck.tp.edu.tw/Resources/Ctrl/ePaper/ePaperOpenFileX.ashx?autoKey=55))
:::

int main()
{
    double n, a, b;
    
    cin >> n;
    a = n;
    
    do
    {
        b = ........       // 挑出的第1個近似值a之後，作一切線，切線和x軸的交點為b
        ........           // 下一次以此次的b繼續求切線和x軸的交點
    } while ........       // b*b!=n？ 當b*b和n的誤差>1e-13時，就繼續逼進
    cout << b;
    
    return 0;
}

Q：a,b簡化只用一個變數。

## 五、陣列
### 1. 陣列宣告

int arr[5];                      // 宣告一個大小為5的int陣列
arr[0]=80;                       // 陣列的索引值由0開始
arr[5]=90;                       // 索引值0~4
int arr[5] =  { 1, 3, 5, 7, 9 }; // 宣告陣列時設定初值
int arr[5] =  { 1 };             // arr[0]初值1，其餘預設為0
int arr[] = { 1, 3, 5, 7, 9 };   // 陣列大小依初值自動計算

int arr2D[4][2];                 // 宣告二維陣列(多維陣列)
int arr2D[4][2] = { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } };

Q：如何建立可以儲存班上期中考成績的2維陣列？
// arr2D[r][c]表示第 r 列，第 c 欄的值(類似英文書寫習慣)

:::info
EX_11：考試成績存放在陣列，找出最高分。
:::

int main()
{
    int a[5]={87,61,92,83,95},max=-1; // 最大值的初值為一個比陣列值都小的數值

    for ........     // 從頭看一遍
    {
        if ........  // 如果陣列第i個位子的值 > max
        {
            ........ // max 換成陣列的值
        }
    }

    cout << "最高分為 " << max << endl;

    return 0;
}

Q：如何找出最低分？

:::info
EX_12：[ZeroJudge c067: 00591 - Box of Bricks](https://zerojudge.tw/ShowProblem?problemid=c067)。
:::

int main()
{
    int n;
    cin >> n;
    
    int h[n],sum=0,ave,mov=0;

    for(int i=0;i<n;i++)
    {
        cin >> h[i];
    }
    
    for ........
    {
        ........                 // 把所有的牆高加總
    }
        
    ........　　　　　　　　　　   // 算出牆高平均

    for ........                 // 把所有的牆看一遍
    {
        if ........              // 如果牆高 > 平均
        {
            ........             // 將(此牆高-平均)加總
        }
    }

    cout << "The minimum number of moves is " << mov << endl;
}

:::info
EX_13_1：大樂透電腦選號。
:mega:　[亂數觀念](https://blog.gtwang.org/programming/c-cpp-rand-random-number-generation-tutorial-examples/)
:::

int main()
{
    ........                     // 宣告一個大小6的num陣列
    srand(16);                   // 設定亂數種子。srand(time(NULL)); 需含入標頭檔 ctime

    for ........                 // 陣列的索引值由0開始，所以i初值要設為0
    {
        num[....] = rand()....;  // 隨機產生1~49間的數，需含入標頭檔 cstdlib
                                 // Q：50~100
    }

    for ........                 // 印出陣列裏的亂數
    {
        cout << num[....] << " ";
    }

    return 0;
}

:::info
EX_13_2：大樂透電腦選號(解決數字重覆的問題)。
:::

int main()
{
    int num[6];                 // 宣告一個大小6的num陣列
    int mark[50]={0};           // 標記陣列的初值=0。50個空間，陣列索引值為0~49
    int t;
    srand(16);                  // 設定亂數種子。srand(time(NULL)); 需含入標頭檔 ctime

    for (int i=0;i<6;i++)       // 陣列的索引值由0開始，所以i初值為0
    {
        do
        {
            t = rand()%49+1;    // 隨機產生1~49間的數，暫放於t
        } while(........);      // 如果mark陣列第t個位子為1，代表亂數重覆，再產生另一個亂數
        
        ........                // 將產生的不重覆亂數記錄在num陣列
        ........                // 將mark陣列第t個位子的值設為1，表示產生過t這個數字
    }

    for (int i=0;i<6;i++)       // 印出陣列裏的亂數
    {
        cout << num[i] << " ";
    }

    return 0;
}


Q1：產生亂數後，檢查此數字是否重覆，如果重覆再產生一次，下列程式碼想法有何漏洞？
    for(int i=0;i<6;i++)
    {
        t=rand()%49+1;
        for (int j=0;j<i;j++)
            if (t==num[j])
                t=rand()%49+1;
        num[i]=t;
    }
    
Q2：t=rand()%5+1會發生什麼狀況？(陣列除錯練習)    

:::info
EX_13_3：大樂透電腦選號(將數字排序顯示-[Bubble Sort](https://medium.com/@mingjunlu/understanding-bubble-sort-7aa4567986ae))

:mega:　其它排序演算法
(1) [插入排序法(Insertion Sort)(1)](https://jason-chen-1992.weebly.com/home/-insertion-shell-sort) [(2)](https://kopu.chat/2017/06/22/插入排序insertion-sort/)、[選擇排序(Selection Sort)](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff)

(2) [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms)
:::

// 此段程式碼置於EX_13_2第18行的位置(產生亂數後排序)

    for ........                       // 6個數字排序只需5個循環
    {
        ........                       // 每次比較索引值0 1、1 2、2 3、3 4、4 5的數字
        {
            if (num[....] > num[....]) // 如果左邊比右邊大
            {
                ........               // num[j]和num[j+1]交換
                ........
                ........
            }
        }
    }

Q：for 內圈寫完後(將最大值移至最右的位子)，複製貼上5次，程式碼會正確嗎？

### 2. 二維陣列

:::info
EX_14：求學測總分、平均、名次。
:::

int main()
{
    int score[4][8] = {{12,13,15,10,12,0,0,0},{15,13,15,15,14,0,0,0},{14,14,12,15,13,0,0,0},{11,10,12,12,10,0,0,0}};
    int sum;

    for ........                      // 4個人，列
    {
        ........                      // 計算每人總分之前，sum 要先歸0
                                      // int sum=0;(每次都宣告一個新的變數) vs. sum=0;(把公用的變數清空)
        for ........                  // 5科，欄
        {
            sum += score[....][....];
        }
        score[....][5] = sum;
        score[....][....] = sum/5;
    }
    
    // 先印出來看看
    cout << "座號\t國文\t英文\t數學\t自然\t社會\t總分\t平均\t名次\n";

    for (int i=0;i<....;i++)         // 4個人，列      
    {
        ........                     // 先印出座號
        for (int j=0;j<....;j++)     // 5科+總分、平均、名次，8欄
        {
            cout << score[....][....] << "\t";
        }
        cout << endl;
    }

    return 0;
}

:::info
EX_14 (Bonus)：多加一個欄位求名次。
Hint：類似bubble sort的寫法。若此位同學的總分<p位同學，名次為p+1。
:::

for ........             // 對第i個人求名次
{
    int p=1;             // 每個人先預設為第1名
    for ........         // 計算成績大於第i個人的人數，從頭比較每個人的總分
    {
        if (score[....][....] < score[....][....]) // 別人的成績>第i個人的成績，名次就多1名
        {
            p++;
        }
    }
    ........             // 記錄第i個人的名次
}

## 六、函式
### 1. 自定函式宣告語法

回傳值的型態 函式名稱(變數型態 參數1，變數型態 參數2，...)
{
    程式碼
    return 回傳值或運算式;
}

:::info
EX_15：[ZeroJudge b112: 5. 高中運動會](https://zerojudge.tw/ShowProblem?problemid=b112)。
以輾轉相除法求兩數的最大公因數(寫成函式)，並用之來求4數的最大公因數。

[輾轉相除法](http://www.mathland.idv.tw/fun/euclidean.htm)

[短除法找三數的最大公因數(數學方法)](https://www.junyiacademy.org/junyi-math/m4n/m4nyb-/mjnfs7b/v/XK_gpcahyTE)

:::

int gcd(int a,int b)
{
    int r;
    do
    {
        r = a % b;              // r 為 a 除以 b 的餘數
        ........                // 下一次的 a 為 ?
        ........                // 下一次的 b 為 ?
    } while ( ........ );       // 當 ? 不為 0 時繼續做

    ........                    // 回傳 a,b 的最大公因數，a? b? r?
                                // g=gcd(12,16) 函式除錯(Step into)
}

int main()
{
    cout << gcd(12,16) << endl; // 先檢查函式有沒有寫對，gcd(12,16)->4

    int a=400,b=200,c=150,d=625,g;
    g=gcd(a,b);                 // g 為 a,b 的最大公因數
    ........                    // g 再和 c 求最大公因數
    ........                    // g 再和 d 求最大公因數
    cout << g;                  // cout << gcd(gcd(gcd(a,b),c),d);
    
    return 0;    
}

:::info
EX_16 (Bonus)：寫一函式可以計算n!，並以之求 $C(n,k)=\frac{n!}{(n-k)! * k!}$，例如C(4,2)=6。

int f(int n)
{
    ........     # 計算 n!
}

int main()
{
    cout << f(5) << endl; // 先檢查函式有沒有寫對，5!->120
    
    int n,k;
    cin >> n >> k;
    cout << ........
   
    return 0;    
}

:::

### 2. 傳值(call by value)、傳參考(call by reference)
:::info
EX_17：將排序時用到的兩數交換程式碼，寫成函式。
:::

void swap(int ....a, int ....b) // void 表示沒有回傳值
{
    int t;
    ........
    ........
    ........
    cout << "函式內："<< a << " " << b << endl;
}

int main()
{
    int a=1,b=2;
    cout << "交換前：" << a << " " << b << endl;
    swap(a,b);
    cout << "交換後：" << a << " " << b << endl;
    
    return 0;    
}

### 3. 遞迴

:mega: 問題的答案，可從同類的子問題(規模更小)得到。

:mega: 在函式之中呼叫函式自己本身，要有終止條件，不然會無窮遞迴下去。

:::info
EX_18：[95數學學測填充題G](http://cs.cysh.cy.edu.tw/computer_concept_108/高中數學遞迴.xps)
用黑、白兩種顏色的正方形地磚依照如下的規律拼成若干圖形：


拼第95個圖需用到幾塊白色地磚。(478)
:::

:::info
EX_18 (Bonus)：求費式數列第n項。

[費式數列遞迴式](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97)
:::

int brick(int n)
{
    if ........          // if後只有一行，可省略{}
        ........
    else
        return brick(n-1)+5;
}

int fib(int n)
{
    if (n == 0)          // n==0時終止，回傳0。if後只有一行，可省略{}
        return 0;
    else if ........     // n==1時終止，回傳1
        ........
    else
        ........         // 遞迴呼叫
}

int main()
{
    int n;
    cin >> n;
    cout << brick(n) << endl; // 5->28
    cout << fib(n) << endl;   // 5->5
   
    return 0;    
}

:::info
EX_19：以遞迴改寫 EX_15 高中運動會中的gcd函式。
:::

........                // 函式宣告，名稱為gcd，參數a,b
{
    if ........ 
        return ........
    else
        return ........
}

int main()
{
    cout << gcd(12,16) << endl; // 先檢查函式有沒有寫對，gcd(12,16)->4
    
    int num[8] = {400, 200, 150, 625, 600, 100, 15, 20};
    
    int g = gcd(num[0], num[1]);
    for ........         // 從num[2]開始，都和g求gcd
        g = gcd(g, ....);
    cout << g;           // ans->5
    
    return 0;    
}

:::info
EX_20：以遞迴函式計算 n 層香檳塔，總共有幾個杯子。
遞迴式 : f(n)=1　,if n==1
　　　　f(n)=？ ,if n>1

:::

int f(int n)
{
    ........
}

int main()
{
    int n;
    cin >> n;
    cout << f(n); // 平面 4->10
                  // 立體 4->20
    return 0;    
}

:::info
EX_20 (Bonus)：計算 n 層「三角錐形」香檳塔，總共有幾個杯子。
( 第1層1個、2->3、3->6、4->10、5->15、第n層->？個杯子 )
[2017的世界紀錄總共杯子數量為50116](https://kknews.cc/zh-tw/food/3j4y43y.html)，疊了幾層？

:::