APCS 109.10.17

上機題目

滿分解法
https://github.com/algo-seacow/Competitive-Programming/tree/master/apcs/10910

筆試第二節

Recursion




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}

的結果





int f(int a, int b) {
    if (b<0) return 0;
    if (b==0) return 1;
    return {???};
}

a * f(a, b-1)
b * f(a, b-1)
a * f(a-1, b)
b * f(a-1, b)

答案是 a * f(a, b-1);

Recursion, 1+2+3+…+n






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

a, b 可以
a, c 可以
a 可以
a, b, d 都可以

答案是三種都可以

Recursion, 1+2+3+…+n, debug






int f(int n) {
    if (n<0) {
        return 0;
    }
    return f(n-1);
}

找第二大的數字, code 有錯, 找一組會讓他錯的測資



...
int a = p[0], b = p[0];
...

當 p[0] 是最大值時會有問題

Switch














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, 費氏數列




int f(int n){
    if (n<=1) return 1;
    return f(n-1) + f(n-2) + 1
}

求 f(6) 的結果

IF














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　都有被呼叫到

字串解密


// code

只要算出第一個字就可回答題目

IF






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




struct {
    int score;
    char name[];
};

找錯

找最小的兩個數字



int a1 = 999, a2 = 999;
int a[] = {2, 1, 4, 7 , 8};
...

奇怪的篩法






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



















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






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, 前序後序











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

化簡判斷式










if(x>10){
    if(y<3){
        return "B";
    }
    else{
        if(x>y)return "A";
        else return "B";
    }
}
else return "A";

化簡成一個 if 跟一個 else

字元比較


s = "abcaaa"

給一函式f(text, n) 求間隔為 n 且相同字元組數為 1 的數量
n: 1~5

IF




int f(int x){
    if (...) return 4x-6
    else return 4x+3
}

給 f(7), f(8) 的結果，求 if 的判斷條件

布林運算


!((x <= y) || (y > z) || (x < z))

選擇會使這個式子成立的選項

ASCII, int 除法





int a = 1;
float b = 2.0;
int c = a / b;

printf("%d %c", c, 65 + c);

已知 'A', 'a' 的ASCII, 求輸出結果

rotate, MOD









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













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, 大數乘法






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


















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:

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →