113 年 國立臺灣大學生物機電系碩士班丁組《計算機概論（A）》

核心觀念

本題考查：

1. 二補數表示法（two's complement）
2. 有號二進位整數的位元數選擇
3. 以加法完成減法
4. 溢位判斷與進位捨棄

二補數的形成方式為：

$$\text{負數二補數}=\text{正數的位元反相}+1$$

計算減法時，利用：

$$A-B=A+\text{二補數}(B)$$

題目中的運算為：

$$-150-(-75)$$

由於 $-150$ 無法用 8 位元二補數表示，因此採用 9 位元。9 位元有號二補數的表示範圍為：

$$-2^{8}\leq x\leq 2^{8}-1$$

即：

$$-256\leq x\leq255$$

因此 $-150$ 與 $-75$ 都能正確表示。

---

解題方法

將：

$$-150-(-75)$$

改寫為：

$$-150+75$$

接著以 9 位元二補數進行運算。

---

一、將 $-150$ 轉為 9 位元二補數

先將 $150$ 轉為二進位：

$$150=128+16+4+2$$

因此：

$$150_{10}=10010110_2$$

補成 9 位元：

$$150_{10}=010010110_2$$

逐位反相：

$$010010110 \longrightarrow 101101001$$

加 $1$：

$$101101001+1=101101010$$

所以：

$$-150_{10}=101101010_2$$

---

二、將 $-75$ 轉為 9 位元二補數

先將 $75$ 轉為二進位：

$$75=64+8+2+1$$

因此：

$$75_{10}=1001011_2$$

補成 9 位元：

$$75_{10}=001001011_2$$

逐位反相：

$$001001011 \longrightarrow 110110100$$

加 $1$：

$$110110100+1=110110101$$

所以：

$$-75_{10}=110110101_2$$

---

三、將減法改為加法

原式為：

$$-150-(-75)$$

減去 $-75$，等同於加上 $-75$ 的二補數。由於 $-75$ 的二補數就是 $+75$：

$$\text{二補數}(110110101)=001001011$$

因此：

此題考察確定性有限自動機 (DFA) 的設計，目標是辨識所有以 "abb" 結尾的字串。

核心觀念：
DFA 由一組狀態 (States)、輸入字母表 (Alphabet)、轉移函數 (Transition Function)、起始狀態 (Start State) 和終止狀態 (Accept States) 組成。DFA 的目標是讀取輸入字串，根據轉移函數在狀態間移動，若字串讀取完畢時，自動機停留在一個終止狀態，則該字串被接受。

設計 DFA 的關鍵在於如何定義狀態，使得每個狀態都能代表「到目前為止已讀取的字串，最長能匹配到目標結尾字串的哪個前綴」。

解題步驟：

1. 定義目標字串和字母表：

   • 目標結尾：abb
   • 字母表 $\Sigma = \{a, b\}$

2. 識別可能的字串前綴：
   我們需要設計狀態來記錄我們已經讀取了目標結尾 abb 的哪個前綴。

   • 空字串 (尚未讀取任何東西)
   • 讀取到 a
   • 讀取到 ab
   • 讀取到 abb (目標結尾)

3. 定義狀態：
   基於上述前綴，我們可以定義以下狀態：

   • $q_0$: 起始狀態。代表尚未讀取到 a，或者剛讀取的字串不構成 a 的前綴。
   • $q_1$: 代表剛讀取的字串以 a 結尾。
   • $q_2$: 代表剛讀取的字串以 ab 結尾。
   • $q_3$: 代表剛讀取的字串以 abb 結尾。這是我們的終止狀態 (Accept State)。

