题解 | #2的幂次方#

递归分解二进制

• ①n=0 ②n=1 ③n>=2 :需要递归分解

注意：

• 当n=1时，输出2(0)
• 而递归调用时：若分解出的指数为1，对应字符串是2,而不是2(2(0))

#include<iostream>
#include<string>
using namespace std;

string two(int a){
    string s;
    if(a==0)s="0";//递归出口
    else if(a==1)s="2(0)";

    else{
      int m[20];//记录分解后对应2的指数
      int powx=0,sum=0;//指数、分解个数
      while(a!=0){
        if(a%2==1)m[sum++]=powx;
        a=a/2;
        powx++;
      }
      
      if(m[sum-1]!=1)s="2(" + two(m[sum-1]) + ")" ;//当指数为1时，是2,而不是2(2(0))
      else s="2" ;//
      
      if(sum>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;
}