2的幂次方表示题解

发布于 2018-12-06  747 次阅读


8758:2的幂次方表示

总时间限制:

1000ms

内存限制:

65536kB

描述

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

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(n≤20000)。

输出

一行,符合约定的n的0,2表示(在表示中不能有空格)。

样例输入

137

样例输出

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

来源

NOIP1998复赛 普及组 第一题

 

 

题解:将一个大数拆分为若干个2的n次方的和,并且将次方和再拆分成若干个部分,这样很容易就可以想起递归算法。

       实际上问题大致分为两步:

1.    将数字分解为2的n次方

2.    将n再次分解为2的n次方(调用自身,如果n==2则结束printf(“2”);

如果n==1 则printf(“2(0)”);)

#include
#include
#include
#include


void work(int n)
{
    if(n==1)//初始判断条件,如果n为1或2则直接输出 
    {
        printf("2(0)");
        return;
    }
    else if(n==2)
    {
        printf("2");
        return; 
    } 
    else
    {
        int j=1,i=0;//j每次乘2,如果大于了n就分解结束,i为当前次数 
        do
        {
            j*=2;
            if(j>n)
            {
                j/=2;
                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);
}