地特三等申論題
107年
[電力工程] 計算機概論
第 一 題
📖 題組：
一個正整數 n 的階乘（factorial）函數定義為 Factorial(n)= n!=1×2×3×…×n，並且定義 0!=1。（每小題 5 分，共 25 分） (一)下列是計算 Factorial(n)的一個虛擬碼（pseudocode）。如果我們呼叫Factorial(6)，那麼這個程式執行到最後"return F"這一行時，F 的值會等於多少？ Algorithm: Factorial (n) { F ← 1 i ← 1 while (i ≤ n) { F ← F × i i ← i + 1 } return F } (二)承上題，如果我們呼叫 Factorial(6)，那麼這個程式執行到最後"return F"這一行時，i 的值會等於多少？ (三)承上題，以上的方法我們將之稱為是一種"iteration solution"，請說明何謂"iteration solution"？ (四)階乘函數亦可以遞迴（recursion）方式定義：0!=1，n!= n×(n-1)!。以下是計算 Factorial(n)的一個 recursive solution 虛擬碼（pseudocode）。請說明何謂"recursive solution"？ Algorithm: Factorial (n) { if (n = 0) return 1 else return n × Factorial (n − 1) } (五)承上題，如果 n 值很大，計算 Factorial(n)的 recursive solution 的空間複雜度（space complexity）為何？
一個正整數 n 的階乘（factorial）函數定義為 Factorial(n)= n!=1×2×3×…×n，並且定義 0!=1。（每小題 5 分，共 25 分） (一)下列是計算 Factorial(n)的一個虛擬碼（pseudocode）。如果我們呼叫Factorial(6)，那麼這個程式執行到最後"return F"這一行時，F 的值會等於多少？ Algorithm: Factorial (n) { F ← 1 i ← 1 while (i ≤ n) { F ← F × i i ← i + 1 } return F } (二)承上題，如果我們呼叫 Factorial(6)，那麼這個程式執行到最後"return F"這一行時，i 的值會等於多少？ (三)承上題，以上的方法我們將之稱為是一種"iteration solution"，請說明何謂"iteration solution"？ (四)階乘函數亦可以遞迴（recursion）方式定義：0!=1，n!= n×(n-1)!。以下是計算 Factorial(n)的一個 recursive solution 虛擬碼（pseudocode）。請說明何謂"recursive solution"？ Algorithm: Factorial (n) { if (n = 0) return 1 else return n × Factorial (n − 1) } (五)承上題，如果 n 值很大，計算 Factorial(n)的 recursive solution 的空間複雜度（space complexity）為何？
📝 此題為申論題，共 5 小題
小題 (一)
下列是計算 Factorial(n)的一個虛擬碼（pseudocode）。如果我們呼叫Factorial(6)，那麼這個程式執行到最後"return F"這一行時，F 的值會等於多少？
思路引導 VIP
面對程式碼追蹤題，應先辨識演算法的核心邏輯（此處為利用 while 迴圈計算連乘積）。接著採用『手動追蹤（Trace）』技巧，逐步記錄迴圈每一回合（Iteration）變數 F 與 i 的值，直到滿足跳出迴圈的條件為止。
小題 (二)
承上題，如果我們呼叫 Factorial(6)，那麼這個程式執行到最後"return F"這一行時，i 的值會等於多少？
思路引導 VIP
追蹤演算法的執行流程，特別留意 while 迴圈（while loop）的終止條件。當迴圈條件不再成立而跳出時，計數器變數通常已經執行了最後一次遞增，因此迴圈結束時 i 的值會剛好是不符合條件的第一個數字（即 n + 1）。
小題 (三)
承上題，以上的方法我們將之稱為是一種"iteration solution"，請說明何謂"iteration solution"？
思路引導 VIP
考生應直擊「迭代（Iteration）」的核心定義，即透過迴圈結構（如 while/for）反覆執行程式碼。作答時除了闡述定義，建議與遞迴（Recursion）進行對比，並點出其不需額外函式呼叫堆疊（Call Stack）、執行效率較高等底層系統優勢，以展現邏輯層次並獲取高分。
小題 (四)
階乘函數亦可以遞迴（recursion）方式定義：0!=1，n!= n×(n-1)!。以下是計算 Factorial(n)的一個 recursive solution 虛擬碼（pseudocode）。請說明何謂"recursive solution"？
思路引導 VIP
看到遞迴（Recursion），首先聯想其兩大核心要件：『終止條件（Base case）』與『遞迴呼叫（Recursive step）』。作答時除了定義『函式呼叫自身』的表層意義外，建議從系統底層的『呼叫堆疊（Call Stack）』運作原理切入，展現對軟硬體架構的全面理解。
小題 (五)
承上題，如果 n 值很大，計算 Factorial(n)的 recursive solution 的空間複雜度（space complexity）為何？
思路引導 VIP
看到遞迴演算法的空間複雜度，應立即聯想到系統底層的「呼叫堆疊（Call Stack）」。每一次遞迴呼叫皆需推入一個新的堆疊框架（Stack Frame），因此最大遞迴深度即決定了空間複雜度的大 O 級別。