---
# System prepended metadata

title: SCIST C++試辦課程

---

# 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;
}

```
# 時間複雜度
![](https://hackmd.io/_uploads/Hyhrw5K03.png)
**計算一支程式丟到電腦上需要執行多久
因為考量不同電腦計算能力的問題
所以速度不是以秒計算
正確來說 時間複雜度會用 演算法執行需要幾個指令 來計算
以 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 的方法數**
![](https://hackmd.io/_uploads/Sy_BHiYR2.png)
### 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];
}
```


