大衞的筆記

筆記說明

此筆記用途在於台北科技大學資訊與財金管理系大二下管理作業系統作業紀錄
並非所有人都適用，此為老師所給予的題目。
這是個人心得的筆記，可能不太適用會未來的學生

（請閱讀W12_趣吧-網路共享旅遊平台）

筆記說明

此筆記用途在於台北科技大學資訊與財金管理系大二下管理作業系統作業紀錄
並非所有人都適用，此為老師所給予的題目。
這是個人心得的筆記，可能不太適用會未來的學生

（請閱讀W11_宸訊科技-開放政府資料打造精準農場決策）

筆記說明

此筆記用途在於台北科技大學通識大二音樂欣賞心得－看見德沃札克‧聽見世紀
並非所有人都適用，我非音樂專長，並不了解音樂。
這是心得，可能不太適用會未來的學生

由於是我自己進行心得，並不一定全部都是正確，只是個人想法。

筆記說明

此筆記用途在於台北科技大學資訊與財金管理系大二下統計學重點整理
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是觀看影片心得後的筆記，老師上課可能不太適用會忘記抄到

題目大意

在 2100 年，電變得非常昂貴，電力公司的累進費率如下

• 1~10CHw 2元
• 101~10000 3元
• 10001~1000000 5元
• 1000000 7元

電力公司為了賺更多錢想出一種方法，電力公司會給你 A、B 兩個數字，其中

• A 是你的用電量與鄰居用電量的總和，如果合在一起的電費帳單
• B 是你的電費與鄰居電費的差額

如果想知道自己的電費，則必須付給電力公司計算費，但你想要省下這筆錢，所以來寫程式計算八！
我們可以保證的是，我們一定比鄰居的用電量還少！
注意：在這題中，每組題目都答案只會有一組解。不必擔心多組解問題

題目連結

題目大意

我有一台很老的手機，他的 RAM 並不大，最近我們遇上了 RAM 用滿的問題，我們現在必須刪除一些電話紀錄，但有一些規則要遵守

• 最後一次電話紀錄一定是今年的紀錄
• 格式為 mm:dd:HH:MM phone +\-，前面為時間，電話名稱，是否為重要紀錄
• 我們只能夠刪除非重要紀錄
• 手機並不會記錄年份，因此我們判斷年份是使用相對時間，也就是如果前一筆的時間 < 下一筆的時間，我們可以定義這兩筆資料在同年份；如果前一筆的時間 >= 下一筆的時間 我們則定義這兩筆資料的年份不一樣，前一筆的資料年份比較遠、後一筆資料年份比較近。
• 我們可以透過上一點來判斷年份，也就是每年至少都要用一筆資料。

請告訴我們最少需要保存幾個資料，就可以將重要資料全部保存並且可以判斷每通紀錄的年份。

題目連結

重點觀念

• 動態規劃的時機 (當資料並不能延續狀態，而是會需要前面資料輔助時就用動態規劃)
• 了解時間可以用字串比較

分析

這題是我認為算是非常麻煩的問題，我學習他花了將近 4 小時。

由於我們要保存最少的資料，但完整性、一樣能辨識年份，我們主要會遇到一些困難點

• 找出最後一年的重要紀錄，如果沒有就直接隨便找一筆紀錄
• 假如兩筆重要紀錄分別是 2001, 2003 年，那我們要留下 2002 的一筆不重要紀錄
• 舉例如下，那我們是不是這三筆資料都必須留下，否則年份辨識不正確

  1 2 3

  01:10:11 1234 + 01:02:23 2345 - 01:12:11 3456 +

• 所有的重要紀錄都必須被留下

根據這些困難點，會發現如果我們使用 greedy 會很難寫，因為例如第三點的情況，我們的 greedy 就必須根據過去資料去判斷，如果第一筆資料與第二筆資料中間又塞入很多的非重要紀錄那就更麻煩了。

因此這邊我們就使用可以提取過去資料與當前資料判斷的動態規劃。

主要的動態規劃則是

