113 年 國立成功大學工程科學系碩士班丙組《計算機概論》

核心觀念

本題考查：

1. 遞迴程序的執行順序。
2. Stack（堆疊）如何模擬函式呼叫與返回。
3. Hanoi Tower 的遞迴關係。

原遞迴程序：

• 先將 $N-1$ 個盤子由 $A$ 移至 $C$。
• 將第 $N$ 個盤子由 $A$ 移至 $B$。
• 再將 $N-1$ 個盤子由 $C$ 移至 $B$。

其移動次數滿足：

$$T(N)=2T(N-1)+1$$

且 $T(0)=0$，因此：

$$T(N)=2^N-1$$

解題方法：以明確 Stack 模擬遞迴

每次遞迴呼叫都建立一個 stack frame，記錄：

• $N$：目前要移動的盤子數
• $A$：起點
• $B$：終點
• $C$：暫存柱
• stage：目前執行到哪個階段

一個 Hanoi Tower 呼叫可分成三個階段：

stage	工作
0	執行 Hanoi(N-1,A,C,B)
1	移動第 $N$ 個盤子，再執行第二個遞迴呼叫
2	第二個遞迴呼叫完成，返回上一層

遞迴呼叫會先處理後加入的工作，因此使用 Stack 的 push 與 pop 即可保留正確順序。

非遞迴版本

核心觀念

二維陣列的位址計算，必須先知道：

• 儲存方式：row-major（列優先）或 column-major（行優先）
• 每個元素所占的位址單位
• 主要維度的大小

本題由 $A(1,1)$ 與 $A(3,3)$ 的位址差，反推出陣列每列（或每行）包含 $15$ 個元素。以下採用一般考題的假設：陣列連續儲存，且每個元素占一個位址單位。

解題方法

以 row-major 為例，若每列有 $N$ 個元素，則：

$$\operatorname{Addr}(A(i,j)) = \operatorname{Addr}(A(1,1)) + \bigl((i-1)N+(j-1)\bigr)$$

由題目可得：

$$\operatorname{Addr}(A(3,3))-\operatorname{Addr}(A(1,1)) = 676-644=32$$

從 $A(1,1)$ 移動到 $A(3,3)$，共跨越：

• 前進兩列：$2N$ 個元素
• 每列再向右前進兩格：$2$ 個元素

因此：

$$2N+2=32$$

這題考查神經網路的前向傳播 (Forward Propagation) 計算。需要根據給定的網路結構、權重、輸入值以及激活函數，逐步計算每一層的輸出。

核心觀念：
神經網路的前向傳播是將輸入數據通過網路的各層，根據權重和激活函數計算輸出。
計算步驟通常是：

1. 計算加權總和（或稱輸入）：$z = \sum w_i x_i + b$ (其中 $b$ 是偏置項，此題沒有給出偏置項，假設為 0)。
2. 將加權總和通過激活函數：$a = \sigma(z)$。

解題步驟：

首先，觀察網路結構圖：

• 輸入層有 $X_1, X_2$。
• 第一層隱藏層有節點 $a_1, a_2$。
• 第二層隱藏層有節點 $a_3, a_4$。
• 輸出層為 $Y$。

根據圖示，我們可以推導出各節點的計算公式：

輸入層：
$X_1 = 1$
$X_2 = 1$

第一層隱藏層：

• 節點 $a_1$：接收來自 $X_1$ 的輸入，權重為 $W_1$；接收來自 $X_2$ 的輸入，權重為 $W_2$。
  $z_{a1} = X_1 \cdot W_1 + X_2 \cdot W_2$
  $a_1 = \sigma(z_{a1})$
• 節點 $a_2$：接收來自 $X_1$ 的輸入，權重為 $W_3$；接收來自 $X_2$ 的輸入，權重為 $W_4$。
  $z_{a2} = X_1 \cdot W_3 + X_2 \cdot W_4$
  $a_2 = \sigma(z_{a2})$

