2的幂次方表示
【题目描述】
任何一个正整数都可以用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
(adsbygoogle = window.adsbygoogle || []).push({});