109 年 國立暨南國際大學資訊工程學系碩士班《資料結構與演算法》

核心觀念

本題比較兩種計算 Fibonacci 數列的方法：

• 遞迴法：同一個子問題會被重複計算。
• 動態規劃法：每個 $F(i)$ 只計算一次，並儲存已求出的結果。

題目定義為：

$$F(n)=F(n-1)+F(n-2)$$

且

$$F(0)=1,\qquad F(1)=1$$

每次計算 $F(n-1)+F(n-2)$，就會執行一次加法運算。

---

解題方法

a. 使用遞迴法計算 $F(12)$

令 $A(n)$ 表示以純遞迴方式計算 $F(n)$ 時所執行的加法次數。

當 $n=0$ 或 $n=1$ 時，直接回傳種子值，不需加法：

$$A(0)=A(1)=0$$

當 $n\ge 2$ 時，除了計算 $F(n-1)$ 與 $F(n-2)$，還需執行目前這一層的 1 次加法，因此：

$$A(n)=A(n-1)+A(n-2)+1$$

逐步計算：

$$\begin{aligned} A(2)&=0+0+1=1\\ A(3)&=1+0+1=2\\ A(4)&=2+1+1=4\\ A(5)&=4+2+1=7\\ A(6)&=7+4+1=12\\ A(7)&=12+7+1=20\\ A(8)&=20+12+1=33\\ A(9)&=33+20+1=54\\ A(10)&=54+33+1=88\\ A(11)&=88+54+1=143\\ A(12)&=143+88+1=232 \end{aligned}$$

因此，純遞迴法計算 $F(12)$ 時，會執行：

$$\boxed{232\text{ 次加法}}$$

也可從遞迴樹理解：每個非基底節點都代表一次加法，而遞迴樹中的非基底節點數即為 232。

---

b. 使用動態規劃法計算 $F(12)$

核心觀念

AVL tree 是一棵二元搜尋樹，且每個節點都必須滿足平衡條件。對節點 $v$ 定義平衡因子：

$$BF(v)=h(v.left)-h(v.right)$$

其中 $h(\cdot)$ 表示子樹高度。

AVL tree 的合法範圍為：

$$-1\le BF(v)\le 1$$

插入或刪除節點後，若某節點 $z$ 的平衡因子超出範圍，就必須透過旋轉恢復平衡。旋轉類型取決於：

1. 失衡節點 $z$ 是左重或右重；
2. 造成失衡的子節點 $y$ 是左重或右重。

四種情況如下：

情況	失衡方向	子樹方向	修正方式
L-L	左左	$z$ 的左子樹之左側	對 $z$ 做右旋
R-R	右右	$z$ 的右子樹之右側	對 $z$ 做左旋
L-R	左右	$z$ 的左子樹之右側	先對 $z.left$ 左旋，再對 $z$ 右旋
R-L	右左	$z$ 的右子樹之左側	先對 $z.right$ 右旋，再對 $z$ 左旋

---

解題方法

設 $z$ 為從插入或刪除位置往樹根方向移動時，第一個失衡的節點，設 $y$ 為 $z$ 的較高子節點。

使用平衡因子判斷：

• $BF(z)>1$：$z$ 左重。
  • $BF(y)\ge 0$：L-L。
  • $BF(y)<0$：L-R。
• $BF(z)<-1$：$z$ 右重。
  • $BF(y)\le 0$：R-R。
  • $BF(y)>0$：R-L。

在插入情況下，也可直接依照新節點與 $z$、$y$ 的鍵值大小判斷；但使用子節點的平衡因子更一般，亦適用於刪除後的重新平衡。

---

判斷旋轉類型的 C-like pseudo-code

enum RotationType {
    NONE,
    LL,
    RR,
    LR,
    RL
};

int balanceFactor(Node *v) {
    if (v == NULL)
        return 0;

    return height(v->left) - height(v->right);
}

RotationType determineRotation(Node *z) {
    int bz = balanceFactor(z);

    // z 左重
    if (bz > 1) {
        int by = balanceFactor(z->left);

        // 左子樹左重或平衡
        if (by >= 0)
            return LL;

        // 左子樹右重
        return LR;
    }

    // z 右重
    if (bz < -1) {
        int by = balanceFactor(z->right);

        // 右子樹右重或平衡
        if (by <= 0)
            return RR;

        // 右子樹左重
        return RL;
    }

    return NONE;
}

其中，$BF(y)=0$ 的情況主要會出現在刪除節點後，因此：

• 左重時以 $BF(y)\ge 0$ 判定為 L-L；
• 右重時以 $BF(y)\le 0$ 判定為 R-R。

---

執行對應旋轉

Node* rebalance(Node *z) {
    int type = determineRotation(z);

    switch (type) {
        case LL:
            // 對 z 做右旋
            return rotateRight(z);

        case RR:
            // 對 z 做左旋
            return rotateLeft(z);

        case LR:
            // 先左旋 z 的左子樹，再右旋 z
            z->left = rotateLeft(z->left);
            return rotateRight(z);

        case RL:
            // 先右旋 z 的右子樹，再左旋 z
            z->right = rotateRight(z->right);
            return rotateLeft(z);

        case NONE:
        default:
            return z;
    }
}

---

四種情況說明

1. L-L 情況

若：

$$BF(z)>1,\qquad BF(z.left)\ge 0$$

核心觀念

