# SCIST C++試辦課程
## [**上課講義**](https://drive.google.com/file/d/1SfAikYzQ2gOT-Ql1ncFDwIG-8cNvy5uy/view?pli=1)
# 演算法
* ### **白話文的解釋就是: 解決問題的方法**
* ### **在計算機科學的方面來說,大家在追求的演算法需要符合以下兩點**
>1. **需要的時間少 (時間複雜度)**
>2. **需要的空間小 (空間複雜度)**
# 排序 Sorting
## Bubble Sort 氣泡排序
* **如果我們要由小排到大的話,Bubble Sort 就是一直把最大的拿到最右邊**
* **再來拿第二大、第三大 直到全部都走過,也就是成功把陣列由小排到大的時候了!**
### [**傑哥的排序**](https://codeforces.com/gym/471838/problem/J)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=a; i<b;i++) //定義縮寫
int main(){
int n; cin >> n;
int N[n];
FOR(i,0,n){
cin >> N[i]; //將數字排入陣列
}
sort(N,N+n); //使用內建排序函式
FOR(i,0,n){
cout << N[i]<< ' ';
}
}
```
## Merge Sort 合併排序
* **把兩段已經排序好的數字合併成一個完整的已經排序好的數列**
### [**合併大師**](https://codeforces.com/gym/471838/problem/K)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i =a;i<b;i++)
int main(){
int n1,n2; cin >> n1 >> n2;
int A[n1 + n2];
FOR(i,0,n1+n2) cin >> A[i];
sort(A,A+n1+n2);
FOR(i,0,n1+n2) cout << A[i]<< ' ';
return 0;
}
```
# 時間複雜度
**計算一支程式丟到電腦上需要執行多久
因為考量不同電腦計算能力的問題
所以速度不是以秒計算
正確來說 時間複雜度會用 演算法執行需要幾個指令 來計算
以 Big O 表示
只會紀錄 最高次方項 並忽略其所有的係數
以下為常見的時間複雜度：**
### O(1) : 常數時間
**n不管輸入多大，都不會影響程式執行時間**
```cpp=
void PrintINT(int n) {
printf("%d\n",n);
}
```
### O(n)：線性時間
**隨輸入 n 的大小而影響 for迴圈執行次數**
```cpp=
int Sum_1_to(int n){
int i,sum=0;
for(i=1;i<=n;i++){
sum += i;
}
return sum;
}
```
### O(n^2)：平方時間
* **巢狀迴圈**
**執行 n * n 次 最高次方項為 n的2次方**
```cpp=
void Mult_table(int n){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
printf("%d\t",i*j);
}
printf("\n");
}
}
```
### O(2^n)：指數時間
* **費波那契數列**
### O(log n)：對數時間
* **二分搜尋法**
**log 以 2 為底 每次從中間開始搜尋 並排除另一半**
```python=
Numbers = [1,3,4,6,7,8,10,13,14]
Find = 4
low = 0
high = len(Numbers) - 1
while low <= high:
mid = (low + high) // 2
if Numbers[mid] > Find:
high = mid - 1
elif Numbers[mid] < Find:
low = mid + 1
else:
break
print(mid)
```
### O(n log n)：線性對數時間
* **合併排序**
>作者: ShiYu Huang
連結: https://shiyu0318.github.io/2022/12/Big-O/
來源: ShiYu's Blog
著作權歸作者所有。商業轉載請聯絡作者獲得授權，非商業轉載請註明出處。
## **前綴和**
### [**一維區間和問題**](https://codeforces.com/gym/471838/problem/L)
```cpp==
#include <bits/stdc++.h>
using namespace std;
#define YuDe ios::sync_with_stdio,cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i = a; i<b; i++)
int main(){
YuDe;
int n,q; cin >> n >> q;
int a[n+1];
FOR(i,1,n+1) cin >> a[i];
int sum[n+1];
sum[0] = 0;
FOR(i,1,n+1){
sum[i] = sum[i-1] + a[i];
}
int l, r;
while(q--){
cin >> l >> r;
cout << sum[r] - sum[l-1] <<'\n';
}
return 0;
}
```
### [**序列相似度**](https://codeforces.com/gym/471838/problem/N)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define YuDe ios::sync_with_stdio,cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define FOR1(i,a) for (int i=1; i<=a;i++)
int main(){
YuDe;
int n; cin >> n;
int a[n],sum[n+1],t;
vector<int> v;
FOR(i,0,n) cin >> a[i];
FOR(i,0,n){
cin >> t;
if (t == a[i]) v.push_back(1);
else v.push_back(0);
}
sum[0] = 0;
FOR1(i,n){
sum[i] = sum[i-1] + v[i-1];
}
int q; cin >> q;
int l,r;
while(q--){
cin >> l >> r;
cout << sum[r] - sum[l-1] <<'\n';
}
return 0;
}
```
## 動態規劃 DP
### 爬樓梯問題
* **一共有n階，每次可以向上爬 1 階或是 2 階，請問有幾種方式?**
**如果要爬第 i 階，就只能從 i − 1 階或是 i − 2 階爬上來**
**那麼爬到第 i 階的方法數就會是，爬到 i − 1 階的方法數加上 i − 2 的方法數**
### DP的一些名詞
* **Base Case**
**就是在電腦開始計算之前需要的資料，像是爬樓梯問題需要知道
dp[1], dp[2]**
* **狀態**
**為我們設了一個叫做 dp 的陣列，要賦予每個位置一個意義，例如說：dpi
就是爬到第 i 階的方法數**
* **轉移**
**透過轉移這個操作，我們可以透過一些運算推知其他東西，例如：
dpi = dpi−1 + dpi−2 這就是爬樓梯問題的轉移式**
### **`所以，DP 就是一連串的狀態進行轉移，最後得到答案!`**
### [**DP大師的考驗**](https://codeforces.com/gym/471838/problem/M)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define YuDe ios::sync_with_stdio,cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i = a; i<b; i++)
int main(){
YuDe;
int n; cin >> n;
int dp[10]={};
dp[1] = 1; dp[2] = 2; dp[3]=4;
FOR(i,4,n+1){
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
cout << dp[n];
}
```
Sign in with Wallet
Connect another wallet