# 基礎演算法 ## 遞迴 指函數本身使用到自己 ::: 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