题解 | #2的幂次方#

典型的递归问题。

1. 对于x需要将其转化为2次幂的和
2. 而其中指数同样需要按第一条处理

因此递归函数就有了基本框架：

• 从大到小，提取x的二次幂的指数x'
• 对指数x'调用递归函数

最终代码如下

//
// Created by Zed on 2024/2/8.
//
#include <iostream>

using namespace std;

void reverse(int x) {
    if (x == 0) {//递归封口
        cout << 0;
        return;
    }
    bool first = false;//为了输出加号准备，在第一个加数出现后，需在后续每个加数后加上一个加号
    for (int i = 15; i >= 0; --i) {//2^15>20000
        if (x & (1 << i)) {//如果x=...+2^i+...，则x二进制表示第i位为1
            if(!first){
                first= true;
            }else{
                cout<<"+";
            }
            if (i != 1) {
                cout << "2(";
                reverse(i);
                cout << ")";
            } else {//特殊处理2^1
                cout << 2;
            }
        }
    }
}
int main() {
    int n;
    while (cin >> n) {
        reverse(n);
        cout << endl;
    }
    return 0;
}