题解 | #2的幂次方#

#include <string>
#include <iostream>

using namespace std;
string two(int n){
    string s;
    int m[20];
     if (n == 0){
         s = "0";
     }else if (n == 1){
         s = "2(0)";
     }else {
         int sum = 0,index = 0;
         while (n != 0){
             if (n % 2 == 1) {
                 m[sum++] = index;//这里注意，sum++是先赋值m[]，再让sum++，对应下面sum要先减1再计算s
             }
                 n = n / 2;
                 index++;
             
         }

         if (m[sum - 1] != 1) {
             s = "2(" + two(m[sum - 1]) + ")";//通过two[m[sum - 1]]先找到最小问题的解
         } else {
             s = "2";
         }

         if (sum > 1) {//如果分解个数大于1，通过这个步骤，实现最小问题的合，再自底向上实现递归
             for (int i = sum - 2; i >= 0; i--) {
                 if (m[i] != 1) {s = s + "+" + "2(" + two(m[i]) + ")";}
                 else{s = s + "+" + "2";}
             }
         }
     }
    return s;
}
int main(){
   int n;
   while(scanf("%d",&n) != EOF){
       cout<<two(n)<<endl; 
   }
    return 0;
}