在計算幾何（Computational Geometry）中，凸包問題（Convex Hull Problem）是基礎且核心的研究主題：
給定二維平面上包含 $n$ 個點的集合 $S$，凸包 $\text{CH}(S)$ 是包含 $S$ 中所有點的最小凸多邊形。求解凸包即為依序（順時針或逆時針）找出構成此凸多邊形邊界的頂點集合。令 $n$ 為輸入點的總數，$h$ 為最終凸包上的頂點個數（$3 \le h \le n$）。

本題比較求解凸包的兩種經典演算法：

1. Package Wrapping Method（禮物包裝法，又稱 Jarvis March）：屬於輸出敏感演算法（Output-Sensitive Algorithm），利用類似用繩子將外圍點逐步纏繞包裹的直觀幾何操作。
2. Graham's Scan Method（葛立恆掃描法）：屬於基於排序的演算法（Sorting-Based Algorithm），透過極座標角度預先排序，並利用**堆疊（Stack）**進行線性單調掃描與回溯。

兩者在底層判斷「轉折方向」時，皆依賴三點的外積（Cross Product）或行列式運算（$\text{CCW}$ 測試）：

$$\text{CCW}(p_1, p_2, p_3) = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)$$

• $\text{CCW} > 0$：代表從向量 $\vec{p_1 p_2}$ 到 $\vec{p_1 p_3}$ 為逆時針轉折（左轉）。
• $\text{CCW} < 0$：代表為順時針轉折（右轉）。
• $\text{CCW} = 0$：代表三點共線（Collinear）。

---

解題方法：演算法步驟詳解

1. Package Wrapping Method (Jarvis March)

• 步驟 1（找起點）：從點集 $S$ 中找出一個保證在凸包上的極值點 $p_0$（通常選 $y$ 座標最小者；若有相同者則取 $x$ 座標最小者）。
• 步驟 2（尋找下一點）：令當前凸包頂點為 $p_i$。在剩下的點中挑選一個點 $p_{i+1}$，使得對所有 $r \in S \setminus \{p_i, p_{i+1}\}$，向量轉折皆滿足 $\text{CCW}(p_i, p_{i+1}, r) \ge 0$（即所有點都在射線 $p_i p_{i+1}$ 的同一側／最外側逆時針方向）。
• 步驟 3（迭代包裝）：將 $p_{i+1}$ 加入凸包頂點序列，並令 $p_i \leftarrow p_{i+1}$。
• 步驟 4（終止條件）：重複步驟 2 與 3，直到選出的下一個頂點繞回起始點 $p_0$ 為止。

2. Graham's Scan Method

• 步驟 1（找基準點）：找出 $y$ 座標最小（若相同則選 $x$ 座標最小）的點作為基準點 $p_0$。
• 步驟 2（極角排序）：計算其餘 $n-1$ 個點相對於 $p_0$ 的極座標角度（Polar Angle），並按角度由小到大排序；若有極角相同者，僅保留距離 $p_0$ 最遠的點。
• 步驟 3（初始化堆疊）：建立一個堆疊 $\text{Stack}$，依序將基準點 $p_0$ 及排序後的前兩點 $p_1, p_2$ 推入（Push）堆疊中。
• 步驟 4（單調掃描）：對排序後的其餘各點 $p_i$（$i = 3 \dots n-1$）：
  • 檢查堆疊次頂端點（$\text{Next-to-Top}$）、頂端點（$\text{Top}$）與當前點 $p_i$ 的轉向關係。
  • 當 $\text{CCW}(\text{Next-to-Top}, \text{Top}, p_i) \le 0$（非左轉，即右轉或共線）時，代表 $\text{Top}$ 必定落於多邊形內部，將 $\text{Top}$ 彈出（Pop）。
  • 重複彈出直到構成嚴格左轉，接著將 $p_i$ 推入堆疊。
• 步驟 5（產出結果）：所有點掃描完成後，堆疊中留存的點即為凸包頂點。

---

詳細比較分析

兩演算法的各項指標對比如下表所示：

比較項目	Package Wrapping (Jarvis March)	Graham's Scan
設計典範	貪婪搜尋 / 輸出敏感型（Output-Sensitive）	預處理排序 + 堆疊單調掃描（Incremental/Scan）

核心觀念

本題考查「具有 $n$ 個節點的不同二元樹數量」，其結果由 Catalan 數（卡特蘭數）給出。

二元樹的每個節點最多有左子樹與右子樹，且左、右子樹的位置不同，因此交換左右子樹會形成不同的二元樹。

具有 $n$ 個節點的二元樹數量為：

$$C_n=\frac{1}{n+1}\binom{2n}{n}$$

其中 $C_n$ 為第 $n$ 個 Catalan 數。

---

解題方法：使用遞迴關係

設 $T_n$ 表示具有 $n$ 個節點的不同二元樹數量。

固定一個根節點後，剩下的 $n-1$ 個節點必須分配到左子樹與右子樹。若左子樹有 $i$ 個節點，右子樹就有 $n-1-i$ 個節點，因此：

$$T_n=\sum_{i=0}^{n-1}T_iT_{n-1-i}$$

初始條件為：

$$T_0=1$$

$T_0=1$ 代表空樹只有一種結構。

依序計算：

$$T_1=T_0T_0=1$$ $$T_2=T_0T_1+T_1T_0=2$$ $$T_3=T_0T_2+T_1T_1+T_2T_0 =2+1+2=5$$ $$T_4=T_0T_3+T_1T_2+T_2T_1+T_3T_0 =5+2+2+5=14$$

因此：