2的幂次方表示

【题目描述】

任何一个正整数都可以用2的幂次方表示。例如：
137=$2^7$+$2^3$+$2^0$
同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：
2(7)+2(3)+2(0)
进一步：7=$2^2$+2+$2^0$（21用2表示）
3=2+$2^0$
所以最后137可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如：
1315=$2^{10}$+$2^8$+$2^5$+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）$2^1$不能写成$2^1$，只能写成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

---

返回目录：题解目录

---