演算法

c++可以說是c的加強版，其實，最大的差異在於c++提供物件導向的語法，雖然物件導向是很重要的概念，但是，APCS的範圍並不包含物件導向的語法與概念。

使用c++還有一些好處，其中一個好處是有一些內建的演算法，如果是使用C的話，內建的演算法就少很多了，而且語法也比較難懂一點。

• 基礎演算法與資料結構學習筆記

排序

• 排序法比較 (動態展示)

  • 選擇、插入、氣泡排序

  • 【筆記】Sorting 排序

  • 快速排序

    • 快速排序1
    • 快速排序2
    • quick sort (c內建函數)

  • sort (c++內建函數)

    • 針對一般的陣列，只要提供排序的起點及終點，就會排序了，例如:

    sort(w, w+n);
    

    • 完整的範例

      #include <stdio.h>
      **#include <algorithm>**
      using namespace std;
      int main(){
      int n;
      int w[1000];
      int f[1000];
      freopen("c471.txt", "r", stdin);
      scanf("%d", &n);
      for (int i = 0; i < n; i++){
          scanf("%d", &w[i]);
      }
      
      **sort(w, w+n);**
      printf("%d", w[0]);
      return 0;
      }
      

    • 如果是個結構陣列，因為沒辦法判定要以哪個變數排序，就必須利用比較函數，定義比較的變數(或公式)

    **bool cmp (box a, box b){
      return a.f * b.w > b.f * a.w;
    }**
    
    sort (boxes, boxes+n, **cmp**);
    

    完整的範例:

    #include <stdio.h>
    **#include <algorithm>**
    using namespace std;
    
    struct box {
        int w;
        int f;
    };
    
    **bool cmp (box a, box b){
      return a.f * b.w > b.f * a.w;
    }**
    
    int main(){
    int n;
    
    freopen("c471.txt", "r", stdin);
    scanf("%d", &n);
    struct box boxes[n];
    for (int i = 0; i < n; i++){
        scanf("%d", &boxes[i].w);
    }
    for (int i = 0; i < n; i++){
        scanf("%d", &boxes[i].f);
    }
    
    **sort (boxes, boxes+n, cmp);**
    
    return 0;
    }
    

搜尋

• 搜尋法 (動態展示)
  • 線性搜尋
    • 就是從頭到尾一個一個比對
  • 二元搜尋 ** 重要
    • 當我們的陣列或vector已經排序，我們就可以透過二元搜尋去加快搜尋的速度，二元搜尋的概念跟利用二元樹搜尋很類似。想像，如果我們要完比大小的遊戲，數字範圍是0-9，大家一開始會猜多少? 會從0開始猜嗎? 如果猜錯了，對方會說是大或小，下個數字會怎麼猜? 這就是二元搜尋的基本概念，其實這樣的做法我們都用過，不是嗎?
    • 我們看一下觀念題，從觀念題了解這兩種搜尋法的差異
    • binary search (c內建函數)
    • binary search (c++內建函數)

觀念題

給定一整數陣列a[0]、a[1]、…、a[99]且a[k]=3k+1，以value=100 呼叫以下兩函式，假設函式f1 及f2之while 迴圈主體分別執行n1 與n2 次 (i.e, 計算if 敘述執行次數，不包含 else if 敘述)，請問n1 與n2 之值為何? 註： (low + high)/2 只取整數部分。

int f1(int a[], int value) { int r_value = -1; int i = 0; while (i < 100) { if (a[i] == value) { r_value = i; break; } i = i + 1; } return r_value; }

int f2(int a[], int value) { int r_value = -1; int low = 0, high = 99; int mid; while (low <= high) { mid = (low + high)/2; if (a[mid] == value) { r_value = mid; break; } else if (a[mid] < value) { low = mid + 1; } else { high = mid - 1; } } return r_value; }

(A) n1=33, n2=4 (B) n1=33, n2=5 (C) n1=34, n2=4 (D) n1=34, n2=5

APCS 2016年3月 第3題

a[0] = 1 a[1] = 4 … a[33]=100

low = 0, high = 99, mid =49 low = 0, high = 49, mid =24 low = 24, high = 49, mid = 36 …

下面哪組資料若依序存入陣列中，將無法直接使用二分搜尋法搜尋資料 (A) a, e, i, o, u (B) 3, 1, 4, 5, 9 (C) 10000, 0, -10000 (D) 1, 10, 10, 10, 100

APCS 2016年10月 第8題

提示: 二元搜尋法的前提是?

int A[8]={0, 2, 4, 6, 8, 10, 12, 14}; int Search(int x) { int high = 7; int low = 0; while (high > low) { int mid = (high + low)/2; if (A[mid] <= x) { low = mid + 1; } else { high = mid; } } return A[high]; }

