下列遞迴函數，當執行 FR(51)後，回傳值為何？
int FR(int N){
if(N <= 1)return 1;
else return N * FR(N/3);
}
int FR(int N){
if(N <= 1)return 1;
else return N * FR(N/3);
}
-
A. 337512% (3) -
B. 400020% (5)
-
C. 433556% (14)
-
D. 50004% (1)
-
未填寫8% (2)
解說:
函數的定義是：
int FR(int N){
if(N <= 1)return 1;
else return N * FR(N/3);
}
if(N <= 1)return 1;
else return N * FR(N/3);
}
(1)當 N 小於或等於 1 時，函數會返回 1。
(2)否則，函數會返回 N 乘以 FR(N / 3)。
我們需要計算 FR(51)。
計算過程
(1)計算 FR(51):
FR(51) = 51 * FR(51 / 3)
(2)計算 51 / 3 取整數結果為 17:
FR(51) = 51 * FR(17)
(3)計算 FR(17):
FR(17) = 17 * FR(17 / 3)
(4)計算 17 / 3 取整數結果為 5:
FR(17) = 17 * FR(5)
(5)計算 FR(5):
FR(5) = 5 * FR(5 / 3)
(6)計算 5 / 3 取整數結果為 1:
FR(5) = 5 * FR(1)
(7)計算 FR(1):
FR(1) = 1
(8)把 FR(1) 的值代入 FR(5):
FR(5) = 5 * 1 = 5
(9)把 FR(5) 的值代入 FR(17):
FR(17) = 17 * 5 = 85
(10)把 FR(17) 的值代入 FR(51):
FR(51) = 51 * 85 = 4335
所以，當 N = 51 時，FR(51) 的回傳值為 4335。
答對率 : 56 %
下列程式片段的時間複雜度為何？
for(i=n; i>0; i/=2)x++;
-
A. O(NlogN)12% (3)
-
B. O(N)48% (12)
-
C. O(logN)32% (8)
-
D. O(1)0% (0)
-
未填寫8% (2)
解說:
我們來分析這段程式碼的時間複雜度：
for(i = n; i > 0; i /= 2) x++;
(1)初始化階段： i 由 n 開始。
(2)條件判斷： 循環條件是 i > 0，即當 i 大於 0 時，循環繼續進行。
(3)重複步驟： 每次迴圈結束時，i 被除以 2 (i /= 2)，這意味著 i 在每次重複的過程中都變成原來的一半。
循環次數計算
要確定循環的次數，我們可以觀察 i 的變化過程：
初始值是 n。
循環每次 i 都除以 2，變為 n/2, n/4, n/8, 依此類推。
這樣，i 的值隨著反覆動作變成 n, n/2, n/4, ..., 1 直到 i 小於等於 0。每次循環，i 減少到原來的一半，因此循環的次數與 i 的初始值 n 的對數（以 2 為底）相關。
總結
循環的次數大約等於 log₂(n)。因此，這段程式碼的時間複雜度為 O(log N)。
答對率 : 32 %
程式設計師為解決問題，會先一步一步以一些類似程序語言的虛擬碼(pseudo code)敘述描述解決問題的步驟，稱為：
-
A. 程式步驟8% (2)
-
B. 演算法56% (14)
-
C. 流程圖24% (6)
-
D. 結構圖4% (1)
-
未填寫8% (2)
解說:
選項解釋：
(A) 程式步驟：這不是一個正式的術語，雖然它可以描述過程，但不如「演算法」來得精確。
(A) 程式步驟：這不是一個正式的術語，雖然它可以描述過程，但不如「演算法」來得精確。
(B) 演算法：演算法是解決特定問題的一系列步驟或規則的集合，通常以類似程式語言的虛擬碼描述。它是計算機科學中的一個核心概念，用於設計和描述問題解決的方法。
(C) 流程圖：流程圖是一種圖形化工具，用來表示演算法的步驟和邏輯關係，但不是以虛擬碼的形式表達。
(D) 結構圖：結構圖通常用來描述程式的結構或模組化設計，不是用來描述解決問題的步驟。
答對率 : 56 %
有關遞迴程式的敘述何者錯誤？
-
A. 遞迴程式必需要有以值傳遞之機制68% (17)
-
B. 遞迴程式必需要有結束條件4% (1)
-
C. 1+2+3…+100，可以用遞迴程式來計算8% (2)
-
D. 所有遞迴程式均可以改為迴圈程式來執行12% (3)
-
未填寫8% (2)
解說:
讓我們逐一分析這些敘述，看看哪一個是錯誤的：
(A) 遞迴程式必需要有以值傳遞之機制
這個敘述是錯誤的。遞迴程式不一定需要以值傳遞的機制。遞迴函數的設計可以使用參數傳遞（按值或按參考），但這並不是遞迴程序的必要條件。遞迴的關鍵在於函數調用自己，以及需要有適當的結束條件來防止無窮迴圈。
這個敘述是錯誤的。遞迴程式不一定需要以值傳遞的機制。遞迴函數的設計可以使用參數傳遞（按值或按參考），但這並不是遞迴程序的必要條件。遞迴的關鍵在於函數調用自己，以及需要有適當的結束條件來防止無窮迴圈。
(B) 遞迴程式必需要有結束條件
這個敘述是正確的。遞迴程序需要有結束條件(基本條件)，以確保遞迴能夠在某個時刻停止，否則會導致無窮遞迴和堆疊overflow。
這個敘述是正確的。遞迴程序需要有結束條件(基本條件)，以確保遞迴能夠在某個時刻停止，否則會導致無窮遞迴和堆疊overflow。
(C) 1+2+3…+100，可以用遞迴程式來計算
這個敘述是正確的。計算數字序列的和（如1+2+3+...+100）確實可以用遞迴程序來實現。例如，可以定義一個遞迴函數，每次調用自己以計算部分和，直到達到結束條件。
這個敘述是正確的。計算數字序列的和（如1+2+3+...+100）確實可以用遞迴程序來實現。例如，可以定義一個遞迴函數，每次調用自己以計算部分和，直到達到結束條件。
(D) 所有遞迴程式均可以改為迴圈程式來執行
這個敘述是正確的。理論上，所有的遞迴程序都可以轉換成迴圈程序，這是因為迴圈和遞迴都能完成相同的計算任務，只是它們的實現方式不同。實際上，許多遞迴程序在優化後可以被轉換為等效的迴圈形式。
這個敘述是正確的。理論上，所有的遞迴程序都可以轉換成迴圈程序，這是因為迴圈和遞迴都能完成相同的計算任務，只是它們的實現方式不同。實際上，許多遞迴程序在優化後可以被轉換為等效的迴圈形式。
答對率 : 68 %
以下敘述何者正確？
-
A. 演算法必須在有限步驟內結束執行動作72% (18)
-
B. 程式必須在有限步驟內結束執行動作4% (1)
-
C. 程式在有限步驟內會結束其執行動作而演算法則可能不會12% (3)
-
D. 演算法與程式均可能在有限步驟內無法結束其執行動作4% (1)
-
未填寫8% (2)
解說:
讓我們分析每個選項，以確定哪個敘述是正確的。
(A) 演算法必須在有限步驟內結束執行動作
這個敘述是正確的。演算法的定義要求它必須在有限步驟內完成，這是演算法的一個基本特徵。演算法的目標是提供一個清晰且可在有限時間內解決問題的方法。
這個敘述是正確的。演算法的定義要求它必須在有限步驟內完成，這是演算法的一個基本特徵。演算法的目標是提供一個清晰且可在有限時間內解決問題的方法。
(B) 程式必須在有限步驟內結束執行動作
這個敘述不完全正確。雖然理想情況下，程式應該在有限時間內結束執行，但在實際情況中，程式可能會陷入無窮迴圈或其他問題，導致無法在有限步驟內結束執行。
這個敘述不完全正確。雖然理想情況下，程式應該在有限時間內結束執行，但在實際情況中，程式可能會陷入無窮迴圈或其他問題，導致無法在有限步驟內結束執行。
(C) 程式在有限步驟內會結束其執行動作而演算法則可能不會
這個敘述是錯誤的。演算法需要在有限步驟內結束執行，而程式的執行有可能無窮迴圈或陷入死結，這樣程式就無法在有限步驟內結束執行。
這個敘述是錯誤的。演算法需要在有限步驟內結束執行，而程式的執行有可能無窮迴圈或陷入死結，這樣程式就無法在有限步驟內結束執行。
(D) 演算法與程式均可能在有限步驟內無法結束其執行動作
這個敘述部分正確，但並不完全。演算法應該在有限步驟內結束執行，而程式有可能因為錯誤或設計不良而無法在有限步驟內結束。然而，這個選項中「演算法」這部分是錯誤的，因此整體上這個選項也是錯誤的。
這個敘述部分正確，但並不完全。演算法應該在有限步驟內結束執行，而程式有可能因為錯誤或設計不良而無法在有限步驟內結束。然而，這個選項中「演算法」這部分是錯誤的，因此整體上這個選項也是錯誤的。
答對率 : 72 %