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

2的幂次方表示

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

【题目描述】

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


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

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

分享给朋友：
返回列表

上一篇：学生分组

下一篇：分数求和

相关文章

【题解】车辆管理

【题目描述】交通管理局长氓氓现在需要一个管理汽车的系统，每一辆汽车都有许多信息需要去记录。 首先，每一辆汽车都有一个独一无二的车牌号 S，车牌号由 7 个字符组成。 然后，对于每一辆车要记录它的排...

分数求和

题目描述】输入n个分数并对他们求和，并用最简形式表示。所谓最简形式是指：分子分母的最大公约数为1；若最终结果的分母为1，则直接用整数表示。如： 5/6  、 10/3  均是最简形...

【题解】给定和为定数

【题目描述】给出若干个整数，询问其中是否有一对数的和等于给定的数。【输入描述】第一行是整数n(0 < n ≤ 100,000)，表示有n个整数。第二行是n个整数。整数的范围是在0到108之间。第...

八皇后2

【题目描述】会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8...

2021年市北区程序设计竞赛试题（初中组）

2021年市北区程序设计竞赛试题（初中组）

1.开关灯（light.cpp）【题目描述】某实验室共有n盏灯，灯的编号为1~n,每盏灯的初始状态是关闭的。现在有m位学生，每位学生可以前去抽取一张带数字的卡片，其数字为Ai，然后依次将自己手中的数字...

字符全排列(2)

【题目描述】从n个字符(n从a开始，依次递增)中选取r个字符，对r个字符进行不重复排列。字典序小的在前面。【输入描述】一行，n和r【输出描述】r个字符的所有组合，每种组合占一行，字符和字符之间用空格隔...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.