# 台大 99 軟體
###### tags: `NTU` `99` `軟體`
1.

count[0] = 34
count[1] = 55
count[2] = 34
count[3] = 21
count[4] = 13
count[5] = 8
count[6] = 5
count[7] = 3
count[8] = 2
count[9] = 1
count[10] = 1

fab(n) 會被 fab(n+1) 和 fab(n+2) 呼叫。所以 fab(n) 的呼叫次數會是 fab(n+1) 和 fab(n+2) 的次數加總。
但 fab(0) 例外。fab(0) 不會被 fab(1) 呼叫，只會被 fab(2) 呼叫，所以 count[0] = count[2]

2.

for (int i = 0; i < 20; i++) {
    if ((x = delete()) == 0)
        insert(0);
    printf("%d\n", x);
    insert(x + peek());
}

3. (a) 將 MAX-HEAPIFY 改一改就好。
(b)
- Build heap: $\sum_{h=0}^{\infty}\frac{n}{d^h}h=O(\frac{nd}{(d-1)^2})$
- remove max: $log_dn$
- total: $O(nlog_dn+\frac{nd}{(d-1)^2})$

4. (a) $A_1(((A_2A_3)A_4)A_5)$
(b) 146000

5.

bool detect(G = (V, E))
{
    let n = |V|;
    bool visited[n] = [false; n];
    Queue q;
    q.insert(s); // choose s (in G) arbitrarily
    visited[s] = true;

    while(!q.empty()) {
        v = q.pop();
        for each u in Adj[v] {
            if (visited[u])
                return false;
            visited[u] = true;
            q.insert(u);
            
        }
    }
    return true;
}

環的最大長度為 |V|，所以最多走訪 |V| 條邊即可知道是否有環。

6. (a) [6A] = $R\cap C_i$, [6B] = $C_i$
(b)