第二層隱藏層：

• 節點 $a_3$：接收來自 $a_1$ 的輸入，權重為 $W_5$；接收來自 $a_2$ 的輸入，權重為 $W_6$。
  $z_{a3} = a_1 \cdot W_5 + a_2 \cdot W_6$
  $a_3 = \sigma(z_{a3})$
• 節點 $a_4$：接收來自 $a_1$ 的輸入，權重為 $W_7$；接收來自 $a_2$ 的輸入，權重為 $W_8$。
  $z_{a4} = a_1 \cdot W_7 + a_2 \cdot W_8$
  $a_4 = \sigma(z_{a4})$

輸出層：

• 節點 $Y$：接收來自 $a_3$ 的輸入，權重為 $W_9$；接收來自 $a_4$ 的輸入，權重為 $W_{10}$。
  $z_Y = a_3 \cdot W_9 + a_4 \cdot W_{10}$
  $Y = \sigma(z_Y)$

權重值：
$(W_1, W_2, W_3, W_4, W_5, W_6, W_7, W_8, W_9, W_{10}) = (-1, -2, -4, -5, 5, -4, -5, 6, 3, -5)$

計算過程：

1. 計算第一層隱藏層的輸出 ($a_1, a_2$)：

• $z_{a1} = X_1 \cdot W_1 + X_2 \cdot W_2 = (1) \cdot (-1) + (1) \cdot (-2) = -1 - 2 = -3$
  $a_1 = \sigma(-3) = \frac{1}{1 + e^{-(-3)}} = \frac{1}{1 + e^3}$
  $e^3 \approx 20.0855$
  $a_1 \approx \frac{1}{1 + 20.0855} = \frac{1}{21.0855} \approx 0.0474$

• $z_{a2} = X_1 \cdot W_3 + X_2 \cdot W_4 = (1) \cdot (-4) + (1) \cdot (-5) = -4 - 5 = -9$
  $a_2 = \sigma(-9) = \frac{1}{1 + e^{-(-9)}} = \frac{1}{1 + e^9}$
  $e^9 \approx 8103.08$
  $a_2 \approx \frac{1}{1 + 8103.08} = \frac{1}{8104.08} \approx 0.000123$

2. 計算第二層隱藏層的輸出 ($a_3, a_4$)：

• $z_{a3} = a_1 \cdot W_5 + a_2 \cdot W_6 \approx (0.0474) \cdot (5) + (0.000123) \cdot (-4)$
  $z_{a3} \approx 0.237 - 0.000492 \approx 0.2365$
  $a_3 = \sigma(z_{a3}) \approx \sigma(0.2365) = \frac{1}{1 + e^{-0.2365}}$
  $e^{-0.2365} \approx 0.7901$
  $a_3 \approx \frac{1}{1 + 0.7901} = \frac{1}{1.7901} \approx 0.5586$

• $z_{a4} = a_1 \cdot W_7 + a_2 \cdot W_8 \approx (0.0474) \cdot (-5) + (0.000123) \cdot (6)$
  $z_{a4} \approx -0.237 + 0.000738 \approx -0.2363$
  $a_4 = \sigma(z_{a4}) \approx \sigma(-0.2363) = \frac{1}{1 + e^{-(-0.2363)}} = \frac{1}{1 + e^{0.2363}}$
  $e^{0.2363} \approx 1.2665$
  $a_4 \approx \frac{1}{1 + 1.2665} = \frac{1}{2.2665} \approx 0.4413$

3. 計算輸出層的輸出 ($Y$)：

• $z_Y = a_3 \cdot W_9 + a_4 \cdot W_{10} \approx (0.5586) \cdot (3) + (0.4413) \cdot (-5)$
  $z_Y \approx 1.6758 - 2.2065 \approx -0.5307$
  $Y = \sigma(z_Y) \approx \sigma(-0.5307) = \frac{1}{1 + e^{-(-0.5307)}} = \frac{1}{1 + e^{0.5307}}$
  $e^{0.5307} \approx 1.6998$
  $Y \approx \frac{1}{1 + 1.6998} = \frac{1}{2.6998} \approx 0.3704$