4. 定義轉移函數 (Transition Function)：
   對於每個狀態和每個輸入字母，確定下一個狀態。

   • 從 $q_0$ (起始狀態)：

     • 如果讀到 a：我們成功匹配了目標結尾的第一個字元 a，進入狀態 $q_1$。
       $\delta(q_0, a) = q_1$
     • 如果讀到 b：我們沒有匹配到 a，而且讀到的 b 也無法構成任何目標前綴，所以我們仍然處於「未匹配」的狀態。我們可以維持在 $q_0$（或者定義一個專門的「陷阱狀態」，但在此情況下，直接回到 $q_0$ 更簡潔）。
       $\delta(q_0, b) = q_0$

   • 從 $q_1$ (以 a 結尾)：

     • 如果讀到 a：我們現在以 aa 結尾。這依然可以視為以 a 結尾（因為 aa 的結尾是 a）。所以我們保持在 $q_1$。
       $\delta(q_1, a) = q_1$
     • 如果讀到 b：我們現在以 ab 結尾。這正好是目標結尾的第二個前綴。進入狀態 $q_2$。
       $\delta(q_1, b) = q_2$

   • 從 $q_2$ (以 ab 結尾)：

     • 如果讀到 a：我們現在以 aba 結尾。這個字串的結尾是 a，這符合 $q_1$ 的定義。我們需要回到 $q_1$。
       $\delta(q_2, a) = q_1$
     • 如果讀到 b：我們現在以 abb 結尾。這正是我們的目標結尾！進入終止狀態 $q_3$。
       $\delta(q_2, b) = q_3$

   • 從 $q_3$ (以 abb 結尾 - 終止狀態)：

     • 如果讀到 a：我們現在以 abba 結尾。這個字串的結尾是 a，這符合 $q_1$ 的定義。我們需要回到 $q_1$。
       $\delta(q_3, a) = q_1$
     • 如果讀到 b：我們現在以 abbb 結尾。這個字串的結尾是 bb。這個 bb 並不能直接構成 abb 的前綴，但 b 本身也不能構成 a 的前綴。我們需要仔細分析。
       如果讀到 abbb，它的結尾是 b。這個 b 不能構成 a 的前綴，所以我們應該回到 $q_0$。
       $\delta(q_3, b) = q_0$

5. 確定起始狀態和終止狀態：

   • 起始狀態：$q_0$
   • 終止狀態 (Accept States)：$\{q_3\}$

6. 繪製 DFA 圖：

   • 畫出四個節點，分別標記為 $q_0, q_1, q_2, q_3$。
   • 用一個箭頭指向 $q_0$ 表示它是起始狀態。
   • 用雙圓圈標記 $q_3$ 表示它是終止狀態。
   • 根據轉移函數繪製帶標籤的箭頭：
     • $q_0 \xrightarrow{a} q_1$
     • $q_0 \xrightarrow{b} q_0$
     • $q_1 \xrightarrow{a} q_1$
     • $q_1 \xrightarrow{b} q_2$
     • $q_2 \xrightarrow{a} q_1$
     • $q_2 \xrightarrow{b} q_3$
     • $q_3 \xrightarrow{a} q_1$

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的：

1. 插入規則：
   對每個新節點，若鍵值小於目前節點，往左子樹走；若鍵值大於目前節點，往右子樹走。

2. 中序走訪（inorder traversal）：
   走訪順序為：

   $\text{左子樹} \rightarrow \text{根節點} \rightarrow \text{右子樹}$

   對於使用通常大小關係的 BST，中序走訪結果必定是由小到大的排序序列。

---

解題方法

依序插入：

$7,5,1,8,3,6,0,9,4,2$

各節點的插入位置如下：

• $7$：成為根節點。
• $5<7$：插入 $7$ 的左側。
• $1<7$，且 $1<5$：插入 $5$ 的左側。
• $8>7$：插入 $7$ 的右側。
• $3<7$、$3<5$，但 $3>1$：插入 $1$ 的右側。
• $6<7$，但 $6>5$：插入 $5$ 的右側。
• $0<7$、$0<5$、$0<1$：插入 $1$ 的左側。
• $9>7$、$9>8$：插入 $8$ 的右側。
• $4<7$、$4<5$、$4>1$、$4>3$：插入 $3$ 的右側。
• $2<7$、$2<5$、$2>1$、$2<3$：插入 $3$ 的左側。

此題考察雜湊表 (Hash Table) 的建構，特別是使用雙重雜湊 (Double Hashing) 來處理碰撞 (Collision)。

