算法訓練：2 的次冪表示（遞歸輸出）

問題描述

將正整數 n (≤20000) 表示為 2 的次冪和，次冪再遞歸展開。約定：a^b 寫作 a(b)，2^1 寫作 2，2^0 寫作 2(0)。項之間用 '+' 連接，無空格。

遞歸算法

函數 print(n)：
1. 將 n 轉二進制，記錄為 1 的位位置（從高到低）。
2. 對每個位 k：
- k=0: 輸出 "2(0)"
- k=1: 輸出 "2"
- k=2: 輸出 "2(2)"
- k>2: 輸出 "2("，遞歸 print(k)，輸出 ")"
3. 非最後一項後輸出 '+'。
遞歸邊界：0,1,2 直接輸出對應字符串。

代碼

#include <cstdio>
void print(int n) {
    int bits[20], cnt = 0;
    for (int i = 0; n; ++i) {
        if (n & 1) bits[cnt++] = i;
        n >>= 1;
    }
    for (int i = cnt - 1; i >= 0; --i) {
        int k = bits[i];
        if (k == 0) printf("2(0)");
        else if (k == 1) printf("2");
        else if (k == 2) printf("2(2)");
        else { printf("2("); print(k); printf(")"); }
        if (i) printf("+");
    }
}
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        print(n);
        puts("");
    }
    return 0;
}