給定一個 1x8的陣列A，A = {0, 2, 4, 6, 8, 10, 12, 14} 。上述函式Search(x) 真正目的是找到 A 之中大於 x的最小值。然而，這個函式有誤。 請問下列哪個函式呼叫可測出函式有誤？ (A) Search (-1) (B) Search (0) (C) Search (10) (D) Search (16)

APCS 2017年3月 第1題

第一次A[mid]是6

每個選項的預期答案是 (A) Search (-1) → 0 (B) Search (0) → 2 (C) Search (10) →12 (D) Search (16) → 應該沒有答案

每個選項的實際答案是 (A) Search (-1) low = 0, high = 7, mid = 3 low = 0, high = 3, mid = 1 low = 0, high = 1, mid = 0; low = 0, high = 0 回傳 A[high] (B) Search (0) (C) Search (10) (D) Search (16)

實作題

• b964 成績指標
  • APCS 2016年3月第1題
• c294 三角形辨別
  • APCS 2016年10月第1題
• c575 基地台

  • APCS 2017年3月第4題

    • 先讀入所有的資料
      • 定義變數的型態時，要注意座標範圍可能很大
    • 將服務點的座標排序

    sort(point, point+n);
    

    • 先求K為1及K為2 (範例2、範例1)

      • 如果只是單純的平分距離，範例2的答案會是對的

      cout << (point[n-1]-point[0]) / k;
      

      • 但範例1的答案只是正好一樣，那要怎麼算呢?

        • 首先，我們來看一下需要幾個基地台，我們先寫一個cover()函數，傳入一個距離，利用距離去算會需要幾個基地台。

        #include <iostream>
        #include <algorithm>
        using namespace std;
        int point[50000];
        int max_distance = 0;
        int n, k;
        
        int cover(int dis){
            int coverage = point[0]+dis;//第一個基地台可以覆蓋的範圍
            int cnt_station = 1;
            for (int i = 0; i < n; i++){
                if (point[i] > coverage){ //超出範圍
                    cnt_station ++;
                    coverage = point[i]+dis;
                }
            }
            return cnt_station;
        
        }
        
        main(){
            freopen("c575.txt", "r", stdin);
        
        cin >>n >>k;
        
        for (int i = 0; i < n; i++){
           cin>> point[i];
        }
        
        sort(point, point+n);
        for (int i = 0; i < n; i++){
           cout<< point[i] << " ";
        }
        cout << endl;
        max_distance = point[n-1] - point[0];
        for (int i = 1; i <= max_distance; i ++){
            cout << "distance "<< i <<":" <<cover(i)<<endl;
        }
        
        return 0;
        
        }
        

        ** 注意，以上程式並不是直接算出答案，老師只是讓大家看怎麼解答。

        

        從以上的計算可以看到1個基地台的最小直徑是7，2個基地台的最小直徑是3，3個基地台的最小直徑是1。

        • 試試看，如果資料如下，最小直徑是21

        5 2 5 1 2 81 60

        

        

      • 從以上的例子就會發現，當服務點跟服務點的距離比較遠的話，裡面就多很多沒必要的計算，這時候，就可以利用二元搜尋來節省計算的時間了! 想想看怎麼利用二元搜尋~

      • 第三子題的座標範圍不超過1,000,000,000，整數的範圍是-2,147,483,648(-2$^{31}$) 至 2,147,483,647，所以，可以利用整數儲存。但是，因為測資數量很大，不使用二元搜尋可能就會超過時間上限(TLE)~

• c471 物品堆疊 (Stacking)
  • APCS 2017年10月第4題
    • 這一題看似需要使用堆疊，但其實不用，別被騙了~
    • box1 = [w1, f1]、box2 = [w2, f2] 注意! 因為是拿下面的箱子會產生上面的箱子的移動成本，所以，成本不是w1 * f1!! p1 放在 p2 的上方：移動成本w1 * f2 p2 放在 p1 的上方：移動成本w2 * f1
  • 子題1，以範例一來說，先讀入w (因為f一樣，可忽略)，針對w排序後 (最重在最上面)，就是最小移動成本
  • 子題2，就需要針對移動成本進行排序

    • 要記得使用結構，這樣w跟f才會一起移動，否則會算錯~

    • 範例2排序後的結果是

      5 3 4 2 3 1

      • 5在最上面，移動5不用移動成本
      • 要移動4，要先移動5，移動2次
      • 要移動3，要先移動5、4，移動1次
      • (5) * 2 + (5+4) * 1 = 10+9
  • 子題4的N很大，程式多寫個迴圈可能就會超過時間上限(TLE)，所以，要思考一下!!