112 年 國立高雄大學資訊工程學系碩士班《離散數學與資料結構》

核心觀念

本題考查「非負整數解」與「正整數解」的計數，主要使用隔板法（Stars and Bars）。

對方程式

$$x_1+x_2+\cdots+x_k=n$$

而言：

• 若 $x_i\geq 0$，非負整數解的個數為

$$\binom{n+k-1}{k-1}.$$

• 若 $x_i>0$，正整數解的個數可先令

$$y_i=x_i-1,$$

將問題轉換為非負整數解。

---

解題方法

（a）$x_i\geq 0$

題目為

$$x_1+x_2+x_3+x_4+x_5=8,$$

其中五個變數皆為非負整數。

可將 $8$ 個相同物品分配給 $5$ 個變數，使用 $4$ 個隔板分成 $5$ 組。例如：

$$＊＊|＊||＊＊＊|＊$$

表示

$$(x_1,x_2,x_3,x_4,x_5)=(2,1,0,3,1).$$

因此需要排列 $8$ 個星號與 $4$ 個隔板，共 $12$ 個位置，選出 $4$ 個位置放隔板：

$$\binom{8+5-1}{5-1} = \binom{12}{4}.$$

計算得

$$\binom{12}{4} = \frac{12\cdot11\cdot10\cdot9}{4\cdot3\cdot2\cdot1} =495.$$

所以，（a）的整數解共有

$$\boxed{495\text{ 組}}.$$

---

（b）$x_i>0$

題目為

$$x_1+x_2+x_3+x_4+x_5=8,$$

且每個變數皆為正整數。

先令

$$y_i=x_i-1,$$

核心觀念

本題考查：

• 乘法原理：連續完成多個步驟時，總方法數為各步驟方法數的乘積。
• 補集原理與容斥原理：計算「三種顏色皆至少出現一次」的序列數。
• 每個紅綠燈的位置 $L_1,\ldots,L_6$ 均有明確區別，因此序列順序不同，即視為不同方法。

---

解題方法

（a）六個紅綠燈的所有可能序列

每個紅綠燈皆可顯示：

• 紅燈
• 黃燈
• 綠燈

因此每一個位置都有 $3$ 種選擇，且六個位置可獨立選擇。依乘法原理：

$$3\times 3\times 3\times 3\times 3\times 3=3^6=729$$

所以共有：

$$\boxed{729\text{ 種}}$$

---

（b）三種顏色皆至少出現一次

設全集 $U$ 為所有六個紅綠燈的顏色序列，則：

$$|U|=3^6$$

定義：

• $R$：沒有紅燈
• $Y$：沒有黃燈
• $G$：沒有綠燈

題目要求的是紅、黃、綠三種顏色皆至少出現一次，也就是不屬於 $R\cup Y\cup G$ 的序列。因此使用容斥原理：

$$|U-(R\cup Y\cup G)| = |U|-|R\cup Y\cup G|$$

計算沒有某一種顏色的情形

例如沒有紅燈時，每個位置只能選黃燈或綠燈：

$$|R|=2^6$$

同理：

$$|Y|=|G|=2^6$$

因此單獨扣除三種情形共：

核心觀念

本題考查：

1. 鴿籠原理（Pigeonhole Principle）。
2. 同餘與整除的關係：
   $a\equiv b\pmod 7 \iff 7\mid(a-b)。$

鴿籠原理指出：若將超過 $m$ 個物件放入 $m$ 個鴿籠，則至少有兩個物件會落在同一個鴿籠。更一般地，若有 $N$ 個物件放入 $m$ 個鴿籠，則某一鴿籠至少包含 $\left\lceil N/m\right\rceil$ 個物件。

---

(a) 鴿籠原理的定義

若有 $m+1$ 個物件分配到 $m$ 個鴿籠中，則至少有一個鴿籠包含至少兩個物件。

在數學證明中，通常將：

• 要分配的物件視為「鴿子」；
• 可分類的位置視為「鴿籠」。

只要物件數量大於分類數量，就能保證至少有兩個物件屬於同一類。

---

(b) 解題方法

題目中的整數集合為

$$S=\{3^n,4^n,5^n,6^n,7^n,8^n,9^n,10^n\}.$$

其中共有 $8$ 個整數。將每個整數依照除以 $7$ 的餘數分類，可能的餘數只有

$$0,1,2,3,4,5,6,$$

共 $7$ 類，因此可將這 $7$ 個餘數視為 $7$ 個鴿籠。

