# 清大 101 軟體
###### tags: `NTHU` `101` `軟體`
1. S + [(i-1) * Y + j - 1] * B
2. (a) 令 start 指向第一個元素，end 指向最後一個元素的後一個位置。
保留一個位置不用，就可以用 start == end 判斷是否為空，end == start - 1 判斷是否滿
(b) 增加一個 empty bit 來代表 queue 是否為空。則可以用 start == end && empty 判斷是否為空，用 start == end && !empty 判斷是否滿
3. (a) F (b) F \(c\) F (d) F (e) T
4. BJ4
5. $n_k=n_{k-1}+n_{k-2}+n_{k-3},n_1=2,n_2=4,n_3=7$
7. $(n+1)!,(lgn)!,(\frac{3}{2})^n,lgn^{lgn}[n^2,4^{lgn}][lg(n!), nlgn]$
:::info
$lgn^{lgn},(\frac{3}{2})^n,(lgn)!$ 還要再想想
:::
7.
$$
B_n=\sum^{n}_{i=1}B_{i-1}B_{n-i}, B_0=B_1=1\\
H_n=2H_{n-1}(1+\sum^{n-2}_{i=0}H_i)+H_{n-1}H_{n-1},H_0=1
$$
8. BJ4
9. BJ4
10. BJ4
11. (a) 200 (b) 316
12. (a) 14 (b) 7
13. (a)
$$
X=\{1,2,3,4,5,6\}\\
S_1=\{1,2,3\},S_2=\{1,4\},S_3=\{2,5\},S_4=\{3,6\}
$$
greedy 會挑出全部，但 optimal 為 $S_1,S_2,S_3$
(b) 這個問題是 minimum edge-cover probem，可先找出 maximum matching，再貪心地找 minimum edge cover
14. 給定一個 n，欲判定其是否為質數，可先解 2-tuple optimization problem，再判斷最佳解是否小於 n+1
轉換過程的時間複雜度是多項式時間，因此若 n-tuple optimization problem 有多項式時間解，則質數判定必有多項式時間解