# 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
Sign in with Wallet
Connect another wallet