Max Coding blog

基礎演算法(Algorithm)-C++

C++ algorithm
2021/08/28

前言

學到演算法這邊終於知道題目不是能解出來就好，要解的簡潔，什麼意思呢？就是說不是答案對就可以了，要有效率，執行速度能快就快，使用空間能小就小，這樣的觀念打破我一直以來的想法，也對程式越來越有興趣了，程式啊程式，你是多麼神秘且講道理啊！！！！ ## 貪婪演算法 貪婪演算法就是做眼前最佳的動作，也就是局部解，但是到最後不見得是最好的動作，以下舉一個找零錢的例子。 通常找顧客零錢都是先將面額大的給顧客，再將較第二大的面額給顧客，依序這樣下去，直到不能找為止，所以貪婪演算法就是運用這個想法。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int main(){
    int cash[10],n;
    cash[0] = 1;
    cash[1] = 5;
    cash[2] = 10;
    cash[3] = 50;
    cash[4] = 100;
    cash[5] = 500;
    cash[6] = 1000;
    cin >> n;
    cout << n << "=";
    for(int i = 6;i >= 0;i--){
        if(n >= cash[i]){
            cout << cash[i] << "*" << n/cash[i] << " ";
            n = n%cash[i];
        }
    }

    return 0;
}

貪婪演算法-最小生成樹(Minimum spanning trees)MST

其實tree是一種資料結構，但我配合greedy來講。 Tree的特性，必連通，但不能有cycle。 MST的定義就是生成出來的樹，他的邊的總和最小的。 英文版定義（由於翻譯成中文可能無法清楚表達他的含義，所以這邊使用別人的定義，原文是英文）： Definition: G = (V,E):weighted connected undirected graph * Spanning tree : S = (V,T),T ⊆ E,undirected tree * Minimum spanning tree(MST) : a spanning tree with the smallest total weight. 中文定義： 1. 樹(tree):一個無向連通非環狀圖(acyclic,connected, undirected graph) 2. 有根樹(rooted tree):以某個頂點為跟的樹（獨立於樹之外的頂點不能作為根）。因此有根樹也被直接稱為樹。 3. 生成樹(spanning tree):包含圖中所有頂點且符合樹的定義的連通子圖。 4. 最小生成樹(minimum spanning tree):即具有最小的權重的生成樹。 ## 用貪婪演算法解最小生成樹 

