PID277 / 整数拆分 （递归）

任何一个正整数都可以用2的幂次方表示。例如： {40%}

137=27+23+20

同时约定方次用括号来表示，即ab 可表示为a（b）。

由此可知，137可表示为：

2（7）+2（3）+2（0）

进一步：7= 22+2+20 （21用2表示）

3=2+20

所以最后137可表示为：

2（2（2）+2+2（0））+2（2+2（0））+2（0）

又如：

1315=210 +28 +25 +2+1

所以1315最后可表示为：

2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）

输入：正整数（n≤20000）

输出：符合约定的n的0，2表示（在表示中不能有空格）

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

void solve(int n)
{
    int i,b[50],p=0;
    for(i=0;n>0;i++,n>>=1)      //二进制转换，应该是最快的方法吧。
        b[i]=n&1;
    for(i--;i>1;i--)
    {
        if(b[i]&1)
        {
            if(p) printf("+");
            printf("2(");
            solve(i);
            printf(")");
            p=1;
        }
    }
    if(b[1]&1)    //特例1
    {
        if(p) printf("+");
        printf("2");
        p=1;
    }
    if(b[0]&1)   //特例2
    {
        if(p) printf("+");
        printf("2(0)");
    }
}



int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        solve(n);
        printf("\n");
    }
    return 0;
}