Dark`Kris

Private blog

I'm spark , hope you fire


NOIp1998PJ/Luogu P1010 幂次方 解题报告

关于此题,我要感谢CoolTeam的题解,帮助我完成了此题

题目描述

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

137=2^7+2^3+2^0        同时约定方次用括号来表示,即a^b 可表示为a(b)。

由此可知,137可表示为:

2(7)+2(3)+2(0) 进一步:7= 2^2+2+2^0 (2^1用2表示)

3=2+2^0    所以最后137可表示为:

2(2(2)+2+2(0))+2(2+2(0))+2(0) 又如:

1315=2^10 +2^8 +2^5 +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表示(在表示中不能有空格)

输入输出样例

输入样例#1: 1315 输出样例#1: 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)


解题思路

递归/分治

CoolTeam的代码备注得很详细我就不多说什么了。

下面贴一下CoolTeam的代码吧:

#include<stdio.h>  
int a[55];  
int dfs(int n)  
{  
//幂为0、1、2则直接输出,>=3则递归求解。   
    int i=0;  
    if(n!=0)  
    {    
        while(n>=a[i]) i++; i--; //找到最大的幂  
        n-=a[i];//下面12~20行是处理减去的这部分。   
        printf("2");   
        if(i!=1)printf("(");//注意1次幂是2而不是2(1)      
        if( i==0 || i == 2 ) printf("%d)",i);//幂为0、1、2时可输出幂(幂1时无输出)   
        //如果幂>=3,对幂递归,不输出幂。   
        if(i>=3) {dfs(i);printf(")");}//递归求解,再添加右括号。  
        if(n!=0) {printf("+");dfs(n);}//子问题与子问题之间用+连接;处理剩余的n(子问题)。  
    }  
    return;  
}  
int main(void)  
{  
    int i,n;  
    a[0]=1;  
    for(i=1;i<50;i++)  
        a[i]=a[i-1]*2; //a:1 1 2 4 8 16 32……   
    scanf("%d",&n);  
    dfs(n);  
    return 0;   
}

感谢惠读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading