109 年 國立成功大學製造資訊與系統研究所丙組《計算機概論》

核心觀念

四變數卡諾圖以 $A,B$ 為列、$C,D$ 為欄，並依 Gray code 排列：

• 列：$AB=00,01,11,10$
• 欄：$CD=00,01,11,10$

卡諾圖分組規則：

• 求最小 SOP：圈選輸出為 $1$ 的格子，$d$ 可視需要納入分組。
• 求最小 POS：圈選輸出為 $0$ 的格子，$d$ 可視需要納入分組。
• 每組格數必須為 $1,2,4,8,\ldots$，且可上下、左右相鄰，邊界也視為相鄰。
• SOP 中，一組 $1$ 對應一個乘積項；POS 中，一組 $0$ 對應一個和項。

本題的關鍵差異是：

• $\prod M(\cdots)$：列出的 maxterm 編號是 $F=0$ 的位置。
• $\sum m(\cdots)$：列出的 minterm 編號是 $F=1$ 的位置。

---

(a) $F(A,B,C,D)=\prod M(1,2,3,5,6,9)\cdot d(4,12,13)$

因此：

• $F=0$：$1,2,3,5,6,9$
• $F=d$：$4,12,13$
• $F=1$：其餘位置，即 $0,7,8,10,11,14,15$

最小 SOP

圈選 $1$ 與適當的 don't-care：

1. 分組 $\{0,4,8,12\}$：

   其中 $C=0,D=0$ 固定，得到

   $C'D'$

2. 分組 $\{10,11,14,15\}$：

   其中 $A=1,C=1$ 固定，得到

   $AC$

3. 分組 $\{5,7,13,15\}$：

   $5,13$ 是 don't-care，四格中 $B=1,C=1$ 固定，得到

   $BC$

因此最小 SOP 為

$$F=C'D'+AC+BC$$

---

最小 POS

求 POS 時圈選 $0$ 與適當的 don't-care。

1. 分組 $\{1,5,9,13\}$：

   $C=0,D=1$ 固定。對於 $0$ 分組，固定值為 $0$ 的變數寫未反相，固定值為 $1$ 的變數寫反相，因此得到

   $C+D'$

2. 分組 $\{2,3\}$：

   $A=0,B=0,C=1$ 固定，得到

   $A+B+C'$

3. 分組 $\{2,6\}$：

   $A=0,C=1,D=0$ 固定，得到

   $A+C'+D$

因此最小 POS 為