精確計算（避免中間四捨五入）：
使用 $a_1 = \frac{1}{1+e^3}$ 和 $a_2 = \frac{1}{1+e^9}$。

• 第一層：
  $z_{a1} = -3$
  $a_1 = \frac{1}{1+e^3}$
  $z_{a2} = -9$
  $a_2 = \frac{1}{1+e^9}$

• 第二層：
  $z_{a3} = a_1 W_5 + a_2 W_6 = \frac{1}{1+e^3} \cdot 5 + \frac{1}{1+e^9} \cdot (-4)$

核心觀念

本題考查兩種參數傳遞方式：

1. Call by value（傳值呼叫）：先計算實際參數的值，再將該值複製給形式參數。
2. Call by address（傳址呼叫）：將實際參數所對應的記憶體位址傳給形式參數，使形式參數與實際參數指向同一個儲存位置。

題目開頭寫「three modes」，但實際只列出上述兩種模式，以下依題目列出的兩種模式作答。

---

一、兩種參數傳遞方式

1. Call by value

procedure increase(x)
{
    x := x + 1;
}

a := 5;
increase(a);

執行時，形式參數 x 取得 a 的複本：

$$x=5$$

函式內執行：

$$x:=x+1=6$$

但 x 只是區域複本，因此函式結束後：

$$a=5$$

所以，函式內修改形式參數，不會影響呼叫端的實際參數。

---

2. Call by address

procedure increase(x)
{
    x := x + 1;
}

a := 5;
increase(a);

傳址呼叫會將 a 的位址傳給 x，因此 x 與 a 指向同一個儲存位置。

函式內執行：

$$x:=x+1$$

等同於直接修改 a：

$$a=5+1=6$$

所以，函式內修改形式參數，會同步修改呼叫端的實際參數。

---

二、本題的關鍵判斷

在 Main 中，先執行：

test[1] := 5;
test[2] := 6;
element := 7;

因此呼叫函式前的狀態為：

變數	值
test[1]	5
test[2]	6
element	7

接著呼叫：

call_by_Mode(test[element]);

將 element=7 代入索引：

$$test[element]=test[7]$$

然而，test 宣告為大小為 2 的整數陣列，只存在：

$$test[1],\ test[2]$$

test[7] 超出陣列合法範圍，因此實際參數在函式呼叫前便已經是非法存取。

---

三、Call by value 的結果

傳值呼叫必須先計算實際參數的值：

$$test[element]=test[7]$$

由於 test[7] 不存在，計算實際參數時即發生陣列索引越界。

因此：

這題考查將指令轉換為機器語言的編碼過程，需要根據提供的「語言描述表」來找出對應的 Op-code 和 Operand，並組合出正確的機器指令格式。

核心觀念：
機器語言指令通常由 Op-code (操作碼) 和 Operand (操作數) 組成。Op-code 決定了執行的操作，Operand 則指定了操作的對象（例如寄存器、記憶體位址、立即數）。「語言描述表」提供了 Op-code 和其對應的操作類型。

解題步驟：
我們需要逐一分析每個指令，並從語言描述表中找到對應的條目。

語言描述表中的相關條目：

• Op-code A (ROX ROTATE): the bit pattern in register R one bit to the right X times. Each time place the bit that started at the low-order end at the high-order end. Example: A403 would cause the contents of register 4 to be rotated 3 bits to the right in a circular fashion.

  • 格式：A (Op-code) + R (寄存器號) + X (旋轉次數)
  • 例子：A403 表示 R=4, X=3。

