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

2的幂次方表示

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

【题目描述】

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


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

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

    分享给朋友：
    返回列表

    上一篇：学生分组

    下一篇：分数求和

    相关文章

    2021年青岛市程序设计竞赛试题（初中组）决赛

    2021年青岛市程序设计竞赛试题（初中组）决赛

    A.趣味三角(triangle.cpp) 【题目描述】 今天，新高一的OIer们第一次进入了机房。z老师想让他们喜欢上OI，于是给了他们每个人一个三角形。 这时候，小q秃发奇想，...

    【题解】航空母舰

    3.航空母舰（aircraft.cpp）【题目描述】航空母舰（Aircraft Carrier）,是一种以舰载机为主要作战武器的大型水面舰艇。依靠航空母舰，一个国家可以在远离其国土的地方、不依靠当地机...

    公路（road）

    公路（road）

    【题目描述】小苞准备开着车沿着公路自驾。公路上一共有n个站点，编号为从1 到n。其中站点i与站点i+1 的距离为vi公里。公路上每个站点都可以加油，编号为i 的站点一升油的价格为a...

    【题解】阶乘问题

    2.阶乘问题（fac.cpp）【题目描述】给定一个正整数n,求出一个最小的整数m并使得m！的末尾连续的0的个数小于n。m!=1*2*3*4*...*m【输入描述】第一行n。【输出描述】一个整数m。【样...

    【题解】报数游戏

    【题目描述】路飞在和他朋友们一块玩一个游戏。由于路飞的机智，这个游戏由路飞担任裁判。首先，路飞会给他们一个人一个编号，并且每个人的编号都不相同。接下来的每一个回合，会给一个数，编号不超过它的最大编号的...

    【题解】尼科彻斯定理

    【题目描述】 验证尼科彻斯定理，即：任何一个整数m的立方都可以写成m个连续奇数之和。【输入描述】任一正整数【输出描述】该数的立方分解为一串连续奇数的和【样例输入】13【样例输出】13*13*...

    鲁ICP备20008475号

    Powered By Z-BlogPHP. Theme by TOYEAN.