申論題 - 阿摩線上測驗

申論題資訊

試卷：110年 - 110 普通考試_資訊處理：程式設計概要#102788
科目：程式設計
年份：110年
排序：0

題組內容

二、程式語言 C 的程式碼是由許多函式（Function）組成。

申論題內容

(一)請說明上述程式執行的結果。

詳解 (共 2 筆)

詳解提供者：Lin Tony

f(20,10)
============================
sum = B(1,2)
sum = 0
============================
sum = B(2,2)
n = 2,k = 2
memo[2][2] = 1
sum = 1
============================
sum = 1 + B(4,2)
n = 4, k = 2
memo[4][2] = B(3,1) + B(3,2)
memo[3][1] = B(2,0) + B(2,1)
memo[2][0] =1
memo[3][1] = 1 + B(2,1)
memo[2][1] = B(1,0) + B(1,1)
memo[1][0] = 1
memo[1][1] = 1
memo[2][1] = 2
num = 2
memo[3][1] = 1 + 2 = 3
num = 4
memo[4][2] = 3 + B(3,2)
memo[3][2] = B(2,1) + B(2,2)
memo[3][2] = 2 + 1 = 3
num = 6
memo[4][2] = 6
num = 8
sum = 7
============================
sum = 7 + B(5,2)
memo[5][2] = B(4,1) + B(4,2)
memo[5][2] = 6 + B(4,1)
memo[4][1] = 3 + B(3,0)
memo[3][0] = 1
memo[4][1] = 4
num = 10
memo[5][2] = 10
num = 12
sum = 17
============================
sum = 17 + B(7,2)
memo[7][2] = B(6,1) + B(6,2)
memo[6][1] = B(5,0) + B(5,1)
memo[5][0] = 1
memo[6][1] = 1 + B(5,1)
memo[5][1] = B(4,0) + B(4,1)
memo[5][1] = 1 + 4 = 5
num = 14
memo[6][1] = 6
num = 16
memo[7][2] = 6 + B(6,2)
memo[6][2] = B(5,1) + B(5,2) = 5 + 10
memo[6][2] = 15
num = 18
memo[7][2] = 21
num = 20
sum = 38
============================
sum = 38 + B(8,2)
memo[8][2] = B(7,1) + B(7,2)
memo[8][2] = B(7,1) + 21
memo[7][1] = B(6,0) + B(6,1)
memo[6][0] = 1
memo[7][1] = 1 + 6
num = 22
memo[8][2] = 28
num = 24
sum = 66

g() = 20 + 10 + 8 + 17 + 15 + 5 + 3 + 12 + 10 + 0 + 1
g() = 30 + 25 + 20 + 15 + 11
g() = 101

詳解提供者：hchungw

此 C 程式碼包含了幾個函數：B、f、g 和 main。

函數 B(int n, int k) 似乎是計算二項式係數（組合數 C(n, k) 或 "n 選 k"）的實現。它使用了記憶化技巧來儲存已計算過的結果以避免重複計算，memo 陣列用於此目的。如果 k 等於 0 或等於 n，則返回 1；否則，計算 B(n-1, k-1) + B(n-1, k)。

函數 f(int N, int M) 計算從 1 到 N 的所有 i 的 B(i, 2) 的總和，但會跳過任何 i 是 M 的倍數的情況，如果 i 等於 0 則終止迴圈。最後打印總和和 number 的值，其中 number 是在 B 函數中被設置為 2。

函數 g(int N, int M) 是一個遞迴函數，當 N 或 M 小於或等於 0 時，返回 1；否則，它遞迴地調用自身兩次：g(N - 2, M - 3) 和 g(M, N)，並返回它們的和。

在 main 函數中，首先調用 f(20, 10)。這將會執行上面描述的 f 函數的邏輯。然後，它調用 printf 打印 g(20, 10) 的結果。

由於 g 函數的結果依賴於 N 和 M 的初值並透過遞迴進行計算，而 f 函數則依賴於二項式係數的計算和是否跳過特定的 i 值。要精確地提供這個程式碼的輸出結果需要執行這個程式。不過，由於 B 函數的記憶化部分，我們可以確信它的目的是提高效率，避免重複計算二項式係數。f 函數計算特定的總和，並在過程中忽略了 M 的倍數的 i 值。而 g 函數通過遞迴計算，其結果取決於特定的初始條件和遞迴樹的深度。

最終輸出會顯示 f 函數的總和和 number 的值（如果 f 函數完整執行），以及 g(20, 10) 的計算結果。由於給定的程式碼片段沒有包含所有函數的實作細節，比如 memo 陣列的初始化情況，我們無法確定具體的數值輸出。