國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

109年普考資料處理概要

答：

(一)印出結果

1.程式是判斷在給定的數列 arr 中，是否存在一個子集，其數字的總和等於 sum。

2.當 n = 4 (也就是數字 8) 時，有兩個選擇：

  (1)包含8，然後從 {7, 3, 2, 5} 中尋找總和為14-8 = 6的數字組合。

  (2)不包含8，直接在 {7, 3, 2, 5} 中尋找總和為14的數字組合。

  以上的每個選擇會再帶來兩個新的選擇，這就是遞迴的過程。

3.透過不斷的選擇 arr[n] 和不選擇 arr[n]，程式嘗試找出是否有一組數字的總和可以等於 14。

4.在這個程式中，答案是 Yes，因為7+2+5 = 14。所以程序會在某個遞迴分支上返回 true。

(二)計算過程

sqst(arr, 4, 14)：

    sqst(arr, 4-1, 14-arr[4]) = sqst(arr, 3, 14-8) = sqst(arr, 3, 6)

    sqst(arr, 4-1, 14) = sqst(arr, 3, 14)

sqst(arr, 3, 6)：

    sqst(arr, 3-1, 6-arr[3]) = sqst(arr, 2, 6-5) = sqst(arr, 2, 1)

    sqst(arr, 3-1, 6) = sqst(arr, 2, 6)

sqst(arr, 2, 1)：

    sqst(arr, 2-1, 1-arr[2]) = sqst(arr, 1, 1-2) = sqst(arr, 1, -1)

    sqst(arr, 2-1, 1) = sqst(arr, 1, 1)

sqst(arr, 1, -1)：return false;

sqst(arr, 1, 1)：

    sqst(arr, 1-1, 1-arr[1]) = sqst(arr, 0, 1-3) = sqst(arr, 0, -2)

    sqst(arr, 1-1, 1) = sqst(arr, 0, 1)

sqst(arr, 0, -2)：return false;

sqst(arr, 0, 1)：

    sqst(arr, 0-1, 1-arr[0]) = sqst(arr, -1, 1-7) = sqst(arr, -1, -6)

    sqst(arr, 0-1, 1) = sqst(arr, 0, 1) = sqst(arr, -1, 1)

sqst(arr, -1, -6)：return false;

sqst(arr, -1, 1)：return false;

sqst(arr, 2, 6)：

    sqst(arr, 2-1, 6-arr[2]) = sqst(arr, 1, 4)

    sqst(arr, 2-1, 6) = sqst(arr, 1, 6)

sqst(arr, 1, 4)：

    sqst(arr, 1-1, 4-arr[1]) = sqst(arr, 0, 4-3) = sqst(arr, 0, 1)

    sqst(arr, 1-1, 4) = sqst(arr, 0, 4)

sqst(arr, 0, 4)：

    sqst(arr, 0-1, 4-arr[0]) = sqst(arr, -1, 4-7) = sqst(arr, -1, -3)

    sqst(arr, 0-1, 4) = sqst(arr, -1, 4)

sqst(arr, -1, -3)：return false;

sqst(arr, -1, 4)：return false;

sqst(arr, 3, 14)：

    sqst(arr, 3-1, 14-arr[3]) = sqst(arr, 2, 14-5) = sqst(arr, 2, 9)

    sqst(arr, 3-1, 14) = sqst(arr, 2, 14)

sqst(arr, 2, 9)：

    sqst(arr, 2-1, 9-arr[2]) = sqst(arr, 1, 9-2) = sqst(arr, 1, 7)

    sqst(arr, 2-1, 9) = sqst(arr, 1, 9)

sqst(arr, 1, 7)：

    sqst(arr, 1-1, 7-arr[1]) = sqst(arr, 0, 7-3) = sqst(arr, 0, 4)

    sqst(arr, 1-1, 7) = sqst(arr, 0, 7)

sqst(arr, 0, 7)：

    sqst(arr, 0-1, 7-arr[0]) = sqst(arr, -1, 7-7) = sqst(arr, -1, 0)

    sqst(arr, 0-1, 7) = sqst(arr, -1, 7)

sqst(arr, -1, 0)：return true;

sqst(arr, -1, 7)：return false;

sqst(arr, 1, 9)：

    sqst(arr, 0-1, 9-arr[1]) = sqst(arr, -1, 9-3) = sqst(arr, -1, 6)

    sqst(arr, 0-1, 9) = sqst(arr, -1, 9)

sqst(arr, -1, 6)：return false;

sqst(arr, -1, 9)：return false;