2的幂次方

此题的题意是给定一个数n，先分解成二进制和的形势2的i次方的和 。
比如： ，而系数 ，直到2上面的系数i全为0或者1为止。
2直接输出为2， 输出为2(0),
所以输入为9，输出为2(2+2(0))+2(0),即 。

所以此题非常适合使用递归策略。

// runtime: 4ms
// space: 488K
#include <iostream>
#include <vector>

using namespace std;
// 计算base的n次方。
int MyPow(int base, int n) {
    int result = 1;
    for (int i = 0; i < n; ++i) {
        result *= base;
    }
    return result;
}
// 把n转换成2的i次方的系数集合，如n=9，返回值是3和0。
vector<int> ToArray(int n) {
    vector<int> a;
    int i = 0;
    while (n > 0) {
        while (n - MyPow(2, i) > 0) {
            i++;
        }
        if (n < MyPow(2, i)) {
            i--;
        }
        n = n - MyPow(2, i);
        a.push_back(i);
        i = 0;
    }
    return a;
}
// 构建答案
string Build(int num) {
    vector<int> n;
    n = ToArray(num);
    int size = n.size();
    string str = "";
    for (int i = 0; i < size; ++i) {
        if (n[i] == 1)
            str += "2";
        else if (n[i] == 0)
            str += "2(0)";
        else
            str +=  "2(" + Build(n[i]) + ")";

        if (i != size - 1)
            str+="+";
    }
    return str;
}

int main() {
    int n;
    while (cin>> n) {
        cout<< Build(n) << endl;
    }
    return 0;
}