核心觀念：
雜湊表是一種用於快速查找、插入和刪除鍵值對的資料結構。它使用雜湊函數將鍵映射到表格中的索引。當兩個不同的鍵映射到同一個索引時，就會發生碰撞。雙重雜湊是一種處理碰撞的方法，它使用第二個雜湊函數來計算探測序列 (Probe Sequence)，以找到下一個可用的槽位。

對於雙重雜湊，當鍵 $k$ 映射到索引 $i$ 時，若該槽位已被佔用，則下一個探測的槽位為 $(i + j \times h_2(k)) \pmod{m}$，其中 $m$ 是雜湊表的大小，$j$ 是探測的次數（從 1 開始）。

解題步驟：

1. 確定雜湊表參數：

   • 雜湊表大小 $m = 13$。
   • 第一個雜湊函數 $h_1(k) = k \pmod{13}$。
   • 第二個雜湊函數 $h_2(k) = 1 + (k \pmod{11})$。
   • 要插入的鍵：$79, 69, 98, 72, 14, 50$。

2. 初始化雜湊表：
   雜湊表有 13 個槽位，初始時都是空的。我們用 null 或 - 表示空槽位。
   Table: [-, -, -, -, -, -, -, -, -, -, -, -, -] (索引 0 到 12)

3. 逐一插入鍵值：

   • 插入 79：

     • $h_1(79) = 79 \pmod{13}$
       $79 = 6 \times 13 + 1$
       $h_1(79) = 1$
     • 槽位 1 是空的。
     • Table: [-, 79, -, -, -, -, -, -, -, -, -, -, -]

   • 插入 69：

     • $h_1(69) = 69 \pmod{13}$
       $69 = 5 \times 13 + 4$
       $h_1(69) = 4$
     • 槽位 4 是空的。
     • Table: [-, 79, -, -, 69, -, -, -, -, -, -, -, -]

   • 插入 98：

     • $h_1(98) = 98 \pmod{13}$
       $98 = 7 \times 13 + 7$
       $h_1(98) = 7$
     • 槽位 7 是空的。
     • Table: [-, 79, -, -, 69, -, -, 98, -, -, -, -, -]

   • 插入 72：

     • $h_1(72) = 72 \pmod{13}$
       $72 = 5 \times 13 + 7$
       $h_1(72) = 7$
     • 槽位 7 已被 98 佔用。發生碰撞！
     • 使用雙重雜湊處理：
       • 計算 $h_2(72) = 1 + (72 \pmod{11})$
         $72 = 6 \times 11 + 6$
         $h_2(72) = 1 + 6 = 7$
       • 第一次探測 ($j=1$): 新索引 = $(h_1(72) + 1 \times h_2(72)) \pmod{13}$
         新索引 = $(7 + 1 \times 7) \pmod{13} = 14 \pmod{13} = 1$
       • 槽位 1 已被 79 佔用。再次碰撞！
       • 第二次探測 ($j=2$): 新索引 = $(h_1(72) + 2 \times h_2(72)) \pmod{13}$
         新索引 = $(7 + 2 \times 7) \pmod{13} = (7 + 14) \pmod{13} = 21 \pmod{13} = 8$
       • 槽位 8 是空的。插入 72。
     • Table: [-, 79, -, -, 69, -, -, 98, 72, -, -, -, -]

   • 插入 14：

     • $h_1(14) = 14 \pmod{13} = 1$
     • 槽位 1 已被 79 佔用。發生碰撞！
     • 使用雙重雜湊處理：
       • 計算 $h_2(14) = 1 + (14 \pmod{11})$
         $14 = 1 \times 11 + 3$
         $h_2(14) = 1 + 3 = 4$
       • 第一次探測 ($j=1$): 新索引 = $(h_1(14) + 1 \times h_2(14)) \pmod{13}$
         新索引 = $(1 + 1 \times 4) \pmod{13} = 5 \pmod{13} = 5$
       • 槽位 5 是空的。插入 14。
     • Table: [-, 79, -, -, 69, 14, -, 98, 72, -, -, -, -]

   • 插入 50：

     • $h_1(50) = 50 \pmod{13}$
       $50 = 3 \times 13 + 11$
       $h_1(50) = 11$
     • 槽位 11 是空的。
     • Table: [-, 79, -, -, 69, 14, -, 98, 72, -, -, 50, -]

