# 程式設計(二) Lab 3 講解

###### tags: `lion_1082`

## lab3 A 部分
### 題目說明
> 根據從 `file.in` 讀入的資料，將最重的 5 隻牛的體重加總起來輸出

### 使用 [fstream](http://cplusplus.com/reference/fstream/fstream/)
1. 使用前需要在原始碼的上方加上 `#include <fstream>`
2. 利用 `constructor` 進行開檔或是利用 `member function` 的形式開啟檔案

`open` 函式的[參數形式](http://cplusplus.com/reference/fstream/fstream/open/)是 `open(filename, open_mode)`

常見的開啟模式有以下幾種：
- `ios::in` : 以讀取模式開啟檔案
- `ios::out` : 以寫入模式開啟檔案
- `ios::app` : 以寫入模式開啟檔案並將寫入指針移動到檔案結尾處

詳細的模式說明可以參考 [ios_base::openmode - C++ Reference](http://cplusplus.com/reference/ios/ios_base/openmode/)

### 如何讀取檔案？
如同使用 `cin` 與 `cout` 一樣

- 如果你是以 `ios::in` 開啟檔案的話，可以把你所宣告的 fstream 變數當作 `cin` 來讀入資料

#include <iostream>
#include <fstream>
using namespace std;

int main() {
    fstream ff; // 宣告 fstream 變數
    int b;
    ff.open('input.txt', ios::in); // 利用 open 函式開啟檔案
    ff >> b; // 從 ff 讀入資料至 b 變數
    cout << b << endl;
    ff.close(); // 關閉檔案
    return 0;
}

### [vector](http://www.cplusplus.com/reference/vector/vector/) 使用
簡單來說， vector 可以說是 array 的進化版
在 C++ 中，有提供許多好用的 [STL](https://www.runoob.com/cplusplus/cpp-stl-tutorial.html) ，而 Vector 就是其中一個 [STL](https://www.runoob.com/cplusplus/cpp-stl-tutorial.html)

#### 使用方法
- 須將 `#include <vector>` 加入程式碼中
- 宣告的時候要告訴編譯器這個 Vector 所要儲存的**元素的資料型態**
- 使用 `push_back` 將元素加入 Vector
- 可以使用 `[]` 或是 `at()` 這個成員函式來存取其中的特定元素
- 使用 `size()` 取得 Vector 的大小

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector <int> aa; // 在 < > 中告知元素的資料型態

    for (int i = 0; i < 10; i++) {
        aa.push_back(i); // 將變數 i 的數值存進 aa 中
    }
    
    // now 0 ~ 9 are in the vector named `aa`
    cout << aa[3] << endl; // output: 3
    cout << aa.at(3) << endl; // output: 3

    cout << aa.size() << endl; // output: 10
    return 0;
}

### [sort](http://www.cplusplus.com/reference/algorithm/sort/) 使用
- 要將 `#include <algorithm>` 加進程式碼裡
- `sort` 函式的[參數結構](http://www.cplusplus.com/reference/algorithm/sort/) ： `sort(begin_pointer, end_pointer, function_pointer)`
- `sort` 可以根據你所提供的 function 來改變排序的方式
- `sort` 可以使用在許多的資料型態上(如 array, vector, string 等等)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector <int> aa;
    aa.push_back(0);
    aa.push_back(3);
    aa.push_back(2);
    aa.push_back(5);
    // now aa is [0, 3, 2, 5]

    sort(aa.begin(), aa.end());
    // the result is [0, 2, 3, 5]
    return 0;
}

搭配傳入比較函數可以做不同的變化

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 定義比較函式
bool cmp(const int a, const int b) {
    return a > b;
}

int main() {
    vector <int> aa;
    aa.push_back(0);
    aa.push_back(3);
    aa.push_back(2);
    aa.push_back(5);

    // 利用比較函式更動排序
    sort(aa.begin(), aa.end(), cmp);
    // now the result is [5, 3, 2, 0]
    return 0;
}

### [範例程式碼 (A 部分)](https://github.com/OscarShiang/pd2_lab3/blob/master/lab3_a.cpp)

## lab3 B 部分
### 題目說明
> 執行 `Vector and Array` 投影片第 21 與 22 頁的程式碼，並依照結果分析 $O(n^2)$ 與 $O(n\ log\ n)$ 的差異

### 時間複雜度
根據[維基百科](https://en.wikipedia.org/wiki/Time_complexity)的敘述：
> 在電腦科學中，演算法的時間複雜度（Time complexity）是一個函式，它定性描述該演算法的執行時間。
> [color= purple]

### [Insertion sort](https://en.wikipedia.org/wiki/Insertion_sort)
與我們日常生活中排撲克牌的方法類似，時間複雜度為 $O(n^2)$

### [sort()](https://en.wikipedia.org/wiki/Sort_(C%2B%2B))
未有統一的實作方法，依照編譯器的不同可能有不同的實作方式
但在 C++11/14 標準裡有規範其時間複雜度為 $O(n\ log\ n)$

### 執行結果
利用測量得到的執行時間畫出下圖：


可以看到 [insertion sort](https://zh.wikipedia.org/zh-tw/插入排序) 在元素越來越多的時候，其所花費時間的上升曲線會比使用 sort 函式還來得陡，這是因為 [insertion sort](https://zh.wikipedia.org/zh-tw/插入排序) 在時間複雜度上屬於 $O(n^2)$

而 sort 函式根據 C++11/14 的標準，時間複雜度為 $O(n\ log\ n)$ ，所以兩者在排序數量漸增時所需花費時間的差異就會逐漸顯現出來。

### [範例程式碼 (B 部分)](https://github.com/OscarShiang/pd2_lab3/blob/master/lab3_b.cpp)