演算法期末專案V2

# 演算法期末報告主題：APCS 解題，以線段覆蓋長度為例指導教授：杜海倫報告人：蔡紹文簡報URL: https://hackmd.io/@jose168/HJ6GH3RC_ YouTube:https://youtu.be/pQ5rYrsCXuM --- ## 解線段覆蓋長度 :::info 1. 題目參考: https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/10/APCS-%E5%AF%A6%E4%BD%9C%E9%A1%8C-2016.03.05.pdf 2. 使用語言: C++、Python 3. 開發工具(IDE) : CodeBlocks 20.03 4. 整合單元: 迴圈、陣列、結構、STL、排序等 ::: --- ## 問題描述 :::info 1. 給定**一維座標上一些線段**，求這些**線段所覆蓋的長度**，注意，**重疊的部分只能算一次**。 2. 例如給定三個線段：(5, 6)、(1, 2)、(4, 8)、和(7, 9)，如下圖，線段覆蓋長度為6。 ::: ![](https://i.imgur.com/wqcPsQ8.png) ---- ## 輸入格式 :::info 1. 第一列是一個正整數 N，表示此測試案例有 N 個線段。 2. 接著的 N 列每一列是一個線段的開始端點座標和結束端點座標整數值，開始端點座標值小於等於結束端點座標值，兩者之間以一個空格區隔。 ::: ## 輸出格式 :::info **輸出其總覆蓋的長度** ::: ---- ## 範例一：輸入與輸出說明 1. 輸入 ![](https://i.imgur.com/iYu9jcC.png) 2. 輸出 ![](https://i.imgur.com/mlZ7BZG.png) ---- ## 範例二：輸入與輸出說明 1. 輸入 ![](https://i.imgur.com/u2u9nmv.png) 2. 輸出 ![](https://i.imgur.com/GArmQAF.png) --- ## 評分說明一 :::info 1. 輸入包含若干筆測試資料，**每一筆測試資料的執行時間限制(time limit)均為 $2$ 秒**，依正確通過測資筆數給分。 2. 每一個端點座標是一個介於 $0\sim M$ 之間的整數，每筆測試案例線段個數上限為 $N$。 ::: ---- ## 評分說明二 :::info 1. 第一子題組共 $30$ 分，$M<1000，N<100$，**線段沒有重疊**。 2. 第二子題組共 $40$ 分，$M<1000，N<100$，**線段可能重疊**。 3. 第三子題組共 $30$ 分，$M<10000000，N<10000$，**線段可能重疊。** ::: --- # 解題 ### 頭腦動一下，要怎麼解？ ### 燒腦嗎？ ### 準備好了嗎? ### 放棄還是繼續？ ### 好吧!挑戰一下 :smile: :smile: :smile: --- ## 解題策略 1. 使用一個大小為 $M$ 的陣列 $(lines)$ 來儲存輸入的起點與終點： **陣列的初值全部預設為 $0$** ![](https://i.imgur.com/tsrl8mV.png) 2. 讀取所有線段的起點 $\sim$ 終點: **更新 $lines$ 中 $start \sim end$ 的值由$0變成1$** 3. 不斷重複 2. ，直到讀完所有的輸入線段 ---- ## 讀取線段的變化過程 ![](https://i.imgur.com/7lLvu3S.png) ::: info 線段總長度: 從陣列開始(0)到結束(M-1)，**統計陣列的總和，即為總長度**。 ::: --- ## 開始實作 ---- ## 建立陣列 :::success 請測試以下程式： 將結果紀錄下來，是否有錯？為什麼要加上 $1000$ ::: ```cpp=1 #include <iostream> #define MAXM 10000000 + 1000 // 依據題目M最大值 using namespace std; int main() { int lines[MAXM]; return 0; } ``` ---- ## 陣列初始化 :::info 使用 **for loop**: ::: ```cpp=1 for(int i=0; i<MAXM; ++i) lines[i]=0; ``` :::info **宣告時給初值**: ::: ```cpp=1 int lines[MAXN]={0}; ``` :::info **使用 memset(陣列名稱, 值, sizeof(陣列名稱)**) ::: ```cpp=1 memset(lines, 0, sizeof(lines)); ```  ---- ## 陣列初始化的選擇請紀錄3種作法CPU執行的時間，效能好不好? 要選用哪個較佳？ --- ## 輸出入資料處理 **重新導向輸出入資料處理輸出入的動作，framework如下** ```cpp=1 #include <iostream> //..... #define MAXM 10000000 + 1000 #define LOCAL // 本機端測試 //........ using namespace std; //....... int lines[MAXM]; int main() { #ifdef LOCAL // 本機端測試 // cin, scanf 的輸入資料來源檔案 freopen("data.inp", "r", stdin); // cout, printf 的輸出檔案 freopen("data.out", "w", stdout); #endif // LOCAL int x1, x2,.....; while(cin>>x1>>x2>>...){ // 開始處理每一個案例 } return 0; } ``` --- ## 實作程式，檢驗輸出結果請執行以下程式: 紀錄程式執行第1,2,3子題時間 ```cpp=1 #include <iostream> #include <ctime> #include <cstring> #define MAXM 10000000+1000 #define LOCAL using namespace std; int lines[MAXM]; int main() { #ifdef LOCAL freopen("data.inp", "r", stdin); freopen("data.out", "w", stdout); #endif // LOCAL clockid_t stime, etime; // 儲存使用者要輸入的線段筆數 int n; // 不斷讀取測試案例 while(cin>>n){ stime = clock(); // 將lines陣列元素全部設為0 memset(lines, 0, sizeof(lines)); // 讀取 n 個線段 for(int i=0; i<n; i++){ // 開始與結束座標 int sPoint, ePoint; cin>>sPoint>>ePoint; // 將sPoint~ePoint間的元素全部設為1 for(int j=sPoint; j<ePoint; j++){ lines[j]=1; } } // 統計 lines 陣列總和 int len = 0; for(int i=0; i<MAXM; i++){ len+=lines[i]; } // 輸出結果 cout<<len<<"\n"; etime=clock(); cout<<"Time elapsed " <<((double)(etime-stime))/CLOCKS_PER_SEC <<" s\n"; } return 0; } ``` --- ## 思考一下 ### 程式效能好像不怎麼好 ### 老師在哪兒? ### 杜老師 :SOS::SOS::SOS::SOS::SOS::SOS::SOS::SOS: --- ## 改進思考方向 :::success 1. 在輸入時紀錄所有輸入線段的最小值($min$)與最大值($max$)，減少迴圈檢查次數($min \sim max$) 2. 將定義在迴圈內的區域變數寫到迴圈外，避免變數配置時間 ::: 好像沒有演算法，只有程式流程的修改，沒軟用 :turtle::turtle::turtle: 先跑一看看再說 ---- ## 程式修改 ```cpp=1 #include <iostream> #include <ctime> #include <cstring> #define MAXM 10000000 + 1000 // 依據題目M最大值 #define LOCAL using namespace std; int lines[MAXM]; int main() { #ifdef LOCAL // cin, scanf 的輸入資料來源檔案 freopen("data.inp", "r", stdin); // cout, printf 的輸出檔案 freopen("data.out", "w", stdout); #endif // LOCAL clockid_t stime, etime; int n, i, j, sPoint, ePoint, len; int min, max; while(cin>>n){// 不斷讀取測試案例 stime = clock(); // 將lines陣列元素全部設為0 memset(lines, 0, sizeof(lines)); // 設定初值 max=-999999999; min= 999999999; len = 0; // 讀取 n 個線段 for(i=0; i<n; i++){ cin>>sPoint>>ePoint; if(sPoint<min) min=sPoint; if(ePoint>max) max=ePoint; // 紀錄輸入線段的min與max for(j=sPoint; j<ePoint; j++) lines[j]=1; } // 統計 lines 陣列總和 for(i=min; i<max; i++) len+=lines[i]; // 輸出結果 cout<<len<<"\n"; etime=clock(); cout<<"Time elapsed " <<((double)(etime-stime))/CLOCKS_PER_SEC <<" s\n"; } return 0; } ``` ---- ## 測試結果 1. 檢驗執行時間好像沒差:cry::cry: 2. 第二子題測試資料：100筆線段，線段最大值$M<1000$ 3. 第三子題測試資料：10000筆線段，線段最大值$M<10000000$ :::spoiler ![](https://i.imgur.com/6a2rflI.jpg) ::: ---- ## 各子題執行時間 1. 第二子題執行結果($100筆: 0\to 1000$的線段輸入)： ```python=1 999 Time elapsed 0.039 s ``` 2. 第三子題執行結果($10000筆: 0\to 10000000$的線段輸入)：: ```python=1 9997865 Time elapsed 68.056 s ```  ---- ## 在輸入那麼多100+10000筆測試資料，我的手快斷了 :cry::cry::cry::shit::shit::shit: ## 我的手一去不復返，怎麼辦 :question::question::question::question: ## 頭髮又掉了很多後 ## 決定讓程式自動處理:smile::smile::smile: ---- ## 各子題的測試資料產生程式 ```cpp=1 #include <iostream> #include <cstdlib> #include <ctime> #define MAXN 100 //#define MAXN 10000 #define MAXM 1000 //#define MAXM 10000000 using namespace std; unsigned int a[MAXN][2]; int main() { freopen("test_case2.inp", "w", stdout); //freopen("test_case3.inp", "w", stdout); int n1, n2; int counts=0; srand( static_cast<unsigned int>(time(NULL)) ); while(counts<MAXN){ n1 = static_cast<int>(1.*rand() *(MAXM-0+1)/(RAND_MAX+1.))+0; n2 = static_cast<int>(1.*rand() *(MAXM-0+1)/(RAND_MAX+1.))+0; if(n1>n2){ int tmp=n1; n1 = n2; n2=tmp; } a[counts][0]=n1; a[counts++][1]=n2; } cout<<counts<<"\n"; for(int i=0; i<MAXN; i++){ cout<<a[i][0]<<" "<<a[i][1]<<"\n"; } return 0; } ``` --- ## 要如何解決第3子題的問題 ### 頭髮又掉了 ### 只能再次呼喊 ~~ 老師在哪兒? ### 杜老師 :SOS::SOS::SOS::SOS::SOS::SOS::SOS::SOS: :::spoiler 我上杜老師的課很認真我想到了:smile: :smile: :smile: ::: --- ## 在子題3，產生時間超過原因 :::info 1. 當線段數變成$10000$時，讀取線段數變多且時間也變長 2. $M在M<10000000$時，每一線段寫入陣列時間變長且重複的部分也要重複寫入$1$，時間浪費許多 3. 計算線段長度的時間因$M$變大而時間變長 ::: --- ## 解決重複或覆蓋線段方式 1. 紀錄每個線段的起點與終點 2. 將所有線段以起點為key由小到大排序，當起點相同時以終點為key由小到大排序 3. 重複或覆蓋線段的處理: 以排序後的第1個線段為起始 - 若下一線段全部重複在目前線段中直接略過，移到下一線繼續判斷 - 若下一線段終點大於目前線段的終點，重設目前線段的終點為下一線段的終點再移到下一線段繼續判斷 ---- ## 解決重複或覆蓋線段方式示意圖 ![](https://i.imgur.com/YFSQZjU.png) 請說出圖形哪邊有錯:sleeping::zzz: --- ## 實作步驟開始使用資料結構與演算法 ---- ## 資料結構之建立與使用 :::info 1. 自訂結構LINE用以代表一個線段 ::: ```cpp=1 typedef struct{ int start; // 線段起點 int end; // 線段終點 }LINE; ``` :::info 2. 建立儲存所有線段的陣列 ::: ```cpp=1 #define MAXN 10000 + 10 LINE lines[MAXN]; ``` ---- ## n個線段之讀入 :::info 使用輸出入資料處理程式架構 ::: ```cpp=1 // 輸入的線段數 int n; while(cin>>n) { // 讀取n個線段 for(int i=0; i<n; i++) { // 將第i個線段資料存入 cin>>lines[i].start>>lines[i].end; } } ``` ---- ## n個線段排序 :::spoiler 1. 使用C\+\+的STL中sort()函式：**必須加入algorithm標頭檔** 2. 語法: sort(陣列起始位置, 陣列結束位置, 排序方法) ::: ```cpp=1 #include<algorithm> ........ // 線段結構排序方式: // 1. 起點相同終點小的排前面 // 2. 起點不同起點小的排前面 int cmp(LINE p, LINE q) { if(p.start!=q.start) return p.start<q.start; else return p.end<q.end; } // 排序 lines結構陣列的元素，依據 cmp 排序準則 sort(lines, lines+n, cmp); ``` ---- ## 線段覆蓋解決方式 1. 當有覆蓋或重複的部分時：使用while不斷找尋目前線段的的終點 3. 計算該線段的距離 ---- ## 線段覆蓋解決方式實作 ```cpp=1 int len=0; //線段總長度 int st; //第i筆線段起點 int ed; //第i筆線段終點 /*依序取出n筆線段資料*/ for(int i=0; i<n; i++){ st=lines[i].start;//第i筆線段起點 ed=lines[i].end; //第i筆線段終點 /*覆蓋線段處理：覆蓋部分視為同一線段*/ while((i+1<n) && lines[i+1].start<ed){ //下一線段終點小於目前線段終點(完全覆蓋) if(lines[i+1].end<=ed) i++; //忽略i+1線段，移到下一個線段 //將下一線段終點設為目前線段終點(重設目前線段的終點) else{ ed=line[i+1].end; i++;//移到下一個線段 } } len+=ed-st; // 線段總長度加上(終點-起點) } ``` --- ## 完整程式碼: 標頭檔與全域變數 ```cpp=1 #include <iostream> #include <algorithm> #include <ctime> #define MAXM 10000000 + 1000 // 依據題目M最大值 #define LOCAL // 本機測試 using namespace std; typedef struct{ int start; int end; }LINE; LINE lines[MAXM]; int cmp(LINE p, LINE q) { if(p.start!=q.start) return p.start<q.start; else return p.end<q.end; } ``` ---- ## 完整程式碼: 主程式 ```cpp=1 int main() { #ifdef LOCAL // 第三子題測資 freopen("test_case3.inp", "r", stdin); freopen("test_case3.out", "w", stdout); clockid_t stime=clock(), etime; #endif // LOCAL int n; while(cin>>n){ for(int i=0; i<n; i++) cin>>lines[i].start>>lines[i].end; sort(lines, lines+n, cmp); int len=0, st, ed; for(int i=0; i<n; i++){ st=lines[i].start; ed=lines[i].end; while((i+1<n) && lines[i+1].start<ed){ if(lines[i+1].end<=ed) i++; else{ ed=lines[i+1].end; i++; } } len+=ed-st; } cout<<len<<"\n"; } #ifdef LOCAL etime=clock(); cout<<"Time elapsed " <<((double) (etime - stime)) / CLOCKS_PER_SEC <<" s\n"; #endif // LOCAL return 0; } ``` ---- ## 測資3測試結果 :::success 使用結構陣列 9997865 Time elapsed **0.036 s** ::: :::info 使用一般陣列 9997865 Time elapsed **68.78** s ::: :::spoiler :::info 很明顯若使用演算法技巧，可以讓效能大大提升。還好有老師教的演算法技巧 :smile::smile::smile::smile::smile: ::: --- ## 後續研究與測試 :::info 使用自己的寫的 sort 函式與 STL sort 函式的做比較:bubble, quick, insert, merge ::: :::success 使用其他語言進行測試 1. python: 執行速度慢但程式較易理解 2. C: 執行效能更勝C++，主要因為scanf()比cin在讀取大量資料時快很多 ::: --- # Q&A --- ### Thank you! :horse_racing: :horse_racing::horse_racing::horse_racing::horse_racing::horse_racing::horse_racing::horse_racing: :::success ### 感謝老師的教導 ### 謝謝各位的聆聽 ### 祝各位平安喜樂 ### 期待在金門相見 :::