4. 最終雜湊表結構：
   所有鍵都已插入。

   Table: [-, 79, -, -, 69, 14, -, 98, 72, -, -, 50, -]

此題考察圖論 (Graph Theory) 的基本概念，包括圖的表示、頂點集合、邊集合以及鄰接矩陣。

核心觀念：

• 圖 (Graph): 由頂點 (Vertices) 和連接頂點的邊 (Edges) 組成。
• 無向圖 (Undirected Graph): 邊沒有方向。如果 A 和 B 之間有一條邊，則表示 A 和 B 之間有關係，這個關係對 A 和 B 來說是相同的。
• 鄰接矩陣 (Adjacency Matrix): 一種表示圖的方法，用一個方陣來表示頂點之間的連接關係。對於有 $n$ 個頂點的圖，鄰接矩陣是一個 $n \times n$ 的矩陣 $A$，其中 $A_{ij} = 1$ 如果頂點 $i$ 和頂點 $j$ 之間有邊，否則 $A_{ij} = 0$。對於無向圖，鄰接矩陣是對稱的。

解題步驟：

a) 繪製圖 G：

1. 確定頂點： 根據題目，有 5 個人：A, B, C, D, E。這些將是圖的頂點。

2. 確定邊： 根據題目給出的「認識」關係，繪製邊。認識關係是雙向的，所以是無向圖。

   • A 和 C 認識 $\rightarrow$ 在 A 和 C 之間畫一條線。
   • A 和 D 認識 $\rightarrow$ 在 A 和 D 之間畫一條線。
   • B 和 C 認識 $\rightarrow$ 在 B 和 C 之間畫一條線。
   • C 和 D 認識 $\rightarrow$ 在 C 和 D 之間畫一條線。
   • C 和 E 認識 $\rightarrow$ 在 C 和 E 之間畫一條線。

   圖 G 的繪製：
   頂點：A, B, C, D, E
   邊：(A, C), (A, D), (B, C), (C, D), (C, E)

       A --- C --- E
       | \ / |
       |  D  |
       | /
       B
   

   一個更清晰的繪製方式：

   graph TD
       A --- C
       A --- D
       B --- C
       C --- D
       C --- E
       A
       B
       C
       D
       E
   

   (請注意，上述 Mermaid 圖僅為示意，實際繪製時，請確保所有節點和邊都正確連接)

   文字描述的圖：
   頂點：A, B, C, D, E
   邊：

   • A 連接到 C 和 D。
   • B 連接到 C。
   • C 連接到 A, B, D, E。
   • D 連接到 A 和 C。
   • E 連接到 C。

b) 列出頂點集合 V 和邊集合 E：

1. 頂點集合 V： 包含圖中的所有頂點。
   $V = \{A, B, C, D, E\}$

2. 邊集合 E： 包含圖中的所有邊。邊的表示方式是頂點對，由於是無向圖，順序不重要，我們通常會按字母順序排列，或者使用集合表示 $\{u, v\}$。

   • A 和 C 認識 $\rightarrow \{A, C\}$

核心觀念

圖中有一個反相器與兩個 NOR 閘，每個元件的傳播延遲皆為 $\Delta$。以下依電路位置假設：A 是下方 NOR 閘的輸出，B 是右側 NOR 閘的輸出。原圖未標出 A、B，若題目另有標示，需依實際測點對應。

下方 NOR 閘接收 $\overline C$ 與 $B$；右側 NOR 閘接收 $C$ 與 $A$。因此穩定時的邏輯關係為：

$$A=\overline{\overline C+B},\qquad B=\overline{C+A}$$

兩個 NOR 閘互相回授，輸出切換時間須逐級計入傳播延遲。

解題方法

設輸入方波週期為 $T$，半週期為 $H=T/2$，並假設 $H>2\Delta$，使輸出有時間完成切換。

