青少年编程知识记录 - 2的幂次方表示

2021年01月28日 14:30:31

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表示（在表示中不能有空格）。

【输入样例】

【输出样例】

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，可以通过枚举的方式进行。先去定义一个数组

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

.jztagtree{max-height:85vh;right:0px}.jzDown{top:10vh}.jztagtree li a{background-color:#448EF6}.jztagtree li a:before{border-right:10px solid #448EF6}.jztagtree li a:hover{background:#0045a6}.jztagtree li a:hover::before{border-right:10px solid #0045a6}

$("#jztoc").toc({content: ".single", headings: "h1,h2,h3"});