C++上課筆記

C++上課筆記 === [記分板](https://docs.google.com/spreadsheets/d/1nPCGl6rGjmjq01idLJn3m96aqoXbtY16j_WaKPjm-fM/edit#gid=0) ### Quetion: > [DRM Messages](https://open.kattis.com/problems/drmmessages) (RE) > [Q483](http://domen111.github.io/UVa-Easy-Viewer/?483) (WA)(單字顛倒) > [Paradox With Averages](https://https://open.kattis.com/problems/averageseasy) (WA)(大學計算機系) > [Q673](http://domen111.github.io/UVa-Easy-Viewer/?673) (WA)([()]) > [Q12695](https://www.udebug.com/UVa/12650) (WA)(生還者) > [UVA Q10110] 還沒上oj測，UVA又又又掛掉了 <style> .blue { color: #288FEA; } </style> ## 名詞統整 - 整合開發環境(IDE) ### online judge (線上評測系統) > #### 網站: [TOJ](https://toj.tfcis.org/oj/info/)、[Kattis](https://open.kattis.com/problems)、[UVA](https://onlinejudge.org/)、[AtCode](https://atcoder.jp/)、[ZeroJudge](https://zerojudge.tw/) - Memory Limit Exceeded(MLE)->耗掉太多記憶體 - Time Limit Exceeded(TLE)->跑太久 - Persentation Error(PE)->格式錯誤 # 20210926 SCIST - **課程內容:** c++基礎語法 (~迴圈) ## 骨幹 ```cpp= #include <iostream> using namespace std; int main() { return 0; } ``` ## 變數 ### 溢位: - int : 4個位元組=32個位元，可存放：±2^31-1 (2147483647) - 過大-> long long型別 -> 在運算後加`LL` ## 迴圈 ### for : ```cpp= for(i=1;i<=n;i++) { cout << "你超棒的!\n"; } ``` 1. 條件用**分號**區隔 2. ( 執行前的準備 ; 執行條件 ; 收尾) # 20210928 科丁 ## 速記 ✏ - cin 不可以輸空白 - 不同資料型態運算: 取型態範圍大的~ - <bits/stdc++.h> - ios::sync_with_stdio(0); - cin.tie(0); -> 只能用cin、cout,不能用endl ## 輔助 - 含所有的標頭檔的標頭檔: ```cpp= #include <bits/stdc++.h> ``` - 加速 - 注意⚠ 1. 只能使用 cin、cout 2. 不能使用 endl ```cpp= ios::sync_with_stdio(0); cin.tie(0); ``` ## 資料型態 - 整數:int - double/float: 小數(精確度高/精確度低) - **字元**: char =='單引號'括字串== ## 輸出/輸入 ### 科學記號&小數點精確度 ```cpp= #include <iomanip> //for setprecision(),setw() ``` 1. 標頭檔 **<iomanip>:** 含setprecision & setw ```cpp= cout << fixed; //for setprecision() ``` 2. ***fixed:*** 搭配setprecision，setprecision可僅控制==小數點後的位數== ```cpp= printf("%.1f",1.234); // c=>精確到小數點後一位(.1f)四捨五入 cout << setprecision(1) << 1.234; // c++ =>精確到小數點後一位 ``` 3. ***setprecision:*** 輸出位數 ```cpp= printf("%4.1f",1.234); // c=> 小數點前四位("4".1f) (含整數&空白) cout << setw(4) << setprecision(1) << 1.234; // c++ => setw空四位 ``` 4. ***setw:*** 輸出寬度 ### scanf - scanf("%d",&A); <=> cin >> A; ## 字串 - 字元: 若干個字元，最後一個是終止字元 ::: success **'A'** -> 65 (is 字元)　 **"A"** -> 65,0 ( is 字串) 　**"ABC"** -> 65,66,67,0 (is 字串) ::: # 20211003 SCIST ## 陣列 - 宣告大小後不可以更改 - 宣告時可以直接賦值 -> { } ==只能用在宣告時== ```cpp= int ax[4]={2,1} for (int i=0; i<4; i++) { cout << ax[i] << '\n'; } ``` :::info cout= 2,1,0,0 -> **不足的補0** ::: # 20211017 SCIST 待補 # 20211019 科丁 - 最大公因數：``__gcd()`` (底線底線) ```cpp= #include <algorithm> cout << __gcd(a,b); ``` # 20211031 SCIST ## 複雜度(complexity) - 計算量&資料量的關係(定義函數) - **O()**= 複雜度，最差情形需所需的計算量 - O(1):常數 constant - O(n):線性 linear /多項 - Big O 表記 O()是上限的意思，表示該函數成長速度不超過此限制 # 20211205 SCIST ## 資料結構 ### 佇列(queue): 先進後出 - enqueue: 將一筆資料加入queue的**最後面** - dequeue: 將**最前面**的資料從queue移除 ### 堆疊(stack): 後進先出 :::info 後進需優先處理，所以先出 ::: - push: 把新的東西加入stack - pop : 把最新的東西移除 ### 鏈結串列(linked-list) | | list | linked-list | | ------------- | ---- | ----------- | | 取得第i個元素 | O(1) | O(n) | | 移除第i個元素 | O(n) | O(n) | | 插入元素到i | O(n) | O(1) | # 20221218 SCIST ## 排序 ### 選擇排序法 Selection Sort - 每次找最小值出來，移到最前面 - 最簡單，但基本上很難省略任何一次作法 ***施工 :construction_worker: ### 氣泡排序法 Bubble sort ### 插入排序法 Insertion Sort ## 更快的排序 ### 合併排序法 Merge Sort ### 快速排序法 Quick Sort ### Sort 函式 *** # 20220309 選手班課程 ### 傳參(參考型別與傳參考呼叫) - 幫變數取別名 ```cpp= int i=5; int &j=i; //參考型別變數j，j和i同地址，代表同一變數 ``` - ***<span class="blue">eg：交換ａ,b變數的值</span>*** - 注意⚠ - **return只能回傳一個值** ```cpp= viod Swap(int &a,int &b){ int tmp=a; a=b; b=tmp; } int main{ Swap(a,b); } ``` ### 巨集 - like a 函式 - 將函式名稱代換成指定的運算式 - 👍：比起函式少了呼叫/返回的時間 -> 更快 ```cpp= #difine f(x) (x)*(x)*(x) ... int main() { int i=3; cout << f(i); //cout i*i*i } ``` - 注意⚠ - 巨集只是代換，運算可能錯誤 - 每一個變數要()起來 - ***<span class="blue">eg：沒括號的後果</span>*** :::warning ```cpp= #difine f(x) x*x*x cout << f(i+1); ``` 替換成 -> i+1 * i+1 * i+1 先乘除後加減 -> i+i+i ::: ### vector(容器) - vector<資料型態>容器名稱(初始值) ```cpp= vector<int>num(n); //一維陣列 vector<vector<int>>num(n,vector<int>(m)); //二維陣列 ``` # 20220313 SCIST ## 二分搜 (binary search) - 先排序(升or降) ```cpp= int binary_search(int c,int d,int e) //(ary,ary+n,k) { while(c<=d){ int mid=(c+d)/2; if(ary[mid]==e) return mid; if(ary[mid]>e) d=mid-1; else c=mid+1; } return -1; } ``` - **廣義的二分搜可以搜尋任何具備單調性的函數** - 單調性 : - ex: 已排序 - 廣義: i<=j => f(i)<=f(j) # 20220320 SCIST ## 深度優先搜尋(DFS) - 窮舉 - 遞迴 - 注意⚠: - 區域變數 & 全域變數 -> 變數的範圍須注意 - 中途結算(prunning): 有點像是前綴和(?) - 剪枝 - ``1+3+4 +2`` & ``1+3+4 +3`` # 20220406 選手班一些小筆記:pencil2: ## 亂數 ```cpp= srand(time(0)); random_shuffle(num.begin(),num.end()); //大風吹 ``` ## merge sort -> vector版 - 傳值 ```cpp= void msort(int *,int,int); void merge(int *,int,int); void printA(int *a,int s) { for(int i=0;i<=s;++i) cout << a[i] << " "; cout << "\n"; } ``` # 20220424 SCIST ## 位元運算(bit-wist operation) > 真值表 - AND: `&` -> 皆為1才是1 - OR: `|` -> 有1就是1 - XOR: `^` -> 相異才為1 - NOT: `~` -> 0轉1，1轉0 ==注意位數== - L-shitf: `<<` -> 超出位數削掉(首位)，不足補0 - R-shift: `>>` -> 超出位數削掉(末位)，不足補0 ## 分治(divide and conquer) - 大化小 - eg:Merge sort ## 貪心(Greedy) - 取最好