由於 $S$ 中有 $8$ 個整數，而餘數類別只有 $7$ 類，根據鴿籠原理，必定存在兩個不同的元素 $x,y\in S$，除以 $7$ 時具有相同的餘數。也就是說，

$$x\equiv y\pmod 7.$$

依同餘的定義可得

核心觀念

本題適合使用**游程編碼（Run-Length Encoding, RLE）**壓縮資料。其核心定義是：

將連續出現的相同資料，表示成「資料值＋連續次數」的形式。

例如：

$$xxxxxx \rightarrow (x,6)$$

原序列為：

$$\texttt{ppxxxxxxpaaabapaaabff}$$

依照連續相同字元分段：

$$\texttt{pp}\ |\ \texttt{xxxxxx}\ |\ \texttt{p}\ |\ \texttt{aaa}\ |\ \texttt{b}\ |\ \texttt{p}\ |\ \texttt{aaa}\ |\ \texttt{b}\ |\ \texttt{ff}$$

共有 $9$ 個游程。

---

解題方法

1. 資料結構

使用一個由記錄組成的陣列，每筆記錄包含：

• symbol：字元
• count：該字元連續出現的次數

壓縮後的資料為：

$$[(\texttt{p},2),(\texttt{x},6),(\texttt{p},1), (\texttt{a},3),(\texttt{b},1),(\texttt{p},1), (\texttt{a},3),(\texttt{b},1),(\texttt{f},2)]$$

也可寫成：

$$\texttt{p2 x6 p1 a3 b1 p1 a3 b1 f2}$$

其中每個二元組代表一段連續相同的字元。

2. 編碼演算法

從左至右掃描原始序列，維護目前字元與其連續次數：

RLE(sequence):
    result = empty list
    i = 0

    while i < length(sequence):
        symbol = sequence[i]
        count = 1
        i = i + 1

        while i < length(sequence)
              and sequence[i] == symbol:
            count = count + 1
            i = i + 1

        append (symbol, count) to result

    return result

套用於本題：

1. 讀到 pp，形成 $(\texttt{p},2)$。
2. 讀到 xxxxxx，形成 $(\texttt{x},6)$。
3. 後續依序形成 $(\texttt{p},1)$、$(\texttt{a},3)$、$(\texttt{b},1)$。
4. 再處理第二組 paaab。
5. 最後 ff 形成 $(\texttt{f},2)$。

因此壓縮結果為：

$$\boxed{ (\texttt{p},2),(\texttt{x},6),(\texttt{p},1), (\texttt{a},3),(\texttt{b},1),(\texttt{p},1), (\texttt{a},3),(\texttt{b},1),(\texttt{f},2) }$$

3. 解碼方式

若要還原原始序列，對每個二元組重複輸出 symbol 共 count 次：

核心觀念

此題考查單向鏈結串列中「指標重新連結」的效果。

若 a 是指向某個節點的指標，則：

• *a 表示 a 所指向的節點。
• (*a).link 表示該節點的 link 欄位。
• (*a).link = a 將該節點的 link 指標改為指向 a 所指向的節點本身。

解題方法

設 a 原本指向節點 $A$，且原本的鏈結關係為：

$$A \rightarrow B \rightarrow \cdots$$

執行：

(*a).link = a;

後，節點 $A$ 的 link 會被改寫成指向自己：

$$A \rightarrow A$$

因此，$A$ 形成一個自我迴圈（self-loop）。

原本由 $A$ 的 link 所指向的後續節點 $B$，不再能從 $A$ 沿著 link 欄位走到。若沒有其他指標指向 $B$ 或其後續節點，這些節點將失去可達性，形成記憶體遺失。

執行結果

核心觀念與指標調整

在雙向環狀鏈結串列（Circular Doubly Linked List）中，將獨立節點 $B$ 插入至節點 $A$ 之前，目標是將鏈結順序調整為 $A\text{->prev} \leftrightarrow B \leftrightarrow A$。必須更新 4 個指標連結：

1. $B$ 的前驅指標（prev）指向 $A$ 的前驅節點（A->prev）。
2. $B$ 的後繼指標（next）指向 $A$。
3. $A$ 原前驅節點的後繼指標指向 $B$。
4. $A$ 的前驅指標更新指向 $B$。

---

精簡關鍵程式碼（C / C++）

核心觀念

本題考查的是「有限二維搜尋空間中的全域最佳化」，重點不是直接微分求出數值，而是設計：

