---
# System prepended metadata

title: 基礎演算法

---

# 基礎演算法

## 遞迴
指函數本身使用到自己

:::    danger
函數必須有盡頭，要有終止條件
:::
### 階乘

因為f(a) = a\*f(a-1)，例如f(3) = 3\*f(2) = 3\*2\*f(1) = 3\*2\*1

```cpp
int f(int in){
    if(in <= 0 ){
        return 1;
    }
    else if(in > 0 ){
        return in*f(in-1);
    }
}
```

### 次方
因為f(m, n)=m\*f(m, n-1)，例如：f(2, 3) = 2\*f(2, 2) = 2\*2\*f(2, 1) = 2\*2\*2\*f(2, 0) = 2\*2\*2\*1
```cpp
int f(int m, int n){
    if(n <= 0 ){
        return 1;
    }
    else if(n > 0 ){
        return m*f(m, n-1);
    }
}
```

##    排序
將陣列中的數字由小排到大的幾種方式，其中快速排序是以下中最快的
### 選擇排序
建立兩個陣列，將輸入陣列中找到最小的方入另一樣陣列的最底端，持續直到一邊鎮列為空
```cpp
#include<iostream>
using namespace std;

int main()
{
    int num[100];
    int N;
    int i, j, tmp;

    //[input]
    cin >> N;
    for( i=0 ; i<N ; i=i+1 )
    {
        cin >> num[i];
    }

    //[sort]
    for( i=0 ; i<N ; i=i+1 )
    {
        for( j=i+1 ; j<N ; j=j+1 )
        {
            if( num[i] > num[j] )
            {
                //變數交換
                tmp = num[i];
                num[i] = num[j];
                num[j] = tmp;
            }
        }
    }

    //[output]
    for( i=0 ; i<N ; i=i+1 )
    {
        cout << num[i] << " ";
    }
    cout << endl;

    return 0;
}
```
### 泡沫排序
從第一項開始比較，若比第二項大，則交換位子，每一次執行完整個陣列再次重複並且少檢查一項，總共檢查n!次，效率是O(n²)
```cpp
for(i=size-1; i>=1; i--) //當i=1時，j只做0和1。
  for(j=0; j<i; j++)
    if(arr[j] > arr[j+1])
      //switch
```
### 插入排序
設第一項為已排序區，其餘為未排序區。比較未排序區的第一個和已排序區，此項依序與已排序區的項比較，若比已排序區大，則跟他交換，或無，則放入已排序區(已排序區長度增加1)，直到未排序區為空。兩排序區總何必為整個陣列的數量，因此不需要建立兩個陣列
```cpp
for(i=1; i<size; i++){
  insert = arr[i];
  j=i-1;
  while(j>=0 && arr[j]>insert){
    arr[j+1] = arr[j];
    j--;
  }
  arr[j+1] = insert;
}
```
### 合併排序
將陣列分割成兩半，若是偶數，兩半等長，若是不為1的基數，則分割成(n/2)+1和n/2，不斷分割直到剩下的陣列只有一項。比較兩個原本是同陣列的陣列，從左到右，大的放右邊，小的放左邊。從最根部的合併直到最後只剩一個陣列

影片：https://www.youtube.com/watch?v=JSceec-wEyw

### 快速排序
設立三個指標，左邊指標、右邊指標、標準指標。
0.左邊和標準指標初始都在最左邊，又邊指標則是在最右邊。
```
[2, 5, 1, 4, 3]
2是左邊指標也是標準指標
3是右邊標準
```
1.從右邊指標開始移動，若右邊指標比標準指標的項還小(<=)，右邊指標向左一格，直到找到此項目。
```
[2, 5, 1, 4, 3]
2是左邊指標也是標準指標
1是右邊標準
```
2.接著左邊指標開始移動，若左邊指標比右邊指標的項還大(>)，做邊指標往右一格，直到找到此項目。
```
[2, 5, 1, 4, 3]
2是標準指標
5是左邊指標
1是右邊標準
```

3.此時若左邊指標項目和右邊指標項目不是同一項，則左右指標項目交換，接著執行上述步驟。
```
[2, 1, 5, 4, 3]
2是標準指標
1是左邊指標
5是右邊標準
```
重複執行一次
```
[2, 1, 5, 4, 3]
2是標準指標
1是左邊指標
1是右邊標準
```
4.若左邊指標碰觸到右邊指標，則這個項目和標準指標交換位置
```
[1, 2, 5, 4, 3]
```

這樣的步驟讓所有在標準指標項的左邊都小於他，在標準指標右邊的都大於他
接著排除標準指標，將兩邊的項目分割成兩個陣列，重複執行上述步驟，直到都只剩下一個項目，再依序拼接
```
[   2         ]
[1]  [ 5, 4, 3]
```
1不用排序，543需要
```
[   2         ]
[1]  [ 3, 4, 5]
```
排完之後5是標準指標被排除
```
[   2         ]
[1]  [       5]
     [ 3, 4]
```
34還是需要排序
```
[   2         ]
[1]  [       5]
     [ 3   ]
        [ 4]
```
這樣就全部分割完了，再依序拼接
```
[   2         ]
[1]  [       5]
     [ 3, 4]
```
```
[   2         ]
[1]  [ 3, 4, 5]
```
```
[1, 2, 3, 4, 5]
```

影片：https://www.youtube.com/watch?v=AsQW27DT82I

##    輾轉相除法
這是一種求最大公因數和最小公倍數相當快的方式
分別有大數A和小數B，先把大數當被除數，小數當除數
「被除數A/除數B=整數C...餘數m」
接著把除數B變成被除數，再把餘數m變成被除數
「被除數Ｂ／除數ｒ=整數D...餘數n」
以此類推直到被除數可以整除除數，此時除數極為最大公因數

###    最大公因數
以上已經把最大公因數取得方法解釋完，舉個例(703, 407)，基本上我們只會用到除數和被除數和餘數，所以先把整數去掉
703%407=296
407%296=111
296%111=74
111%74=37
74%37=0
因此37是703和407的最大公因數
在計算的時候會寫
```
1|703|407|1
 |407|296|
2|296|111|1
 |222| 74|
2| 74| 37|
 | 74|   |
 |  0|
```

###    最大公倍數
這算法很簡單，找出最大公因數後，把兩數除與最大公因數
再把最大公因數乘整除後的兩個數字，拿703和407舉例
703/37=19
407/37=11
37\*19\*11=7733
7733就是最大公被數


-------------------------
##  資料來源
排序1：https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/selection_sort.html
排序2：https://andyli.tw/sort/#%e6%8f%92%e5%85%a5%e6%8e%92%e5%ba%8f-insertion-sort

