---
# System prepended metadata

title: S3 演算法 week 6
tags: [S3 公開資源]

---

# S3 演算法 week 6
###### tags: `S3 公開資源`

:::info
時間：12/25 9:00 ~ 17:00
地點：成大資工系新館 **65304** 教室
主題：遞迴與排序
直播連結：https://youtu.be/boxEzGdyuiQ
:::

# 必作題題解

[TOC]

## 二章－第六節

### [No－Judge 能撐多久](https://hackmd.io/@sa072686/cp/%2FFRgcCDGCQG-ECiVj7tWSgw#%E8%83%BD%E6%92%90%E5%A4%9A%E4%B9%85)

撰寫者：fishhh

$$
f(n) = 
\begin{cases}
0 & n = 0 \\
f(\lfloor \frac{n}{b} \rfloor) + 1 & n > 0
\end{cases}
$$


:::spoiler 參考程式碼
```cpp
#include "iostream"
using namespace std;
int a,b;
int top_down(int now){
    if(now==0){
        return 0;
    }
    return top_down(now/b)+1;
}
int top_down2(int now){
    if(now>a){
        return 0;
    }
    return top_down2(now*b)+1;
}
int main(){   
    cin>>a>>b;
    cout<<top_down(a)<<"\n";
    cout<<top_down2(1)<<"\n";
    //buttom up
    int cnt=0;
    while(a!=0){
        a/=b;
        cnt++;
    }
    cout<<cnt<<"\n";
}
```
:::

---

### [No Judge - 次方加總](https://hackmd.io/@sa072686/cp/%2FFRgcCDGCQG-ECiVj7tWSgw#%E6%AC%A1%E6%96%B9%E5%8A%A0%E7%B8%BD)

撰寫者：fishhh

$$
f(n) = 
\begin{cases}
1 & n = 1 \\
f(n - 1) \times n + 1 & \text{otherwise}
\end{cases}
$$



:::spoiler
```cpp=
#include "iostream"
using namespace std;
int a,b;
int top_down(int now){
    if(now==0){
        return 1;
    }
    return top_down(now-1)*a+1;
}
int n_pow;
int top_down2(int now){ //或者是回傳型別改成pair<int,int> 會更直觀(補充)
    if(now==0){
        n_pow=1;
        return 1;
    }
    int ret=top_down2(now-1);
    n_pow*=a;
    return ret+n_pow;
}
int main(){
    cin>>a>>b;
    cout<<top_down(b)<<"\n";
    cout<<top_down2(b)<<"\n";
    //buttom_up
    int now=1,ans=0;
    for(int i=0;i<=b;i++){
        ans+=now;
        now*=a;
    }
    cout<<ans<<"\n";
}
```
:::

---

### [No Judge - 擲骰](https://hackmd.io/@sa072686/cp/%2FFRgcCDGCQG-ECiVj7tWSgw#%E6%93%B2%E9%AA%B0)

$$
f(n, m) = 
\begin{cases}
\displaystyle\sum_{k = 1}^{b}f(n - 1, m - k) & n > 0 \\
1 & m = 0 \\
0 & \text{otherwise}
\end{cases} \\
ans = f(a, c)
$$


撰寫者：fishhh

:::spoiler 參考程式碼
```cpp=
#include "iostream"
using namespace std;
int a,b,c;
int top_down(int now_dice,int tot){
    if(now_dice==0){
        if(tot==c)return 1;
        else return 0;
    }
    int cnt=0;
    for(int i=1;i<=b;i++){
        cnt+=top_down(now_dice-1,tot+i);
    }
    return cnt;
}
int main(){
    cin>>a>>b>>c;
    cout<<top_down(a,0)<<"\n";
    
    
    /*******以下為 bottom up 解法*******/
    int count[10][200]={}; //count[i][j] 前i顆骰子 可以丟出幾次總合為 j 的情況
    //因為題目給沒有給範圍 這裡假設最多9顆骰子
    count[0][0]=1;
    for(int i=1;i<=a;i++){
        for(int j=0;j<=100;j++){ //假設 a*b max =100
            for(int k=1;k<=b;k++){
                count[i][j+k]+=count[i-1][j];
            }
        }
    }
    cout<<count[a][c];

}
```
:::


---

### [No Judge - 比較大小](https://hackmd.io/@sa072686/cp/%2FFRgcCDGCQG-ECiVj7tWSgw#比較大小)

撰寫者：Eason

~~雖然可以直接比較兩個字串~~
但請大家使用遞迴去練習

用遞迴去比較每一個字元
需特別注意當$s_i$ = $t_i$時
要判斷應該回傳還是繼續遞迴
其他情況回傳題目所要求的即可

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;