以 $C$ 上升緣發生於 $t=0$ 為例：

• **$C$ 上升：**右側 NOR 閘收到 $C=1$，經 $\Delta$ 後使 $B$ 下降；接著下方 NOR 閘在 $\overline C=0$ 且 $B=0$ 時輸出 $A=1$，再經 $\Delta$ 後使 $A$ 上升。因此 $B$ 於 $t=\Delta$ 下降，$A$ 於 $t=2\Delta$ 上升。

核心觀念

本題考查 Huffman coding（霍夫曼編碼），是一種根據字元出現頻率建立的最佳前綴碼。

主要原則如下：

• 頻率越高的字元，通常配置越短的編碼。
• 頻率越低的字元，通常配置越長的編碼。
• Huffman tree 的每個內部節點，其權重等於兩個子樹權重之和。
• 從根節點到葉節點的路徑決定字元編碼，約定左分支為 $0$、右分支為 $1$。
• Huffman code 具備 prefix-free property（前綴碼性質），任一字元的編碼不會是另一字元編碼的前綴，因此能夠唯一解碼。

---

解題方法

將所有字元依頻率由小到大排列：

$$d:4,\quad a:5,\quad e:7,\quad c:9,\quad b:12$$

每次取出頻率最小的兩個節點合併，產生新的內部節點，再將新節點放回排序集合中。

第一步：合併 $d$ 與 $a$

$$4+5=9$$

產生節點 $(da):9$。

目前節點為：

$$e:7,\quad c:9,\quad (da):9,\quad b:12$$

第二步：合併 $e$ 與 $c$

$$7+9=16$$

產生節點 $(ec):16$。

目前節點為：

$$(da):9,\quad b:12,\quad (ec):16$$

第三步：合併 $(da)$ 與 $b$

$$9+12=21$$

產生節點 $((da)b):21$。

第四步：合併兩個子樹

$$16+21=37$$

根節點權重為 $37$。

---

a) Huffman tree

約定左分支為 $0$、右分支為 $1%，可建立下列 Huffman tree：

                 (37)
                /    \
             0 /      \ 1
              /        \
           (16)        (21)
          /    \       /    \
       0 /      \ 1  0 /      \ 1
        e:7      c:9 (da):9   b:12
                    /    \
                 0 /      \ 1
                  d:4      a:5

其中：

• 根節點：$37$
• 左子樹：$7+9=16$
• 右子樹：$9+12=21$
• 整體：$16+21=37

核心觀念

本題考查：

1. 暫存器內容的保存與覆寫。
2. 立即值（immediate value）的載入。
3. 算術運算的運算元與結果存放位置。
4. 程式計數器 PC 的順序執行與跳躍。
5. 將

$$(A+5)\times(B-3)$$

分成兩個因子後再相乘。

假設原始輸入分別存放於暫存器 $A$ 與 $B$，最後結果必須存放於暫存器 $C$。

解題方法

先計算兩個因子：

$$A_1=A+5$$ $$B_1=B-3$$

再計算：

$$C=A_1\times B_1$$

若要完成此運算，指令集至少必須具備：

• 對 $A$ 加上立即值 $5$ 的能力；
• 對 $B$ 減去立即值 $3$ 的能力；
• 將 $B$ 複製到 $C$；
• 令 $C$ 乘以 $A$。

例如，若補充下列常見指令：

• ADD A, #5：$A\leftarrow A+5$
• SUB B, #3：$B\leftarrow B-3$
• MOV C, B：$C\leftarrow B$
• MUL C, A：$C\leftarrow C\times A$

則程式如下：

; 原始 A、B 分別為輸入值
ADD A, #5      ; A = A + 5
SUB B, #3      ; B = B - 3
MOV C, B       ; C = B - 3
MUL C, A       ; C = (B - 3) × (A + 5)
HLT            ; 停止

交換乘法因子的順序後，可得：

$$C=(B-3)(A+5)=(A+5)(B-3)$$

因此，程式結束時，$C$ 即為所求結果。

題面指令集的問題

依照題目列出的「支援指令」，無法嚴格寫出能計算任意 $A$、$B$ 輸入值的合法程式，原因如下。

