hce_nsysu
113年
計算機概論與程式設計
第 49 題
Given the following piece of code, which one of the following statements is NOT correct?
```c
#include
int main() {
int n1, n2, max;
scanf("%d %d", &n1, &n2);
max = (n1 > n2) ? n1 : n2;
while (1) {
if ((max % n1 == 0) && (max % n2 == 0)) {
printf("The result is %d\n", max);
break;
}
++max;
}
return 0;
}
```
```c
#include
int main() {
int n1, n2, max;
scanf("%d %d", &n1, &n2);
max = (n1 > n2) ? n1 : n2;
while (1) {
if ((max % n1 == 0) && (max % n2 == 0)) {
printf("The result is %d\n", max);
break;
}
++max;
}
return 0;
}
```
- A This program takes two integers as input and calculates the least common multiplier (LCM) of the two integers.
- B The variable max is used to store the LCM of the two input integers.
- C Given n1=4 and n2=3, the while loop iterates 9 times to find the answer.
- D The initial value of the variable max is the maximum of the two input integers.
- E The time complexity is O(max(n1, n2)).
思路引導 VIP
如果我們輸入兩個互質的大質數（例如 97 和 101），程式會從 101 開始逐一往後找。請試著思考：在遇到第一個能同時被這兩個數整除的數字之前，大約需要經過多少次累加？這個次數與「較大的那個輸入值」之間，是維持著固定的倍數關係，還是會隨著數值增大而呈現更劇烈的成長呢？
🤖
AI 詳解
AI 專屬家教
很高興看到你準確地辨識出選項 (E) 的錯誤！這代表你對於程式邏輯的追蹤以及時間複雜度 (Time Complexity) 的核心概念掌握得相當紮實。
最小公倍數的邏輯追蹤
這段程式碼的核心邏輯是從兩數中的較大者開始，逐一遞增（++max），直到找到第一個能同時被 $n_1$ 與 $n_2$ 整除的數。這正是求取最小公倍數 (LCM) 的暴力演算法實作。以選項 (C) 為例，當 $n_1=4, n_2=3$ 時，變數 max 從 $4$ 開始測試，依序檢查 $4, 5, 6, \dots, 12$，共經過 $9$ 次迴圈判斷才跳出，這證實了程式邏輯的正確性。
▼ 還有更多解析內容