当前位置：首页 > 题解目录 > 正文内容

2的幂次方表示

亿万年的星光4年前 (2021-01-28)题解目录1112

【题目描述】

任何一个正整数都可以用2的幂次方表示。例如：
137=2⁷+2³+2⁰

同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：
2(7)+2(3)+2(0)
进一步：7=2²+2+2⁰（21用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表示（在表示中不能有空格）。

【输入样例】

【输出样例】

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

【分析】

（1）2¹不能写成2¹，只能写成2
（2）最后分解的结果只有2和0，没有分解的继续分解
（3）最后的结果是一堆字符串的形式

【思路1】: 递归模式

//2的幂次方表示 
#include<iostream>
#include<string> 
using namespace std;
string cf(int n) {
    if(n==1) return "2(0)";   //递归结束情况 
    if(n==2) return "2";     //递归结束情况 
    int l=1,c=0;   //初值和次数 
    while(l*2<=n) {  
        l*=2;  // l是比n小的可以表示成2的c次方的最小数 
        c++;  //结束之后c值会保留最高次数 ，
    }
    string h;  //用h表示最终的结果 
    if(l==2) 
        h+="2";
    else 
        h+="2("+cf(c)+")";  //继续递归，直到结束     
    if(l==n) 
        return h;    
    h+="+" + cf(n-l);  //n-l表示剩余部分，继续递归 
    return h;
}
int main() {
    int n;
    cin>>n;
    cout<<cf(n);
    return 0;
}

【思路2】：模拟和枚举

在初赛部分讲过进制转换，枚举到2的10次方，然后这个题的数据范围是20000，可以通过枚举的方式进行。先去定义一个数组

int num[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
// 最后一个32768是2的16次方

然后在计算中先找出最大的那个数，减去最大那个数之后就继续。

#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio> 
using namespace std;
int num[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
void digui(int x)
{
    if(x==0)  //0的情况 
    {
        printf("0");
        return ;
    }
    if(x==1)  //1的情况 
    {
        printf("2(0)");
        return ;
    }
    if(x==2) //2的情况 
    {
        printf("2");
        return ;
    }
    
    for(int i=14;i>=0;i--)
    {
        if(x>=num[i])  //从最大数开始找 
        {
            x-=num[i]; //减去最大的那个 
            printf("2");
            if(i!=1)
            {
                printf("(");
                digui(i);
                printf(")");
            }
            if(x!=0)   // 如果没有分解完，就输出+号 
                printf("+");
        }
    }
}
int main()
{
    int i,j;
    int n;
    scanf("%d",&n);
    digui(n);
    printf("\n");
    return 0;
}

补充：对于此题，不同数值表示方式

    s[1]="2(0)";           //1=2^0
    s[2]="2";              //2=2^1
    s[3]="2(2)";        //4=2^2
    s[4]="2(2+2(0))";    //8=2^3=2^(2+1)=2^2+2^1
    s[5]="2(2(2))";      //16=2^4,4="2(2)"  ,4前面出现过，直接使用
    s[6]="2(2(2)+2(0))";//32=2^5=2^(4+1) =2^4+2^1
    s[7]="2(2(2)+2)";     //64=2^6=2^(4+2) =2^4+2^2
    s[8]="2(2(2)+2+2(0))";             //128=2^7=2^(4+2+1)=2^4+2^2+2^1
    s[9]="2(2(2+2(0)))"    ;            //256=2^8, 8前面出现过，直接用
    s[10]="2(2(2+2(0))+2(0))";        //512=2^9=2^(8+1)=2^8+2^1
    s[11]="2(2(2+2(0))+2)";            //1024=2^10=2^(8+2)=2^8+2^2
    s[12]="2(2(2+2(0))+2+2(0))";    //2048=2^11=2^(8+2+1)=2^8+2^2+2^1
    s[13]="2(2(2+2(0))+2(2))";        //4096=2^12=2^(8+4)=2^8+2^4
    s[14]="2(2(2+2(0))+2(2)+2(0))";    //8192=2^13=2^(8+4+1)=2^8+2^4+2^1
    s[15]="2(2(2+2(0))+2(2)+2)";//16384=2^14=2^(8+4+2)=2^8+2^4+2^2
    s[16]="2(2(2+2(0))+2(2)+2+2(0))";//32768=2^15=2^(8+4+2+1)=2^8+2^4+2^2+2^1