首页 > 代码库 > PID277 / 整数拆分 (递归)

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;
}


PID277 / 整数拆分 (递归)