台綜大B30 計概114 第六題 解答 ※ 販售必究 ※ 台灣綜合大學, 資訊管理系, 轉學考

※ 請供考生參考 / 營利必究 ※

 Q6. 如下，請計算當 n = 5 時，第 6 行語句（r = r + 1;）會被執行多少次。

int mystery(n) {

    int r = 0;

    for (int i = 1; i <= n - 1; i++)

        for (int j = i + 1; j <= n; j++)

            for (int k = 1; k <= j; k++)

                for (int m = 1; m <= k; m++)

                    r = r + 1;

    return r;

}

Ans:

int mystery(n) {

    int r = 0;

    for (int i = 1; i <= n - 1; i++)          // ①

        for (int j = i + 1; j <= n; j++)      // ②

            for (int k = 1; k <= j; k++)      // ③

                for (int m = 1; m <= k; m++)  // ④

                    r = r + 1;                // ⑤ (我們要計算的次數)

    return r;

}

內層迴圈展開

最內層 (m 迴圈)：

• for (m = 1; m <= k; m++)

• 執行次數 = k

所以對於固定的 k，⑤ 執行次數 = k

---

第三層迴圈 (k 迴圈)

• for (k = 1; k <= j; k++)

• 執行總次數 = 1 + 2 + 3 + ... + j = j(j+1)/2

所以對於固定的 j，⑤ 執行次數 = j(j+1)/2

---

第二層迴圈 (j 迴圈)

• for (j = i+1; j <= n; j++)

• 所以對於固定的 i，⑤ 執行次數 =

  $$\sum_{j=i+1}^{n} \frac{j(j+1)}{2}$$

---

第一層迴圈 (i 迴圈)

• for (i = 1; i <= n-1; i++)

• 所以總次數 =

  $$\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{j(j+1)}{2}$$

---

代入 n = 5

我們要算：

$$\sum_{i=1}^{4} \sum_{j=i+1}^{5} \frac{j(j+1)}{2}$$

逐步計算：

• i = 1 → j = 2..5

  $$\frac{2\cdot3}{2} + \frac{3\cdot4}{2} + \frac{4\cdot5}{2} + \frac{5\cdot6}{2} = 3 + 6 + 10 + 15 = 34$$

• i = 2 → j = 3..5

  $$6 + 10 + 15 = 31$$

• i = 3 → j = 4..5

  $$10 + 15 = 25$$

• i = 4 → j = 5

  $$15$$

---

總和

$$34 + 31 + 25 + 15 = 105$$

---

✅ 答案：當 n = 5 時，語句 r = r + 1; 會執行 105 次。