1. 能保存候選區域的資料結構；
2. 能系統性搜尋整個定義域的演算法；
3. 能區分區域極大值與全域極大值。

函數定義在封閉矩形區域

$$D=[-3,3]\times[-3,3].$$

由於 $f(x,y)$ 是由多項式與指數函數組成的連續函數，而 $D$ 是有界閉集合，因此依據魏爾斯特拉斯極值定理，$f$ 在 $D$ 上必定存在全域最大值。

單純使用梯度上升法，只能保證收斂到某個局部最大值，無法保證找到全域最大值。因此本題適合使用「分支限界法」搭配最大堆積（max-heap）。

---

解題方法：二維分支限界法

將整個搜尋區域切割成許多小矩形。對每個矩形 $R$ 維護：

• 一個目前已知的函數值下界；
• 一個該矩形內函數值的上界；
• 矩形的範圍；
• 該矩形內目前找到的最佳候選點。

若某個矩形的上界已經不可能超過目前最佳解，就可以直接捨棄該矩形，不必繼續搜尋。

1. 矩形節點的表示

令矩形

$$R=[x_{\min},x_{\max}]\times[y_{\min},y_{\max}].$$

每個節點可定義為：

$$\text{Node}= (R,\ U(R),\ L(R),\ (x_c,y_c)),$$

其中：

• $U(R)$：矩形 $R$ 內 $f$ 的安全上界；
• $L(R)$：矩形 $R$ 內已找到的函數值下界；
• $(x_c,y_c)$：目前的候選點，通常取矩形中心；
• $R$：矩形本身。

以矩形中心

$$x_c=\frac{x_{\min}+x_{\max}}{2},\qquad y_c=\frac{y_{\min}+y_{\max}}{2}$$

作為候選點，則

$$L(R)=f(x_c,y_c).$$

為了使上界正確，可使用區間算術計算 $f(R)$。若區間算術得到

$$f(R)\subseteq [a,b],$$

則可令

$$U(R)=b.$$

因為所有 $(x,y)\in R$ 都滿足

$$f(x,y)\leq U(R).$$

---

2. 使用最大堆積選擇搜尋區域

使用最大堆積依照 $U(R)$ 排序，讓上界最大的矩形優先取出。

最大堆積的根節點永遠代表「最有希望產生全域最大值」的區域。每次取出該矩形後，將它分割成四個子矩形：

$$R_1,R_2,R_3,R_4.$$

再分別計算各子矩形的上界與候選點，加入最大堆積。

目前最佳解以全域變數維護：

$$f_{\text{best}}=f(x_{\text{best}},y_{\text{best}}).$$

若某個矩形滿足

$$U(R)\leq f_{\text{best}}+\varepsilon,$$

則即使該矩形內存在真正最大值，也只會比目前最佳值高出至多 $\varepsilon$，因此可以安全刪除。

其中 $\varepsilon$ 是允許誤差，例如 $10^{-8}$。

---

3. 上界的計算方式

方法一：區間算術

令

$$A=(1-x)^2e^{-x^2-(y+1)^2},$$ $$B=(x-x^3-y^3)e^{-x^2-y^2},$$

則

$$f(x,y)=A-B.$$

將 $x$、$y$ 分別以區間表示，透過區間加減乘除與指數運算，可以得到 $f(R)$ 的區間範圍。其上端即為 $U(R)$。

這種方法的優點是上界具有數學保證；缺點是矩形較大時，區間估計可能較寬，導致需要多切割幾次。

方法二：利用梯度建立 Lipschitz 上界

若在矩形 $R$ 中可以找到梯度範數上界 $M_R$，則對任意 $(x,y)\in R$：

$$f(x,y)\leq f(x_c,y_c)+M_R\|(x,y)-(x_c,y_c)\|.$$

因此可令

$$U(R)=f(x_c,y_c)+M_Rr_R,$$

其中 $r_R$ 是矩形中心到最遠角落的距離：

$$r_R= \sqrt{ \left(\frac{x_{\max}-x_{\min}}{2}\right)^2+ \left(\frac{y_{\max}-y_{\min}}{2}\right)^2 }.$$

梯度可由下式計算。令

$$P=x-x^3-y^3,$$

則

$$\frac{\partial f}{\partial x} = e^{-x^2-(y+1)^2} \left[-2(1-x)-2x(1-x)^2\right] - e^{-x^2-y^2} \left[(1-3x^2)-2xP\right],$$

以及