1
2
3
4
5
6
7
8
F = empty set
while(當問題未得解){
	找出問題區域最佳解的方式找出一個邊;
	if(選出來的邊不會使F產生任何cycle)
		將邊加入F中;
	if(答案是生成樹)
		此問題得解;
}
## Kruskal algorithm 先將所有邊拿掉，接著再依序找小邊，並隨時確保他不會形成一個cycle。 ## Prim algorithm 先挑一個點，然後找那個頂點連接的邊哪個最小，然後當所有的點都選到後就結束了。 ## 排序演算法 ### bubble sort 泡沫排序法是一個很直觀且簡易的一種排序算法，以升冪從未排序的第一筆開始，第一筆資料和第二筆做交換，如果第二筆大於第三筆，就將第二筆和第三筆交換，以此類推。 Time complexity :O(n^2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int counts;
    while(cin >> counts){
        vector<int> vec;
        int temp;
        for(int i = 0;i < counts;i++){
            cin >> temp;
            vec.push_back(temp);
        }
        for(int i = 0;i < counts;i++){
            for(int k = 0;k < counts-1;k++){
                if(vec[k] > vec[k+1])
                    swap(vec[k],vec[k+1]);
            }
        }
        for(int i = 0 ;i < counts;i++){
            cout << vec[i] << " ";
        }
        cout << endl;
    }
    return 0;
}
## merge sort merge sort 是一個運用divide and conquer 演算法的演算法，先將問題分為數個子問題，最後再結合起來就會是問題的答案了。 time complexity : O(nlogn) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
using namespace std;
long long int infinity = 999999999;
void merge(vector<int> &vec,int first,int mid,int last){
    vector<int> left_area(vec.begin()+first,vec.begin()+mid+1);
    vector<int> right_area(vec.begin()+mid+1,vec.begin()+last+1);
    left_area.emplace(left_area.end(),infinity);
    right_area.emplace(right_area.end(),infinity);
    int left_idx = 0,right_idx = 0;
    for(int i = first;i <= last;i++){
        if(left_area[left_idx] <= right_area[right_idx]){
            vec[i] = left_area[left_idx];
            left_idx++;
        }
        else{
            vec[i] = right_area[right_idx];
            right_idx++;
        }
    }
}
void merge_sort(vector<int> &vec,int first,int last){
    if(first < last){
        int mid = (first+last)/2;
        merge_sort(vec,first,mid);
        merge_sort(vec,mid+1,last);
        merge(vec,first,mid,last);
    }
}
int main(){
    vector<int> vec{48,23,19,34,65,20,3};
    cout << "original : ";
    for(int i = 0;i < vec.size();i++)
        cout << vec[i] << " ";
    cout << endl;
    cout << "After merge sort : ";
    merge_sort(vec,0,7);
    for(int i = 0;i < vec.size();i++)
        cout << vec[i] << " ";

    return 0;
}
首先使用vector來儲存資料，接著把vector加入merge_sort()函式，merge_sort主要運行遞迴，前面有說merge_sort是將大問題分為數個子問題，而此遞迴就是為了實現此方式，首先將矩陣分為兩個，各自再分為兩個，一直分到不能分為止，此時停止遞迴，接著合併各個矩陣，在第6行和第7行是vector的constructor，將兩個矩陣分別放入left_area和right_area，然後用emplace把一個極大的數字插在他們的最後的地方，然後開始比較，兩個不同的vector用兩個不同的指標，把小的依序擺下來，擺好後在和下一個比，直到完成排序，這樣就完成merge_sort了。 ## quick sort quick sort是一個運用divide and conquer 演算法的演算法，而隸屬於algorithm這個函式庫中有一個函式sort()就是利用quick sort，這是別人寫好的，可以接利用，首先先介紹這個函式，這個函式可加入三個參數，第一個參數是陣列或向量的第一個值，而第二個值是陣列或向量的最後一個值，第三個參數可有可無，是放入自訂函式，決定升冪或降冪，或當陣列或向量並不純，而是有和結構做連接，所以此時適合加入第三個參數，幫助解決。 time complexity : O(nlogn) 但是worst case的時候是O(n^2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
struct data{
    int a;
    int b;
};
bool cmp(data x,data y){
    if(x.a == y.a) return x.b < y.b;
    else return -1;
}
int main(){
    data foo[10];
    srand(time(NULL));
    for(int j = 0;j < 10;j++)
        foo[j].a = 0;
    for(int i = 0;i < 10;i++){
        foo[i].b = rand()%1000;
    }
    sort(foo,foo+10,cmp);//此處加入第三個參數
    for(int i = 0;i < 10;i++)
        cout << foo[i].b << " ";

    return 0;
}
但是不能只會用別人的東西，自己也要會寫，所以接下來要介紹quick sort是如何運行的。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
void quick_sort(int *arr,int front_,int end_);
void swap_(int *a,int *b);
int partition_(int *arr,int front_,int end_);
int main(){
    int arr[10] = {3,5,7,2,13,21,6,1};
    for(int i = 0;i < 8;i++)
        cout << arr[i] << " ";
    cout << endl;
    quick_sort(arr,0,7);
    for(int i = 0;i < 8;i++)
        cout << arr[i] << " ";

    return 0;
}
void swap_(int *a,int *b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
void quick_sort(int *arr,int front_,int end_){
    if(front_ < end_){
        int pivot = partition_(arr,front_,end_);
        quick_sort(arr,pivot+1,end_);
        quick_sort(arr,front_,pivot-1);
    }
}
int partition_(int *arr,int front_,int end_){
    int pivot = arr[end_];
    int i = front_-1;
    for(int j = front_;j < end_;j++){
        if(arr[j] < pivot){//to control ascending power and Descending powers
            i++;
            swap_(&arr[i],&arr[j]);
        }
    }
    i++;
    swap_(&arr[i],&arr[end_]);
    return i;
}
quick sort有一個很重要的東西，就是pivot，他就像一個標準，每個值要和他比較，在他左邊的值是比他小的，在他右邊是比他大的，保持這個特性一直做下去，而我們的pivot會採用陣列裡最後一個值，沒有強制規定要找哪一個，而在partition_裡的迴圈作用是一個一個做比較，最後再將pivot插入中間，以得到在他左邊的值是比他小的，在他右邊是比他大的。而quick_sort函式裡是一個遞迴，一直重複直到無法再分到更小的，這邊和merge sort有幾分相似。

總結

我覺得排序演算法是一堂很重要的課，也是進入演算法世界的第一把鑰匙，表面上在排序，但實際上有許多的觀念在背後，其實排序演算法有很多，但我這邊就舉三個例子即可，學玩排序後就來學搜尋吧！ ## 二分搜尋法(binary search) 配合圖片二分搜會學的比較輕鬆，在進行二分搜前可以先畫一個\(1\) * \(n\)的矩陣來幫助理解 以上為一個\(1\)*\(9\)的矩陣，每個格子中儲存一個數字，切記在進行二分搜得時候要先把數字排好，我習慣由小排到大，而接下來就可以進行搜尋了。 假設我們要搜尋的目標是14我們先將矩陣的數量除二，可得目前index值為(0+8)/2 = 4，而index[4]的位置並非我們要找的數值，且index[4] = 9小於我們的目標14所以我們直接拋棄尋找小於9的數字，直接往以9為中心的右側繼續尋找下一個，一直重複此動作即可尋找到14的位置。

我們之所以要使用binary search 而不用linear search是因為linear search的time complexity 是O(n) 而binary search 的 time complexity 是O(logn)比較快。

程式碼: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
int Binary_search(int * arr,const int target,int left,int right);
int main(){
    int arr[10] = {3,19,23,8,14,6,9,1,20};//1,3,6,8,9,14,19,20,23
    const int target = 14;
    sort(arr,arr+9);
    int position = Binary_search(arr,target,0,8);
    cout << position+1 << endl;

    return 0;
}
int Binary_search(int * arr,const int target,int left,int right){
    while(left < right){
        int mid = (left+right)/2;
        if(arr[mid] == target) return mid;
        else if(arr[mid] > target) right = mid;
        else if(arr[mid] < target) left = mid+1;
    }
}
## 圖論 ### dfs 深度優先搜尋法 以下為鄰接矩陣的作法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
int vertex,edge;
bool visited[10] = {false};
int maps[10][10] = {{0}};
void dfs(int node);
void print();
int main(){
    cin >> vertex >> edge;
    int tmp1,tmp2;
    for(int i = 0;i < edge;i++){
        cin >> tmp1 >> tmp2;
        maps[tmp1-1][tmp2-1] = maps[tmp2-1][tmp1-1] = 1;
    }
    print();
    cout << endl;
    for(int i = 0;i < vertex;i++){
        if(!visited[i]) dfs(i);
    }
    return 0;
}
void dfs(int node){
    cout << node+1 << " ";
    visited[node] = true;
    for(int i = 0;i < edge;i++){
        if(!visited[i] && maps[node][i] == 1) dfs(i);
    }
}
void print(){
    for(int i = 0;i < vertex;i++){
        for(int j = 0;j < vertex;j++){
            cout << maps[i][j] << " ";
        }
        cout << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#define N 50
#define M 50
using namespace std;
int graph[N][M];
int visited[N];
void dfs(int n);
int main(){
    fill(visited,visited+N,0);
    int n,m;
    cin >> n >> m;
    int tmp1,tmp2;
    for(int i = 0;i < n;i++){
        cin >> tmp1 >> tmp2;
        graph[tmp1][tmp2] = 1;
        graph[tmp2][tmp1] = 1;
    }
    cout << endl;
    visited[1] = 1;
    dfs(1);

    return 0;
}
void dfs(int n){
    cout << n << " ";
    for(int i = 1;i <= 6;i++){
        if(graph[n][i] == 1 && visited[i] == 0){
            visited[i] = 1;
            dfs(i);
        }
    }
}
以上兩種的寫法都是dfs，只是有一些部分不太一樣。 我們程式講解就拿第二個為例子，由於我們是鄰接矩陣，所以建立一個二維陣列來存放資料比較清楚，再建立一個陣列存放node是否被走訪過，那由於此圖是undirected graph(無向圖)，所以假設1連到2，就等於2連到1，接著進入dfs()，我們使用一個迴圈去跑，如果沒被走過且看我們傳入的n有相連的話就將他走訪遞迴，讓走訪過程中走到不能再走後就回傳，雖然我們設的是void，但可以想成回傳一個NULL。 ### bfs 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstring>
#define vertex 6
#define edge 7
using namespace std;
bool visited[vertex];
int line[edge][2];
void bfs(int n){
    int que[100];
    visited[n] = true;
    int last = -1,first = -1;
    que[++last] = n;
    while(first < last){
        int pop = que[++first];
        cout << pop << " ";
        for(int i = 0;i < vertex;i++){
            if(visited[i] == 0 && line[pop][i] == 1){
                que[++last] = i;
                visited[i] = true;
            }
        }
    }
}
int main(){
    fill(visited,visited+vertex,0);
    memset(line,0,sizeof(line));
    for(int i = 0;i < edge;i++){
        int tmp1,tmp2;
        cin >> tmp1 >> tmp2;
        line[tmp1][tmp2] = line[tmp2][tmp1] = 1;
    }
    for(int i = 0;i < vertex;i++){
        if(!visited[i]){
            bfs(i);
        }
    }


    return 0;
}
首先來看廣度優先搜尋法和深度優先搜尋法的差異: dfs是用在深度 > 廣度，而bfs是用在廣度 > 深度，所以在做bfs時要注意，我們不是把路走訪到不能走為止，而是走到一個node就要將node同一階層的人都走過，再繼續往下走。 由於dfs和bfs有一些地方相同，所以相似的地方我就不多做贅述了，在bfs()裡我們建立一個佇列(queue)，其實這邊也可以使用STL的queue，但這裡我還是選擇製作一個陣列做撰寫，這邊還有一個地方比較特別的就是我們建立兩個變數分別稱為first和last，代表我們對queue的index，這也是我為甚麼不使用STL的queue，因為對於初學，有index的程式比較好理解，我們先將傳入的n加入佇列裡，接著進入迴圈，這裡的條件是說如果last == first 的時候代表佇列裡已經沒有元素了，所以此時就跳出迴圈，那迴圈的第一個部分是說我們將已經在佇列最前面的元素輸出，也就是pop，剩下的就和dfs類似了。 ## 動態規劃(dynamic programming) 終於到了我心中的大大大大魔王，這是我目前學到最難做最難想的演算法，運用到的許多遞迴的觀念還有分治演算法的概念，所以對遞迴和分治法要夠熟來解決dp才能得心應手。 但dp的難度真的太高，所以這邊只會紀錄最基礎的部分。 一般如果要進行費氏數列的運算會利用遞迴做，f(n-1)+f(n-2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int f(int n){
    if(n == 1 || n == 2) return 1;
    return f(n-1)+f(n-2);
}
int main(){
    for(int i = 1;i <= 10;i++){
        cout << f(i) << " ";
    }
    cout << endl;

    return 0;
}
雖然此方法可行，但是當數字過大的時候他就沒辦法運算，此時就要用到動態規劃法，這樣可以算到很大的數字。 
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main(){
    long long int f[100];
    f[0] = 1;
    f[1] = 1;
    for(int i = 2;i < 80;i++)
        f[i] = f[i-1]+f[i-2];
    cout << f[69] << endl;//ouput = 190392490709135

    return 0;
}

by 中和高中 吳振榮
CATALOG
  1. 1. 前言
  2. 2. 貪婪演算法-最小生成樹(Minimum spanning trees)MST
  3. 3. 總結
    1. 3.0.0.1. by 中和高中 吳振榮
Total : 31
2023
2021
C++ OOP CSS web dev HTML Linux Pytorch Machine Learning TensorFlow2 Python Scikit Learn TensorFlow1 Math theorem algorithm Data structure Transfer Learning APCS TensorFlow