1. MOV A, #5 會覆寫原本的 A

題目唯一提供的立即值載入指令是：

MOV A, #5

執行後：

$$A\leftarrow 5$$

原本的 $A$ 值會遺失，因此無法再計算原式中的 $A+5$。

2. 沒有載入常數 3 的指令

題目沒有提供：

MOV B, #3

核心觀念

本題考查整數陣列的循序走訪與迴圈操作：

1. 尋找最大值及其索引

   • 逐一比較陣列元素。
   • 使用變數 maxValue 儲存目前最大值。
   • 使用變數 maxIndex 儲存最大值所在位置。
   • 若出現相同最大值，以下程式保留第一次出現的位置。
   • 索引採用常見的 0-based index，第一個元素索引為 $0$。

2. 反向輸出陣列

   • 陣列最後一個元素索引為 $n-1$。
   • 使用迴圈令索引由 $n-1$ 遞減至 $0$。

陣列走訪的基本時間複雜度為 $O(n)$，最多只需要額外使用固定數量的變數，因此空間複雜度為 $O(1)$。

解題方法

a) 找出最大元素及其索引

初始化：

$$\text{maxValue} = A[0]$$ $$\text{maxIndex} = 0$$

接著從索引 $1$ 開始逐一檢查：

$$\text{若 } A[i] > \text{maxValue}$$

便更新：

$$\text{maxValue} = A[i]$$ $$\text{maxIndex} = i$$

使用嚴格大於 >，可確保遇到相同最大值時保留第一次出現的位置。

b) 反向輸出

陣列共有 $n$ 個元素，合法索引範圍為：

$$0, 1, 2, \ldots, n-1$$

因此反向輸出時，迴圈從 $n-1$ 開始，每次遞減 $1$，直到索引 $0$。

參考程式碼（C++）

此題考察程式設計能力，要求開發一個程式來計算並顯示給定正整數的質因數分解 (Prime Factorization)。

核心觀念：

• 質因數分解 (Prime Factorization): 將一個合數 (composite number) 表示為一系列質數 (prime numbers) 的乘積。例如，$84 = 2 \times 2 \times 3 \times 7$。
• 質數 (Prime Number): 大於 1 的自然數，除了 1 和它本身以外不再有其他因數。
• 演算法：
  1. 從最小的質數 2 開始嘗試。
  2. 如果當前數字 n 能被當前質數 p 整除，則將 p 加入質因數列表，並將 n 更新為 n / p。重複此步驟，直到 n 不能再被 p 整除。
  3. 嘗試下一個質數。
  4. 如果嘗試到 p，且 $p \times p > n$，則表示剩餘的 n 本身也是一個質數（如果 $n>1$）。
• 程式結構：
  • 需要一個主函數或入口點。
  • 需要獲取使用者輸入。
  • 需要一個核心函數來執行質因數分解。
  • 需要將結果格式化並輸出。
  • 建議使用迴圈和函數。

解題步驟：

1. 選擇程式語言：
   選擇 Python，因為其語法簡潔，適合快速實現。

2. 設計質因數分解函數 prime_factorization(num)：

   • 該函數接收一個正整數 num 作為輸入。
   • 初始化一個空列表 factors 來儲存質因數。
   • 處理因數 2：
     • 使用 while num % 2 == 0: 迴圈，只要 num 能被 2 整除，就將 2 加入 factors，並更新 num = num // 2。
   • 處理奇數因數：
     • 從 3 開始，嘗試奇數作為可能的因數。
     • 使用 for i in range(3, int(num**0.5) + 1, 2): 迴圈。這裡的上限是 num 的平方根，因為如果 num 有一個大於其平方根的因數，那麼它必定也有一個小於其平方根的因數。步長為 2，因為我們已經處理了 2，之後只需要檢查奇數。
     • 在迴圈內部，使用 while num % i == 0: 迴圈，只要 num 能被 i 整除，就將 i 加入 factors，並更新 num = num // i。
   • 處理最後的質因數：
     • 如果在上述迴圈結束後，num 仍然大於 1，則說明剩餘的 num 本身是一個質數（且大於其原始平方根）。將這個剩餘的 num 加入 factors。
   • 返回 factors 列表。