$$F=(C+D')(A+B+C')(A+C'+D)$$

---

(b) $F(A,B,C,D)=\sum m(1,2,3,5,6,9)+\sum d(4,12,13)$

因此：

此題考驗組合數學中的「隔板法」(Stars and Bars) 以及相關的計數技巧。

核心觀念：

1. 隔板法 (Stars and Bars)： 將 $n$ 個相同的物品分配到 $k$ 個不同的箱子。
   • 若箱子可以為空：有 $\binom{n+k-1}{k-1}$ 種方法。
   • 若箱子每個至少一個：先放入一個物品，剩下 $n-1$ 個物品分配到 $k$ 個箱子，有 $\binom{(n-1)+k-1}{k-1} = \binom{n-1}{k-1}$ 種方法。

部分 1: 至少四個機器人分配到五條生產線

問題：將 36 個相同的機器人分配到 5 條不同的生產線，要求每條生產線至少有 4 個機器人。

設 $x_i$ 為分配給第 $i$ 條生產線的機器人數量，其中 $i = 1, 2, 3, 4, 5$。
我們需要找到非負整數解的數量，滿足：
$x_1 + x_2 + x_3 + x_4 + x_5 = 36$
且 $x_i \ge 4$ 對於所有 $i \in \{1, 2, 3, 4, 5\}$。

為了解決 $x_i \ge 4$ 的條件，我們進行變數替換。
令 $y_i = x_i - 4$。由於 $x_i \ge 4$，所以 $y_i \ge 0$。
將 $x_i = y_i + 4$ 代入原方程式：
$(y_1 + 4) + (y_2 + 4) + (y_3 + 4) + (y_4 + 4) + (y_5 + 4) = 36$
$y_1 + y_2 + y_3 + y_4 + y_5 + 20 = 36$
$y_1 + y_2 + y_3 + y_4 + y_5 = 36 - 20$
$y_1 + y_2 + y_3 + y_4 + y_5 = 16$

現在我們需要找到 16 個非負整數 $y_i$ 的組合數量，這是一個標準的隔板法問題。
物品數量 $n' = 16$ (星星，Stars)。
箱子數量 $k = 5$ (生產線)。
需要 $k-1 = 4$ 個隔板 (Bars)。

總共有 $n' + k - 1 = 16 + 5 - 1 = 20$ 個位置，從中選擇 $k-1 = 4$ 個位置給隔板。
方法數為 $\binom{n' + k - 1}{k-1} = \binom{20}{4}$。

計算 $\binom{20}{4}$:
$\binom{20}{4} = \frac{20!}{4!(20-4)!} = \frac{20!}{4!16!} = \frac{20 \times 19 \times 18 \times 17}{4 \times 3 \times 2 \times 1}$
$= \frac{20}{4 \times 1} \times \frac{18}{3 \times 2} \times 19 \times 17$
$= 5 \times 3 \times 19 \times 17$
$= 15 \times 19 \times 17$
$= 285 \times 17$

$285 \times 17 = 285 \times (10 + 7) = 2850 + 285 \times 7$
$285 \times 7 = (300 - 15) \times 7 = 2100 - 105 = 1995$
$2850 + 1995 = 4845$

所以，至少有四個機器人分配到每條生產線的方法數是 4845 種。

詳細步驟：

1. 定義變數：設 $x_1, x_2, x_3, x_4, x_5$ 為分配給五條生產線的機器人數量。
2. 建立方程式：$x_1 + x_2 + x_3 + x_4 + x_5 = 36$。
3. 建立限制條件：$x_i \ge 4$ for $i=1, \dots, 5$。
4. 進行變數替換以滿足非負條件：令 $y_i = x_i - 4 \ge 0$。
5. 轉換方程式：$y_1 + y_2 + y_3 + y_4 + y_5 = 16$。
6. 套用隔板法：計算將 16 個相同物品分配到 5 個不同箱子的方法數。
7. 計算結果：$\binom{16+5-1}{5-1} = \binom{20}{4} = 4845$。

部分 2: 至少四個，但最多十個機器人分配到五條生產線

問題：將 36 個相同的機器人分配到 5 條不同的生產線，要求每條生產線至少有 4 個機器人，且最多有 10 個機器人。

設 $x_i$ 為分配給第 $i$ 條生產線的機器人數量。
我們需要找到整數解的數量，滿足：
$x_1 + x_2 + x_3 + x_4 + x_5 = 36$
且 $4 \le x_i \le 10$ 對於所有 $i \in \{1, 2, 3, 4, 5\}$。

首先，處理下限條件 $x_i \ge 4$。
令 $y_i = x_i - 4$，則 $y_i \ge 0$。
方程式變為 $y_1 + y_2 + y_3 + y_4 + y_5 = 16$。

現在處理上限條件 $x_i \le 10$。
將 $x_i = y_i + 4$ 代入 $x_i \le 10$：
$y_i + 4 \le 10$
$y_i \le 6$

所以，我們需要找到非負整數 $y_i$ 的數量，滿足：
$y_1 + y_2 + y_3 + y_4 + y_5 = 16$
且 $0 \le y_i \le 6$ 對於所有 $i \in \{1, 2, 3, 4, 5\}$。

這個問題可以使用「排容原理」(Inclusion-Exclusion Principle) 來解決。
總共有 $N = \binom{16+5-1}{5-1} = \binom{20}{4} = 4845$ 種方法，不考慮上限。

這題是作業系統中關於「程序控制（Process Control）」的經典考題，核心觀念在於測試考生是否清楚理解 fork() 系統呼叫的返回值機制、父子程序的執行流程分流，以及 exec() 系列函數如何替換當前程序的記憶體映像。解題關鍵在於掌握 fork() 會在父程序返回子程序的 PID（非零值），而在子程序返回 0，藉此判斷式決定執行路徑；同時必須記住一旦呼叫 exec() 成功，該程序原本的後續程式碼將不會再執行，因為整個程序空間已被新程式取代。

解題過程分析

我們將逐步追蹤 ProgramP 的執行流程，假設初始程序為 $P_0$（即執行 main() 的程序）。

步驟 1：第一個 fork() 呼叫
程式進入 main() 後首先執行條件判斷：

if (fork() == 0)

此時發生第一次程序分叉：

1. 父程序 ($P_0$)：fork() 返回子程序的 PID（假設為 $pid_1$，且 $pid_1 \neq 0$）。因此條件 fork() == 0 為假（False），$P_0$ 進入 else 區塊。
2. 子程序 ($P_1$)：fork() 返回 $0$。因此條件 fork() == 0 為真（True），$P_1$ 進入 if 區塊。

步驟 2：分析子程序 $P_1$ 的行為
$P_1$ 進入 if 區塊後執行：

exec("ProgramA");

exec() 函數的功能是用新的程式（此處為 "ProgramA"）替換當前程序的程式碼、資料與堆疊段。若執行成功，$P_1$ 原本的後續指令（包含 main 函數的結束）將不再執行。

• 結果：$P_1$ 轉變為執行 "ProgramA" 的程序。在親屬關係圖中，$P_1$ 仍是 $P_0$ 的子程序，但其內容已變為 ProgramA。

步驟 3：分析父程序 $P_0$ 的行為
$P_0$ 進入 else 區塊後，遇到第二個 if 判斷：

if (fork() == 0)

此時發生第二次程序分叉（僅由 $P_0$ 執行）：

1. 父程序 ($P_0$ 本身)：fork() 返回新子程序的 PID（假設為 $pid_2$，且 $pid_2 \neq 0$）。條件為假，進入內層的 else 區塊。
2. 新子程序 ($P_2$)：fork() 返回 $0$。條件為真，進入內層的 if 區塊。

步驟 4：分析新子程序 $P_2$ 的行為
$P_2$ 進入內層 if 區塊後執行：

exec("ProgramB");

同樣地，exec() 替換了 $P_2$ 的記憶體映像。