# APCS 110.01.09
[CC 姓名標示─非商業性─相同方式分享](https://creativecommons.org/licenses/by-nc-sa/3.0/tw/legalcode)
## 觀念第一場
- bubble sort like
```c=
int F(int seed) {
int a[10] = {...};
for (int i=0 ;i<9; i++){
if (a[i+1] >= a[i] && a[i+1] <= seed){
int temp = a[i+1];
a[i+1] = a[i];
a[i] = temp;
}
}
printf("%d", a[seed-3]);
}
```
給定 seed = 7
求輸出結果
- bubble sort like
```c=
int F() {
int a[8] = {8, 7, 6, 5, 1, 2, 3, 4}
for (int i=0; i<7; i++){
for (int j=i; j<7; j++){
if (a[i+1] >= a[i]){
int temp = a[i+1];
a[i+1] = a[i];
a[i] = temp;
}
}
}
}
```
求出最後 a 的內容
- recursion, dp, math
```c=
int f(int n){
if (n>=101) return n - 10;
return f(f(n + 11));
}
```
求出 f(5) 與 f(99)
- recursion
```c++=
int i = 5;
int main(){
while (i){
i = i - 1;
main();
printf("%d", i);
}
}
```
求輸出結果
- 學生成績，填入 if 條件中的大小於，code 有用到 struct
```c=
typedef struct student_info{
...
} student_t;
```
找各科成績總和最高的
分數一樣先比數學
數學也一樣就輸出第一個找到的
兩個填空看出第一個就可以選出選項了
- nested loop, time complexity
```c=
int f(int n){
int a = 0;
for (int i=0; i<n; i++){
for (int j=1; j<=n; j = j*2){
for (int k=i; k<n; k++){
a++;
}
}
}
return a;
}
```
求 f(n) 的結果
- for loop 篩法
```c=
int a[21];
for (int i=0; i<=20; i++){
a[i] = 0;
}
for (int i=3; i<=20; i++){
if (a[i] == 0){
for (int j=i*i; j<=20; j+=i){
a[j] = 1;
}
}
}
```
求 a 最後有幾項是 1
- 費氏數列
```c=
int F(int n){
int a = 1, b = 2;
int i = 0;
int p = 0;
while (i<n){
p = a + b;
a = b;
b = p
i = i+1;
}
return p;
}
```
求出 F(9)
- 1+2+3+...+n 遞迴，多選題，上次考試出過
```c=
int sum(int n){
if (???){
return ???;
}
return n + sum(n-1);
}
```
(a) n<=1, n
(b) n<0, n+1
\(c\) n==0, 0
答案是三個都可以
- array index
```c=
int F(int n){
int A[1000] = {};
for (int i=1; i!=n; i+=2){
A[i] = 1;
}
}
```
1. 1000
2. 999
3. 0
4. -1
問 n 等於哪個選項不會造成陣列索引值錯誤
- array index
```c=
int a[10] = {10, 9, 7, 2, 3, 4, 5, 6, 1, 8};
int b[10] = {2, 1, 3, 4, 5, 6, 7, 2, 4, 5};
for (int i=0; i<10; i++){
a[b[i]-1] = b[a[i]] + 1
}
printf("%d", a[7]);
```
1. 輸出是 2
2. 輸出是 6
3. a[] 索引值錯誤
4. b[] 索引值錯誤
- queue
```c=
int Q[100];
int front = 0, end = 0;
for (int i=1; i<=15; i++){
Q[end] = i;
end = end + 1;
}
while (front + 1 < end){
}
printf("%d", front);
```
求輸出結果
- float / int 運算
```c=
int a = 7, b = 3;
float w = a / 2 / b * 1.0;
float x = a / b / 2.0;
float y = a / 2 / b;
float z = 1.0 * a / 2 / b
```
問 w, x, y, z 哪些相同
- swap
```c=
void swap(int a, int b){
printf("%d, %d", a, b);
???
b = a - b;
a = a - b;
printf("%d, %d", a, b);
}
```
求 ??? 要填入什麼可以讓 a, b 數值交換
- abs
```c=
```
## 觀念第二場
- pointer
```c=
int f(int *a, int *b);
int g(int *a, int *b);
int main(){
int a = 2, b = 5;
int x = f(&a, &b);
printf("%d %d %d", x, a, b);
}
int f(int *a, int *b){
int c = 10;
*a = *a + *b / 5;
int p = g(b, a) % 2;
if (p % 2 == 0){
return *b - p;
} else {
return *b + p;
}
}
int g(int *a, int *b){
return (*a - *b) * 5 + 2;
}
```
求輸出結果
- reverse array
```
void reverse(int a[], int n){
for (int i=0; ???; i++){
int temp = a[i];
a[i] = a[n-1-i];
a[n-1-i] = temp;
}
}
```
??? 應該填入什麼可以讓這個 function 成功把陣列的順序顛倒?
- call by value, 不會改變數值
```c=
void f(int x, int y){
int temp = x;
x = y;
y = temp;
}
int main(){
int x = 32, y = 5;
h(x, y);
printf("%d", (x-y)*(x+y + 4);
}
```
求輸出結果
- nested loop
```c=
for (int i = 1; i <= 5; i++) {
for (int j = 0; ??? ; j += 3) {
printf("[%d] ", i + j);
}
}
```
已知輸出結果為 [1][2][3][4][7][5][8], 求 ??? 應該填入什麼？
- nested loop
```c=
int f(char s[], int n){
char t[1000];
int j = 0;
for (int i=0; i<m; i++, j+=2){
if (s[i] == '0'){
t[j] = 'w';
t[j+1] = 'a';
} else if (??? || ???){
t[j] = 't';
t[j+1] = 'e';
} else if (s[i] == '3' || s[i] == '5'){
t[j] = 'd';
t[j+1] = 'o';
} else if (s[i] == '4' || s[i] == '6'){
t[j] = 'p';
t[j+1] = 'u';
} else {
t[j] = ' ';
j = j-1;
}
}
t[j] = '\0';
printf("%s ", t);
}
int main(){
char s[] = "0328675";
f(s, 8);
}
```
已知輸出結果為 "wadote putedo"，求兩個 ??? 分別應該是什麼？
- string encode
```c=
char s1[10][10] = {'A'};
char s2[10][20] = {};
```
- 後序運算式 parser
給一個運算式 "3*5/6+2-1"，求它的後序運算式
- 魔方陣
對於 a[n][n] 是一個 n 階魔方陣
1 的位置在 [n-1][(n-1)/2]
若 i 的位置在 (x, y)，且右下方沒有東西，i+1 就放在右下方
否則 i+1 方在 i 的正上方一格
給定 i 的座標 (x, y)，已知右下方有東西，求 i+1 的座標
- 陣列中奇數個數
```c=
int f(){
int a[5] = {9, 2, 4, 7, 2};
int b[10] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1};
int c = 0;
for (int i=0; i<5; i++){
c += b[a[i]];
}
return c;
}
```
求回傳值
- recursion
```c=
int f(int n){
if (n<2) retur n;
if (n / 2 % 2 == 0){
return -n * f(n-2);
} else {
return n * f(n-2);
}
}
```
求 f(8)
- stack
有一個空的 stack 依序放入 5, 3, 10, 4, 20
求這個 stack pop 的順序
- random stack
已經給定一個 stack 的實做程式法，支援 `empty`, `push(x)`, `pop()`, `top()`
```c=
int level = 1;
for (int i=0; i<6; i++){
if (empty()){
push(level);
level = level + 1;
} else if (rand() % 2 == 0){
printf("%d ", top());
pop();
level = level - 1;
} else {
push(level);
level = level + 1;
}
}
while (!empty()){
printf("%d ", top());
pop();
}
```
找出不可能的輸出結果
- 找不可能的 output
```c=
int f(int n){
if (n>17) n += 5;
while (n>=23) n -= 6;
if (n > 17) n += 2;
return n;
}
```
- array index easy
```c=
int main(){
int a[5] = {1, 7, 2, 4, 3};
int i = 2;
printf("%d ", a[i]);
i = i + 2;
printf("%d ", a[i] + 1);
}
```
求輸出結果
- switch without break
```c=
int main(){
char c = 'a';
switch(c){
case 'a':
printf("a");
case 'b':
printf("b");
case 'c':
printf("c");
default:
printf("d");
}
}
```
求輸出結果
- binary search
```c=
int f(int a[], int s, int f) {
int min = 0, max = s-1;
while (min < max){
int mid = (min + max) / 2;
if (f > a[mid]){
l = mid + 1;
} else if (f < a[mid]){
r = mid - 1;
} else {
return mid;
}
}
return -1;
}
int main(){
int a[8] = {2, 3, 3, 5, 8, 8, 8, 8};
printf("%d", f(a, 8, 8));
}
```
求輸出結果
Sign in with Wallet
Connect another wallet