3. 編寫主程式邏輯：

   • 提示使用者輸入一個正整數。
   • 使用 input() 獲取使用者輸入，並轉換為整數。
   • 進行輸入驗證：確保輸入的是正整數。如果輸入無效，提示使用者重新輸入。
   • 調用 prime_factorization() 函數獲取質因數列表。
   • 格式化輸出結果，將質因數用 * 連接起來。

4. 編寫 Python 程式碼：

import math

def prime_factorization(num):
    """
    Calculates the prime factorization of a given positive integer.

    Args:
        num: A positive integer.

    Returns:
        A list of prime factors.
    """
    factors = [] # Initialize an empty list to store prime factors

    # Handle factor 2
    # Keep dividing num by 2 as long as it's even
    while num % 2 == 0:
        factors.append(2)
        num //= 2 # Use integer division

    # Handle odd factors starting from 3
    # We only need to check up to the square root of the remaining number
    # We increment by 2 because we only need to check odd numbers
    # The loop range goes up to int(sqrt(num)) + 1 to ensure the square root itself is checked if it's an integer
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        # While i divides num, add i to factors and divide num by i
        while num % i == 0:
            factors.append(i)
            num //= i

    # If after all divisions, num is still greater than 1,
    # it means the remaining num is a prime factor itself.
    if num > 1:
        factors.append(num)

    return factors

def main():
    """
    Main function to prompt user for input, perform prime factorization,
    and display the result.
    """
    while True:
        try:
            # Prompt the user to enter a positive integer
            user_input = input("Enter a positive integer: ")
            number = int(user_input)

            # Validate the input: must be a positive integer
            if number <= 0:
                print("Invalid input. Please enter a positive integer greater than 0.")
            elif number == 1:
                print("Prime Factorization of 1: 1") # Special case for 1
                break
            else:
                # Get the list of prime factors
                prime_factors = prime_factorization(number)

                # Format the output string
                # Use ' * '.join() to connect the factors with '*'
                # Convert each factor to string before joining
                output_string = " * ".join(map(str, prime_factors))

                # Display the result
                print(f"Prime Factorization of {number}: {output_string}")
                break # Exit the loop after successful execution

        except ValueError:
            # Handle cases where the input is not a valid integer
            print("Invalid input. Please enter a valid integer.")
        except Exception as e:
            # Catch any other unexpected errors
            print(f"An error occurred: {e}")

# Execute the main function when the script is run
if __name__ == "__main__":
    main()

5. 解釋程式碼邏輯 (Comments)：
   程式碼中已包含詳細的英文註解。

   中文解釋：

   • prime_factorization(num) 函數：
     • 接收一個正整數 num。
     • 初始化一個空列表 factors。
     • 首先，檢查 num 是否能被 2 整除。如果可以，將 2 加入 factors，並用 num //= 2 更新 num。重複此步驟直到 num 變成奇數。
     • 然後，從 3 開始，以步長為 2（即只檢查奇數）遍歷到 num 的平方根。對於每個奇數 i，檢查它是否能整除當前的 num。如果能，將 i 加入 factors，並用 num //= i 更新 num。重複此步驟直到 num 不能再被 i 整除。
     • 最後，如果經過上述處理後 num 仍然大於 1，說明剩餘的 num 本身就是一個質因數（例如，原始數字是 7，或者經過分解後剩下 13）。將這個 num 加入 factors。
     • 返回包含所有質因數的列表 factors。
   • main() 函數：
     • 使用一個 while True 迴圈來不斷提示使用者輸入，直到輸入有效。
     • try-except 區塊用於處理可能的錯誤，如使用者輸入非數字。
     • input() 獲取字串輸入，int() 轉換為整數。
     • 檢查輸入是否為正整數 (number > 0)。
     • 單獨處理數字 1 的情況，其質因數分解是 1。
     • 如果輸入有效且大於 1，調用 prime_factorization() 獲取因數列表。