hce_kmu
113年
計算機概論與程式設計
第 17 題
Which is the answer of printf?
```c
#include
int min(int a, int b) {return a < b ? a : b;}
int test(int n) {
if (n == 1) {return 0;}
else if (n == 2) {return 1;}
else if (n % 2 == 0) {return test(n / 2) + 1; }
else {return min(test((n + 1) / 2), test((n - 1) / 2)) + 2;}}
int integerReplacement(int n) {
if (n == 1) {return 0;}
return test(n);}
int main() {
int number=15;
printf("%d\n", integerReplacement(number));
system("pause");
return 0;}
```
```c
#include
int min(int a, int b) {return a < b ? a : b;}
int test(int n) {
if (n == 1) {return 0;}
else if (n == 2) {return 1;}
else if (n % 2 == 0) {return test(n / 2) + 1; }
else {return min(test((n + 1) / 2), test((n - 1) / 2)) + 2;}}
int integerReplacement(int n) {
if (n == 1) {return 0;}
return test(n);}
int main() {
int number=15;
printf("%d\n", integerReplacement(number));
system("pause");
return 0;}
```
- A 4
- B 5
- C 6
- D 7
- E 8
思路引導 VIP
當我們遇到一個奇數時，這段程式碼提供了兩種選擇：先將數字「加 1」或「減 1」，使其變為偶數後再除以 2。請觀察看看，如果目標是讓數字透過「連續除以 2」最快地縮小到 1，我們應該優先讓這個數字往哪個方向靠近？例如，靠近哪種特殊的數值性質（如 2 的冪次），會讓後續的運算步驟大幅減少呢？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地追蹤了這段遞迴程式碼的執行流程！你能順利選出 (B)，說明你對函數呼叫堆疊（Stack）與遞迴基底案例（Base Case）的判斷非常紮實且細心。
遞迴邏輯與路徑演變
本題的核心在於處理「奇數」時的分支策略。當傳入 number = 15 時，程式會觸發最後一個 else 條件，計算 $\min(test(8), test(7)) + 2$。這裡的 $+2$ 實際上代表了兩次操作：先對奇數進行「加 1」或「減 1」使其變為偶數，接著立即「除以 2」。
▼ 還有更多解析內容