Coding Prep 演算法資料結構教學

歡迎加入我的 Discord 群組與我討論程式相關的問題!

加入 Discord

這部分的教學會介紹四種 APCS 考試範圍提到的演算法

排序 (sorting)

所謂的排序，就是把一串資料按照順序排好。大家之前學到的排序方法可能有：

  • Bubble Sort
  • Insertion Sort
  • Selection Sort 等

但是，其實這些排序方法的複雜度都是 O(n^2)，很多時候都是不夠快的。
在 C++ 中，標頭檔 <algorithm> 中就有包含一個 std::sort 的功能，複雜度是 O(nlogn)，非常好用！
sort 的用法就是 sort(開頭, 結尾)。其中結尾是不包含的，以下我示範陣列跟 vector 的實作方式。

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main(){
    vector <int> a = {5, 3, 4, 2, 1};
    int b[5] = {2, 4, 3, 5, 1};
    
    sort(a.begin(), a.end());
    sort(b, b+5); 
    
    cout << "a: ";
    for(int i = 0;i < 5;i++){
        cout << a[i] << " \n"[i == 4];
    }
    
    cout << "b: ";
    for(int i = 0;i < 5;i++){
        cout << b[i] << " \n"[i == 4];
    }
}

output

a:
1 2 3 4 5
b:
1 2 3 4 5

而 C++ sort 強大的地方還有你可以自定義要用甚麼方法排序，有兩種方法可以達到這個目的。第一種是寫一個 cmp function，把他當參數傳入 sort 。以下的程式碼就是我想要他從大到小排序。

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
bool cmp(int a, int b){
   return a > b;
}
int main(){
    vector <int> a = {5, 3, 4, 2, 1};
    sort(a.begin(), a.end(), cmp);
    cout << "a: ";
    for(int i = 0;i < 5;i++){
        cout << a[i] << " \n"[i == 4];
    }
}

output

a:
5 4 3 2 1

第二種方法是你自己寫一個 struct，並且告訴電腦你的 struct 大小順序是怎麼決定的。一樣可以寫一個 cmp 或者是可以直接定義你的 operator < 代表甚麼。

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
struct Point{
    int x, y;
    bool operator < (const Point &a) const {
        if(x == y) return y < a.y;
        else return x < a.x;
    }
}; 
int main(){
    vector <Point> a = {{1, 2}, {4, 3}, {1, 3}, {5, 2}, {4, 2}};
    sort(a.begin(), a.end());
    cout << "a:\n";
    for(int i = 0;i < 5;i++){
        cout << a[i].x << ' ' << a[i].y << '\n';
    }
}

output

a:
1 2
1 3
4 3
4 2
5 2

以上就是排序大概所需要的知識，請善用 cmp function，會用的話 <algorithm> 裡面的 std::sort 就很夠用了！

搜尋 (searching)

所謂搜尋，就是在很多資料裡找到你想要的資料，而在 APCS 中，我們找資料的方法主要有兩種。

  1. 線性搜尋

線性搜尋是最基本的搜尋方法，我們直接跑過整個資料，看看我們要的資料有沒有在裡面。這樣的時間複雜度會是 O(n)，其中 n 是資料的大小。

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector <int> a = {2, 4, 1, 6, 2, 6, 3, 9};
    for(int i = 0;i < a.size();i++){
        if(a[i] == target) {
            cout << "Found!\n";
            return 0;
        }
    }
    cout << "Not found...\n";
}

output

Found!

2. 二分搜尋法

上面的作法非常基本易懂，但是當資料變得太大時，一個一個跑過去看就會很花時間。於是，在這裡我們介紹第二種搜尋法。二分搜尋法只能運用在具有單調性的序列上，例如單調遞增或者單調遞減。

在有單調性的時候，我們在搜尋時可以每次從中間切開來，看看中間的值是不是我們要的，如果值太大就往左邊看，太小就往右邊看。

由於太大的話右邊的東西只會更大，所以我們要的答案一定在左邊。太小的話左邊的東西只會更小，所以答案一定在右邊。這樣我們就可以每次將看的範圍減半，複雜度就會降到 O(logn) !

以下是一個二分搜流程的示意圖。(圖片取自 【Day31】[演算法]-二分搜尋法Binary Search)

以下是實作的 code

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector <int> a = {1, 2, 2, 3, 5, 6, 9, 10};
    int target = 8;
    int l = 0, r = 7; // 範圍的左界和右界
    while(l < r) {
        int m = (l + r) / 2; // 取中間
        if(a[m] < target) l = m+1; // 答案一定在右邊
        else r = m;
    }
    cout << l << '\n';
}

output

6

以上就是二分搜的實作，最後如果沒找到要的答案的話，左界的位置就是如果存在答案應該會在的位置! 大家可以自己想想看為甚麼!

例題

而二分搜尋法除了在這種判斷一個數字有沒有出現，或是要找到位置之外，也有很多的應用。二分搜也可以用來找一個問題的答案!

範例題目: APCS 2017-0304-4基地台

題目要求我們找到最小的直徑，而透過觀察可以發現。答案具有上面提到的單調性質! 單調性值不限於只能是遞增或是遞減。假如你把這題所以有可能的從小到大直徑都列出來，然後可以符合條件的直徑用 1 表示，不能的用 0 表示，算出來大概會長得這樣

000000000001111111111

而這個結果也很直覺，因為當你直徑已經可以蓋到所有的基地台，更大的直徑也一定可以滿足。在這題我們希望找到最小的那個直徑，也就是 0 跟 1 的分界點，我們就可以用二分搜找到那個分界點！

因為假如我們選到 1 ，那右邊一定都不是答案 (現在這個比右邊都小也可以滿足條件，所以這個答案一定比較好)，選到 0 左邊一定也不是答案 (現在已經太小了左邊只會更小)。有沒有發現這跟上面的例子很像！

在二分搜時，你可以想像有一個只回傳 0 跟 1 的 function f(x) 。而這個 f(x) 會有一個分界點，在分界點以上都回傳 1，以下都回傳 0。我們就可以用二分搜找到他的分界點。在這題的 f(x) 就是要檢查一個直徑可不可以覆蓋全部的基地台。

在這種要求最大 X 最小，或者是最小 X 最大的答案很有可能都是要用到二分搜單調性的技巧喔！

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n, k;
    cin >> n >> k;
    vector <int> a(n);
    for(int i = 0;i < n;i++){
        a[i];
    }
    sort(a.begin(), a.end());
    int l = 0, r = 1e9; //　左右界
    while(l < r){
        int m = (l+r)/2;
        int cur = -1, cnt = 0;
        while(cur < n-1){
            int new_cur = cur+1;　
            cnt++;
            while(new_cur + 1 < n && a[new_cur+1] <= a[cur+1] + m)
                new_cur++;
            cur = new_cur;
        }
        if(cnt <= k)  // 滿足條件！先保留這個看看左邊有沒有更小的
            r = m;
        else 
            l = m+1; // 不滿足，這個一定不行，從下一個開始往右邊看
    }
    printf("%d\n", l);
}

還有一點要注意的是在二分搜時，如果邊界沒有設定好有可能會發生無窮迴圈的情況。我上面的寫法是閉區間的寫法，基本上照著寫不會錯。想要知道其他種寫法或是已經遇到無窮迴圈問題的 (QAQ) 可以到這邊看看喔！
我也推薦都用一種寫法就好，比較熟悉也比較不會出錯。

資料參考：資訊之芽講義 (大推！！！

Blog at WordPress.com.