题解 | 2的幂次方

考察递归和分治思想，这道题我做了挺久的，要注意（）和+这两个符号的添加，明确知道每一轮遍历想得到什么结果，

对于一个n，使用递归函数是为了得到仅包含2，+，2（0）这几个字符的字符串，因此设置res空字符串用于拼接，同时考虑什么时候是拼2，拼+，拼2（0），注意每轮都是遍历完n的2次幂数组才返回res。

#include<stdio.h>
#include<string>
#include<iostream>
#include<vector>
using namespace std;
string fun(int n) {
    vector<int> mi;
    //1.n转成2的幂次和,用一个动态数组保存,2^15=32768>20000
    for (int i = 0; i < 15; i++) {
        //1左移0位=2^0,1左移1位=2^1,1左移2位=2^2
        if (n & (1 << i)) {//若n的第i位为1
            mi.push_back(i);
        }
    }
    //把大问题变成小问题，返回小问题求解的结果，从而递归解决大问题
    string res = "";
    //2.遍历保存2次幂的动态数组,因为输出幂的顺序是从大到小的，从后开始遍历
    for (int i = mi.size() - 1; i >= 0; i--) {
        if (mi[i] == 0) {
            res += "2(0)";

        } else if (mi[i] == 1) {
            res += "2";

        } else {
            res += "2(" + fun(mi[i]) + ")";
        }
        //除了最后一次，每次拼接后，加一个“+”
        if (i != 0)res += "+";

    }
    //3.注意要遍历完数组完成res的拼接再放回最终结果
    return res;

}
int main() {
    int n;

    while (scanf("%d", &n) != EOF) {
        printf("%s\n", fun(n).c_str());

    }
    return 0;
}