long long s_len, t_len;

int cmp(string a, string b, int index){
    if (a[index] < b[index]) return -1;
    else if (a[index] > b[index]) return 1;
    else if (a[index] == b[index] && index == s_len - 1 && s_len == t_len){
        return 0;
    }
    else return cmp (a, b, index + 1);
}

int main(){
    string s, t;
    cin >> s >> t;
    s_len = s.size();
    t_len = t.size();
    cout << cmp (s, t, 0) << '\n';
    return 0;
}
```
:::

---

### [No - Judge 爬樓梯問題](https://hackmd.io/@sa072686/cp/%2FBbRsMnLrQFuCeLifVxecJA#爬樓梯問題)

撰寫者：Eason

我們假設 $dp_i$ 為爬上第 $i$ 階的方法數
則可以先算出： 
>第 $1$ 階($dp_1$) = 1 (因為只能從第0階走上來)
>第 $2$ 階($dp_2$) = 2 (可以從第0階走兩步上來，也可以從第1階走一步上來)
>第 $i$ 階($dp_i$) = $dp_{i-1} + dp_{i-2}$ (可以從第$i-2$階走兩步上來，也可以從第$i-1$階走一步上來)

$$
dp_i = 
\begin{cases}
1 &  i = 1 \\
2 &  i = 2 \\
dp_{i-1} + dp_{i-2} & \text{otherwise}
\end{cases}
$$

所以直接用陣列模擬就好

:::spoiler bottom-up
```cpp=
#include<iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    long long dp[105];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout << dp[n] << '\n';
    return 0;
}
```
:::
:::spoiler top-down
```cpp=
#include<iostream>
using namespace std;

long long solve(int i){
    if (i == 1) return 1;
    else if (i == 2) return 2;
    return solve(i - 1) + solve(i - 2);
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    cout << solve(n) << '\n';
    return 0;
}
```
:::


---

### [No－Judge 爬樓梯．改一](https://hackmd.io/@sa072686/cp/%2FBbRsMnLrQFuCeLifVxecJA#%E7%88%AC%E6%A8%93%E6%A2%AF%EF%BC%8E%E6%94%B9%E4%BA%8C)

撰寫者：fishhh

:::spoiler 參考程式碼
```cpp=
#include "iostream"
using namespace std;
int step[100]={};
int top_down(int now){
    if(now<=0){
        return 0;
    }
    return min(top_down(now-1),top_down(now-2))+step[now];
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>step[i];
    }
    cout<<top_down(n)<<"\n";

    /*~~~~~~~~~~buttom-up~~~~~~~~~~~~~*/
    int min_cost[100]={}; // min_cost[i] 代表位於 i 時的最小扣血量
    for(int i=1;i<100;i++)min_cost[i]=1e9;
    //min_cost[0] 一定是0 (因為是起點)
    for(int i=0;i<=n;i++){ // 枚舉起點
        min_cost[i+1]=min(min_cost[i+1],min_cost[i]+step[i+1]);
        min_cost[i+2]=min(min_cost[i+2],min_cost[i]+step[i+2]);
    }
    cout<<min_cost[n]<<"\n";
}
``` 
:::

---

### [No - Judge 爬樓梯．改二](https://hackmd.io/@sa072686/cp/%2FBbRsMnLrQFuCeLifVxecJA#爬樓梯．改二)

撰寫者：Eason

大致概念跟爬樓梯問題一樣
改一下初始的值就好

$$
dp_i = 
\begin{cases}
1 &  i = 1 \\
1 &  i = 2 \\
2 &  i = 3 \\
4 &  i = 4 \\
dp_{i-1} + dp_{i-3} + dp_{i-4} & \text{otherwise}
\end{cases}
$$

:::spoiler bottom-up
```cpp=
#include<iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    long long dp[105];
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 4;
    for (int i = 5; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 3] + dp[i - 4];
    }
    cout << dp[n] << '\n';
    return 0;
}
```
:::
:::spoiler top-down
```cpp=
#include<iostream>
using namespace std;

long long solve(int i){
    if (i == 1) return 1;
    else if (i == 2) return 1;
    else if (i == 3) return 2;
    else if (i == 4) return 4;
    return solve(i - 1) + solve(i - 3) + solve(i - 4);
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    cout << solve(n) << '\n';
    return 0;
}
```
:::

---

### [No－Judge 運算式求解](https://hackmd.io/@sa072686/cp/%2FBbRsMnLrQFuCeLifVxecJA#%E9%81%8B%E7%AE%97%E5%BC%8F%E6%B1%82%E8%A7%A31)

撰寫者：fishhh







