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

2的幂次方表示

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

【题目描述】

任何一个正整数都可以用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)

【分析】

（1）21不能写成21，只能写成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，可以通过枚举的方式进行。先去定义一个数组

1
2
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


    扫描二维码推送至手机访问。

    版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。

    分享给朋友：
    返回列表

    上一篇：学生分组

    下一篇：分数求和

    相关文章

    【题解】计数2的N次方

    【题目描述】任意给定一个正整数N(N≤100)，计算2的n次方的值。【输入描述】输入一个正整数N。【输出描述】输出2的N次方的值。【样例输入】5【样例输出】32【参考答案】#include<io...

    【题解】怪盗基德的滑翔翼

    【题解】怪盗基德的滑翔翼

    【题目描述】怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。有一天，怪盗...

    连词成句

    【题目描述】有一天，毛毛上课的时候遇到了一个难题，老师让同学们把黑板上的单词连成一句话。已知连词的规则是：从待选词中选出正确的单词按照顺序输出，“正确的单词”表示除第一个单词外，其余单词都是小写字母，...

    【题解】柠檬水找零

    【题目描述】在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你...

    学生分组

    【题目描述】有N组学生，给出初始时每组中的学生个数，再给出每组学生人数的上界R和下界L(L≤R)，每次你可以在某组中选出一个学生把他安排到另外一组中，问最少要多少次才可以使N组学生的人数都在[L,R]...

    【题解】数字的选择

    【题目描述】有n个非负整数，请从这n个非负整数中，选出m个数，在不改变m个数的顺序的情况下，构成一个新数列，要求该数列的中相邻两个数的差值绝对值的和尽可能小。请问，这个最小的差值绝对值的和是多少？比如...

    鲁ICP备20008475号

    Powered By Z-BlogPHP. Theme by TOYEAN.