# APCS 109.10.17
## 上機題目
滿分解法
https://github.com/algo-seacow/Competitive-Programming/tree/master/apcs/10910
### 第 1 題: 人力分配
- https://zerojudge.tw/ShowProblem?problemid=f312
### 第 2 題: 人口遷移
- https://zerojudge.tw/ShowProblem?problemid=f313
### 第 3 題: 勇者修煉
- https://zerojudge.tw/ShowProblem?problemid=f314
### 第 4 題: 低地距離
- https://zerojudge.tw/ShowProblem?problemid=f315
## 筆試第二節
### Recursion
```cpp=
int f(int x, int y) {
if (x<=0) return y;
return f(x-1, 2*y + x + 3);
}
```
求 f(5, 3) 的結果，答案為 147
### Recursion, 填空
f(a,b) 會輸出 $a^b$ 的結果
```cpp=
int f(int a, int b) {
if (b<0) return 0;
if (b==0) return 1;
return {???};
}
```
1. a * f(a, b-1)
2. b * f(a, b-1)
3. a * f(a-1, b)
4. b * f(a-1, b)
答案是 a * f(a, b-1);
### Recursion, 1+2+3+...+n
```cpp=
int f(int n) {
if ( {???} ) {
return {???};
}
return n + f(n-1);
}
```
上面兩段 {???} 可以填入什麼，能讓 f 正確回傳 $a^b$？
a. n<=1 與 n
b. n<=0 與 0
c. n<1 與 0
1. a, b 可以
2. a, c 可以
3. a 可以
4. a, b, d 都可以
答案是三種都可以
### Recursion, 1+2+3+...+n, debug
```cpp=
int f(int n) {
if (n<0) {
return 0;
}
return f(n-1);
}
```
### 找第二大的數字, code 有錯, 找一組會讓他錯的測資
```cpp=
...
int a = p[0], b = p[0];
...
```
當 p[0] 是最大值時會有問題
### Switch
```cpp=
int ans = 0;
int a[6] = {0, 1, 5, 4, 4, 3};
for (int i=0; i<6; i++) {
switch(a[i]) {
case 1: ans += 1; break;
case 2: ans += 2;
case 3: ans += 3; break;
case 4: ans += 4; break;
case 5: ans += 5; break;
case 6: ans += 6;
default: ans += 6;
}
}
cout << ans << endl;
```
### Trace code, 2D array, 最後一題
### while loop 要繼續的條件
已知超過 365 天或是 人數變成負數就結束 while loop, 求 while loop 的 condition
答案是 people > 0 && days < 365
### DP, 費氏數列
```cpp=
int f(int n){
if (n<=1) return 1;
return f(n-1) + f(n-2) + 1
}
```
求 f(6) 的結果
### IF
```cpp=
int f(int a, int b) {
int n = 2, m = 5;
if (a<3 && b<7) {
if (a>=4) {
return n+m;
}
else {
return n-m;
}
}
else {
return n*m;
}
}
```
找出一個選項，包含三個 f，n+m, n-m, n*m 都有被呼叫到
### 字串解密
```cpp=
// code
```
只要算出第一個字就可回答題目
### IF
```cpp=
int main(){
int a=4, b=3, c=7;
if (a<b) cout << 'A'
else if (!(a==0)) cout << 'B'
else cout <<'C'
}
```
求輸出結果
###
## 筆試第一節
### bubble sort + struct cpy
```cpp=
struct {
int score;
char name[];
};
```
找錯
### 找最小的兩個數字
```cpp=
int a1 = 999, a2 = 999;
int a[] = {2, 1, 4, 7 , 8};
...
```
### 奇怪的篩法
```cpp=
int a[1001] = {};
for (int i=3; i<=1000; i+=2) {
for (int j=i*i; j<=1000; j = j + i + i) {
a[j] = 1;
}
}
```
找偶數 index 的總和，答案是 0
### scope : local / global
```cpp=
int rateUSD2TWD = 30;
int rateTWD2JPD = 5:
int USD2TWD(int x) {
int rateUSD2TWD = 40;
return x * rateUSD2TWD;
}
int TWD2JPD(int x) {
int rateTWD2JPD = 4:
return x * rateTWD2JPD;
}
void main(){
int iUSD = 10;
int iTWD = USD2TWD(iUSD);
cout << iTWD << endl;
int iJPD = TWD2JPD(iTWD);
cout << iJPD << endl;
int d = USD2TWD(iUSD) + TWD2JPD(iTWD) / rateTWD2JPD;
cout << d << endl;
}
```
正確的輸出是 300, 1200, 540 找出要輸出的數字
### Recursion, 費氏數列, dp
```cpp=
int a[10] = {0}
int f(int n) {
a[n]++;
if (n<=1) return 1;
return f(n-1) + f(n-2) + 1
}
```
call f(6) : 求出 a[0], a[1]
### Recursion, 前序後序
```cpp=
void f1(int x);
void f2(int x) {
if (x<=0) return;
f1(x-1);
cout << x << endl;
}
void f1(int x) {
if (x<=0) return;
cout << x << endl;
f2(x-1);
}
```
call f1(5), 求輸出的結果, 答案是 53124
### 化簡判斷式
```cpp=
if(x>10){
if(y<3){
return "B";
}
else{
if(x>y)return "A";
else return "B";
}
}
else return "A";
```
化簡成一個 if 跟一個 else
### 字元比較
```cpp=
s = "abcaaa"
```
給一函式f(text, n) 求間隔為 n 且相同字元組數為 1 的數量
n: 1~5
### IF
```cpp=
int f(int x){
if (...) return 4x-6
else return 4x+3
}
```
給 f(7), f(8) 的結果，求 if 的判斷條件
### 布林運算
```cpp=
!((x <= y) || (y > z) || (x < z))
```
選擇會使這個式子成立的選項
### ASCII, int 除法
```cpp=
int a = 1;
float b = 2.0;
int c = a / b;
printf("%d %c", c, 65 + c);
```
已知 'A', 'a' 的ASCII, 求輸出結果
### rotate, MOD
```cpp=
int f(int a, int b, int c, int n) {
while (n--) {
int tmp = a;
a = b;
b = c;
c = tmp;
}
return a;
}
```
找出輸出結果不是 25 的選項
### Trace code, do-while
```cpp=
int f(int x) {
int ans = 0;
do{
ans += x;
} while (ans >=0 && ans <= 10);
return ans;
}
int main(){
while (x<=40) {
x = x + f(x);
}
cout << x << endl;
}
```
### Nested loop, 大數乘法
```cpp=
a[] = {-2, -1, 0, 1, 2}
b[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i=0; i<5; i++) {
c[i] = c[i] + a[j] * b[i+j];
}
```
### 奇怪的 stack, 計算字串中 AB 的個數是否一樣多
問哪組輸入會回傳true
```cpp=
char s[] = "abaabababa"; // a b 組成的字串
int n = strlen(text);
bool check(s, n){
int p[100] = {0};
int t = 0;
for(int i=0;i<n;i++){
if(s[i]=='a' && (p[i]==1 || p[i]==0)){
t++;
p[t] = 1;
}
if(s[i]=='b' && (p[i]==2 || p[i]==0)){
t++;
p[t] = 2;
}
else t--;
}
return t == 0;
}
```
## License and copyright
Author: 演算法海牛
Posted on: 2020-10-17
Licensed under: <a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/"><img alt="創用 CC 授權條款" style="border-width:0" src="https://i.creativecommons.org/l/by-nc/4.0/88x31.png" />
Sign in with Wallet
Connect another wallet