程式設計(二) Lab 3 講解

tags: lion_1082

lab3 A 部分

題目說明

根據從 file.in 讀入的資料，將最重的 5 隻牛的體重加總起來輸出

使用 fstream

1. 使用前需要在原始碼的上方加上 #include <fstream>
2. 利用 constructor 進行開檔或是利用 member function 的形式開啟檔案

open 函式的參數形式是 open(filename, open_mode)

常見的開啟模式有以下幾種：

• ios::in : 以讀取模式開啟檔案
• ios::out : 以寫入模式開啟檔案
• ios::app : 以寫入模式開啟檔案並將寫入指針移動到檔案結尾處

詳細的模式說明可以參考 ios_base::openmode - C++ Reference

如何讀取檔案？

如同使用 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 使用

簡單來說， vector 可以說是 array 的進化版
在 C++ 中，有提供許多好用的 STL ，而 Vector 就是其中一個 STL

使用方法

• 須將 #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 使用

• 要將 #include <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 部分)

lab3 B 部分

題目說明

執行 Vector and Array 投影片第 21 與 22 頁的程式碼，並依照結果分析

$O(n^2)$ 與

$O(nlogn)$ 的差異

時間複雜度

根據維基百科的敘述：

在電腦科學中，演算法的時間複雜度（Time complexity）是一個函式，它定性描述該演算法的執行時間。
[color= purple]

Insertion sort

與我們日常生活中排撲克牌的方法類似，時間複雜度為

$O(n^2)$

sort()

未有統一的實作方法，依照編譯器的不同可能有不同的實作方式
但在 C++11/14 標準裡有規範其時間複雜度為

$O(nlogn)$

執行結果

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

可以看到 insertion sort 在元素越來越多的時候，其所花費時間的上升曲線會比使用 sort 函式還來得陡，這是因為 insertion sort 在時間複雜度上屬於

$O(n^2)$

而 sort 函式根據 C++11/14 的標準，時間複雜度為

$O(nlogn)$ ，所以兩者在排序數量漸增時所需花費時間的差異就會逐漸顯現出來。

範例程式碼 (B 部分)