8758:2的幂次方表示

8758:2的幂次方表示

• 查看
• 提交
• 统计
• 提问

总时间限制: 

1000ms

 

内存限制: 

65536kB

描述

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

    137=2⁷+2³+2⁰

同时约定方次用括号来表示，即a^b可表示为a(b)。由此可知，137可表示为：

    2(7)+2(3)+2(0)

进一步：7=2²+2+2⁰（2¹用2表示）

        3=2+2⁰

所以最后137可表示为：

    2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如：

    1315=2¹⁰+2⁸+2⁵+2+1

所以1315最后可表示为：

    2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

输入

一个正整数n（n≤20000）。

输出

一行，符合约定的n的0，2表示（在表示中不能有空格）。

样例输入

137

样例输出

2(2(2)+2+2(0))+2(2+2(0))+2(0)

来源

NOIP1998复赛 普及组 第一题

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
void work(int n)
{
    if(n==1) 
    { 
        printf("2(0)");
        return;
    }//初始判断条件，如果n为1或2则直接输出
    else if(n==2) 
    {
        printf("2");// 2的一次方 
        return;
    }
     else 
    {
        int j=1,i=0;//j每次乘2,如果大于了n就分解结束，
                    //i为当前次数(指数)
        do 
        {
            j=2*j;
            if(j>n) 
            {
                j/=2;//回退到当j<n时 
                if(i==1)//这步非常重要，确定是否需要继续 2()
                    printf("2");
                else 
                {
                    printf("2(");
                    work(i);
                    printf(")");
                }
                if(n-j!=0) 
                { //如果n分解之后还有剩余的数，那么继续分解
                    printf("+");
                 work(n-j);
                }
                return;
            } 
            else
            i++;
        } while(1);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    work(n);
}