题目

1208：2的幂次方表示

时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
任何一个正整数都可以用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)

题目分析：题目要求在最后的结果只有0和2这两个数字，其它数字一律用2的n次方表示，这里面的n也需要进行以上处理，所以可以考虑用递归算法。

C++代码

#include<iostream>
using namespace std;
string f(unsigned int n)
{
	if(n==0)
		return "0";
	unsigned int i,t;
	for(i=0,t=1;t<=n;i++)//把n分成2的i次方+j
		t*=2;
	i--; 
	t/=2;
	string result;
	if(i==1)//2的1次方直接返回2
		result="2";
	else
	{
		result="2(";
		result+=f(i);//递归求i的表示方法
		result+=")";	
	}
	if(n-t)//还有剩余的数，即j>0
	{
		result+="+";
		result+=f(n-t);//递归求j的表示方法
	}
	return result;
}
int main()
{
	unsigned int n;
	cin>>n;
	cout<<f(n);
	return 0;
}