• Op-code B (BRXY JUMP): to the instruction located in the memory cell at address XY if the bit pattern in register R is equal to the bit pattern in register number 0. Otherwise, continue with the normal sequence of execution. (The jump is implemented by copying XY into the program counter during the execute phase.) Example: B43C would first compare the contents of register 4 with the contents of register 0. If the two were equal, the pattern 3C would be placed in the program counter so that the next instruction executed would be the one located at that memory address. Otherwise, nothing would be done and program execution would continue in its normal sequence.

  • 格式：B (Op-code) + R (比較寄存器號) + XY (目標位址)
  • 例子：B43C 表示 R=4, XY=3C。

• Op-code 6 (RST ADD): the bit patterns in registers S and T as though they represented values in floating-point notation and leave the floating-point result in register R. Example: 634E would cause the values in registers 4 and E to be added as floating-point values and the result to be placed in register 3.

核心觀念

本題要求將 16 位元機器指令轉換成組合語言指令。依 MARIE 指令集的格式：

$$\text{指令}=\text{4 位元操作碼}+\text{12 位元運算元}$$

每個十六進位數字代表 4 個位元，因此四位十六進位數中：

• 第一位：操作碼（opcode）
• 後三位：運算元，通常代表記憶體位址或條件碼

本題未附上「language description table」，以下依 MARIE 常見指令集解碼：

操作碼	指令
$2$	Store
$4$	Subt
$8$	Skipcond
$B$	AddI

其中 Skipcond 的條件碼為：

• 000：若累加器 $AC<0$，跳過下一個指令
• 400：若 $AC=0$，跳過下一個指令
• 800：若 $AC>0$，跳過下一個指令

解題方法

先取每組指令的第一個十六進位數字判斷操作碼，再將後三個十六進位數字解讀為運算元。

---

A. 4034

第一個十六進位數字為 $4$，對應 Subt。

後三位為 034，代表記憶體位址 $034$。

因此：

$$\boxed{\texttt{Subt 034}}$$

其意義為：

$$AC \leftarrow AC-\text{M}[034]$$

也就是從累加器中減去記憶體位址 034 內的內容。

---

B. 8023

第一個十六進位數字為 $8$，對應 Skipcond。

後三位為 023。Skipcond 實際判斷的是運算元最前面的條件欄位；023 的高位條件碼為 000，因此代表：

$$\boxed{\texttt{Skipcond 000}}$$

其意義為：若 $AC<0$，跳過下一個指令。

023 中低位的數字不影響條件判斷，因此此指令的有效條件是「累加器小於零」。

---

核心觀念

本題考查簡化機器的：

• 程式計數器（Program Counter, PC）與指令擷取
• 立即定址（immediate addressing）
• 暫存器加法
• 記憶體直接定址（direct addressing）
• 8 位元資料的十六進位運算

每條指令占用連續兩個記憶體位址。PC 會指向目前指令的第一個位元組，執行後通常增加 $2$。

依語言描述表：

• 2RXX：將立即值 XX 載入暫存器 $R$
• 53XY：將暫存器 $X$ 與暫存器 $Y$ 相加，結果存入暫存器 $3$
• 3RXX：將暫存器 $R$ 的內容存入記憶體位址 XX
• C000：停止執行

---

解題方法

由於 PC 初值為 00，依序讀取每兩個位元組：

PC	指令	動作
00	25 03	$R_5 \leftarrow 03$
02	20 F9	$R_0 \leftarrow F9$
04	53 05	$R_3 \leftarrow R_0+R_5$
06	33 00	$M[00]\leftarrow R_3$
08	C0 00	停止

逐步計算如下。

第一步：執行 25 03

指令 25 03 表示將立即值 03 載入暫存器 $5$：

$$R_5 \leftarrow 03$$

因此：

$$R_5=03$$

第二步：執行 20 F9

指令 20 F9 表示將立即值 F9 載入暫存器 $0$：

$$R_0 \leftarrow F9$$

因此：

$$R_0=F9$$