• dp[i] 保留至第 i 個紀錄中最少要保存幾個紀錄
• 在重要紀錄中的那些不重要紀錄我只紀錄一筆，dp[i] = min(dp[i], dp[j]+1、i < j < n，j 表示同年份的資料，如果直接提取 dp[j]+1，+1 則是紀錄 i
• 如果碰到重要紀錄，則直接跳出 for j 迴圈，因為重要紀錄不可省略

主要架構如上述所說，如果有些不清楚則建議查看下方題目程式碼

參考連結

Uva11052 - Economic phone calls by txya900619

心得

這題好難QQQ，而且好複雜！ 我原本是想要用 greedy 去做，做到一半才發現第三點用 greedy 去做並不好做。

但是也沒有想到 dp 要怎麼做比較好，就看力瑋的程式碼，不斷思考怎麼運作，後來詢問力瑋程式碼意思才逐漸開竅。

能想出這份程式碼的人真的太聰明了，我的缺點是遇到太多大問題時不擅長拆解，但我擅長將小問題解決，可能跟我的個性有關吧，喜歡注重細節，但常常忽略大局。

總之，中庸之道我也需要攝取攝取。
但我想要成為一位優秀的人，住在漂亮的房子、給小孩好的教育，幸福的人生。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 1020;
int n, dp[MAXN];

struct record{ //用於記錄每筆資訊
    string time, phone, mark;
    int year;

    //constructor 
    record(string _time, string _phone, string _mark, int _year){
        time = _time;
        phone = _phone;
        mark = _mark;
        year = _year;
    };
    record(): time(""), phone(""), mark(""), year(0){} //一開 year 始預設為 0

};
deque<record> info; //用於紀錄題目每筆紀錄

void debug(){ //debug 無意義
    for(int i = 0; i < n; i++){
        cout << info[i].time << ' ' << info[i].phone << ' ' << info[i].mark << ' ' << info[i].year << '\n';
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> n && n){ //輸入資料
        string time, phone, mark;
        info.clear(); //清空，避免影響到其他測資
        for(int i = 0; i < n; i++){ //輸入資料
            cin >> time >> phone >> mark;
            info.push_back( record(time, phone, mark, 0));
        }

        int year = 0; //先對題目的資料做辨識年份
        for(int i = 1; i < n; i++){
            if(info[i].time <= info[i-1].time) info[i].year = ++year; //年份不同， year 因此加一
            else info[i].year = year;
        }

        //debug();

        //first_mark 為年份最久的重要記錄，因為在遠的紀錄我們不須留下
        // flag 判斷是否已經讀取到年份最新的重要紀錄
        //last_mark 年份最新的重要紀錄
        int first_mark = n, flag = 1, last_mark;
        for(int i = n-1; i >= 0; i--){
            if(info[i].mark == "+") first_mark = i; //最後一次讀取就是年份最久的重要紀錄

            //我們必須把最新的年份直到出現今年的重要紀錄時都讓 dp[i] = 1，
            //因為這些紀錄，我們只需要紀錄一筆即可
            dp[i] = flag && info[i].year == year ? 1 : n-i; 
            if(flag && (info[i].mark == "+" || info[i].year != year)){ //更新最近紀錄
                flag = 0;
                last_mark = i;
            }

        }

        //dp 動態規劃，由最近年份至最遠年份
        for(int i = last_mark; i >= first_mark; i--){
            for(int j = i+1; j < n; j++){ //不斷的往最近年份推
                //由於我們動態規劃的核心是想要做成 重要紀錄、一筆非重要紀錄、重要紀錄
                //重要紀錄、非重要紀錄，視為一個區塊

                //但中間的一筆非重要紀錄，不一定只有一筆，所以我們就透過下方 if 來 dp
                //我們選擇*哪一個*非重要紀錄可以讓我們的 dp[i] 最小，下方的 dp[j] 則是上一個區塊，我們從上一個區塊中哪一個 dp[j] 可以使 dp[i] 最小

                //如果年份相同 or (前一年的資料，但離第 i 份資料不差超過一年)
                if(info[i].year == info[j].year || \
                   (info[i].year + 1 == info[j].year && info[i].time >= info[j].time))
                    //判斷 dp[i] 的資料是否比較少 or 省略 j~i 的紀錄，直接 dp[j]+1 誰少
                    dp[i] = min(dp[i], dp[j]+1); 
                else break; //當前區塊結束，跳出迴圈，原因是並非同區塊的資料

                if(info[j].mark == "+") break; //當前區塊結束，跳出迴圈，原因是遇到重要紀錄
            }
        }

        //for(int i = 0; i < n; i++) cout << dp[i] << ' ';
        //cout << '\n';
        cout << dp[first_mark] << '\n'; //輸出保留至第一個紀錄中最少要保存幾個紀錄
    }


    return 0;
}

Insertion sort 插入排序 介紹與實作原理

插入排序是最簡單的一種排序法之一，以遞減排序為例。

• 先給定一陣列，index 1 是最大，之後的陣列數值遞減
• 透過雙重迴圈
  • 第一層迴圈，決定第 i 大的位置的數字
  • 第二層迴圈，判斷從第 i 以後的的位置，哪個數字最大就放置後面

時間複查度為 \(O(n^2)\)，雖然不實用，但對初學者直觀

quick sort 快速排序 介紹與實作原理

快速排序顧名思義就是快的排序嘛XD。平均時間複雜度為 \(O(n log n\)，算是平常大家會用的演算法之一

實作原理如下：

• 定義 L 與 R，分別是當前數列的最左邊 index 與最右邊的 index
• standard 為每次 quick_sort 的第一值，每個人可以定義如何選擇此數字。
  • 定義：x 為數值，數堆為 standard 左 or 右 邊的數值
  • 我們主要是想讓陣列從原本的 standard x x x x x x，透過程式碼運算後改成 x x x standard x x x，再讓 standard 的左右邊再進行一次 quick_sort。
  • 而我們交換的方式就是使用兩個指針 L and R，從 L 開始不斷往右找直到找出第一個值比 standard 還大；從 R 開始不斷往左找直到找出第一個值比 standard 還大
  • 找到後進行交換，之後重複上一點，直到 L、R 指針相遇
  • 其中 standard 的左邊一定比 standard 還小，standard 的右邊一定比 standard 還大
  • 因此要找出最適合此排序的 standard 會讓排序變得更輕鬆，否則如果選出過大的 standard 會使的分好的兩堆數量過於偏頗，如： ```x x x x x standard x ``，
• 之後將 standard 隔開的兩數堆在進行 quick_sort，直到 standard 的左右沒辦法在分堆(遇到邊界)

合併排序 merge sort 介紹與實作原理

合併排序主要是透過 divide 的方式將每一個數列不斷分割成兩數堆(將數列進行分割)，平均時間複雜度為 \(O(n log n\)，是目前時間穩定、效率優質的演算法之一。
也是目前大家會選擇的排序演算法之一。

實作原理如下：

• 以下舉例是由小到大
• 準備一個暫存的數列 temp
• 先不斷進行遞迴，將數列分割成兩個子數列
• 處理程序：
  • 如果不能夠再分割，直接回傳數字
  • 將先前遞迴好的兩子數列，定義 A、B，分別給於這兩個子數列一個指針，定義 start_l、start_r
  • 將 start_l、start_r 指針指定的數字進行比較，如果 start_l 比較小就放入 temp，並將 start_;+1，反之 start_r 比較小就反入 temp，並將 start_r+1，
  • 上面此點主要是將兩個已經排序好的子數列，再依照順序放入 temp 中，因為我們可以知道 A、B 一開始一定是最小的數值，後面都是更大的數值，所以我們可以透過此操作來進行優化
  • 如果已經有一邊的子數列用完，而另一邊沒有用完，則將剩下的另一邊依照順序放入 temp
  • 之後將 temp 的數列放回原本的數列

最後就可以輸出答案！

Josephus problem 約瑟夫問題介紹

約瑟夫問題是一個非常黑暗的問題XD，主要是殘兵們不想被對方軍團俘虜，而想出一種自殺方式，其內容大概如下

• 全部人圍成一個圓圈，編號 \(1,2,3,…,n\)
• 定義一個數字 \(k\)，只要數到第 k 個數字，那麼那個人就自殺。
• 接下來，從死掉的那個人開始在數 k 個數字，再來第 \(2k\) 的人自殺。
• 不斷數著 k、不斷地自殺，不斷循環，直到最後只剩下一個人為止。

而我們的主角 Josephus 則不想要自殺，於是他必須找到一個位置，並且是最後剩下的那個人。

表達大致上的意思，並沒有全部完整表達。

下方我的證明可能並沒有很好閱讀，因此不懂的讀者可以參考约瑟夫环——公式法（递推公式） by 陈浅墨