# 106/03/04 APCS考古題觀念題練習1~7題

1. 輸入16會找到超出A陣列

2. F函式的用處是打出某個數量的*持續等同此數可以除以2的數量
比如輸入4
會先有****
再來在執行2次的F(4/2)
分別在打出兩次**
再來會在執行四次F(2/1)，四次的*
總共12個*
**如果是基數會有特殊的情形**
比如輸入5
會先有*****
再來只會執行F(2)兩次，也就跟上個的後半部一樣
但第一次是五個*，所以F(5)比F(4)多一個*
**n在題目中是整數**
(A)
A1：F(1), F(4)是1+12=13個*
A2：F(2), F(3)是4+5=9個
(B)
A1：F(2), F(10)是4+36=40, F(10)是10加兩個F(5)
A2：F(5), F(7)是13+17=30, F(7)是7加兩個F(3)
(C\)
A1：F(2), F(11)是4+37=41, F(11)是11加兩個F(5)
A2：F(5), F(8)是13+32=45, F(8)是8加上兩個F(4)
(D)
A1：F(3), F(12)是5+44=49, F(12)是12加上兩個F(6)，F(6)是6加上兩個F(3)
A2：F(6), F(9)是16+33=49

3. 這題一樣可以暴力解，跟上一題差不多
(A)
F(14)=14*F(13)=14*13*F(12)一定>40(越乘越大)
(B)
F(14)=14+F(11)=14+11+F(8)=14+11+8+F(5)=14+11+8+5+F(2)=14+11+8+5+2=40
(C\)
F(14)=14-F(12)一定<40(越減越小)
(D)
F(14)=F(42+1)無解，永遠不會<4並輸出

4. 理論
r==0代表a整除b
最大公因數是a, b可以整除的最大數字(15和6的最大公因數是3)
如果a剛好可以被b整除，勢必b就是最大公因數，所以第一格是b
再來需要一個演算法叫做**輾轉相除法**
簡單來說：大數/小數=整數...餘數，再把小數/餘數=整數...餘數2，然後再把剛剛的被除數「餘數」除剛剛的「餘數２」，以此類推
總之，上一個的除數要變成下一個的被除數
所以第二格是GCD(b, r)
5. p會被陣列最大值取代，q會被陣列最小值取代，但若沒有大於或小於的值p=q=A[0]
6. 這個程式的問題是rowsume沒有歸0，所以第一個值會是對的，之後的就不一定了，程式執行上沒有問題
7. 我們用一表示一次\
B(5, 2)
=B(4, 1)+B(4, 2)
=B(3, 0)+B(3, 1)+B(3, 1)+B(3, 2)
=三+B(2, 0)+B(3, 0)+B(2, 0)+B(3, 0)