Description
任何一个正整数都可以用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)
Input一个正整数n(n≤20000)。Output一行,符合约定的n的0,2表示(在表示中不能有空格)。Sample Input137
Sample Output
2(2(2)+2+2(0))+2(2+2(0))+2(0)
递归求解问题
分解表达式可得 最小组成单位 ‘2’,’+’,”2(“,”2(0)”,’)’;
判断终止条件, 当n == 2 或者n == 1;
技巧, 求小于n的2的次方的最大值
#include<iostream>
using namespace std;
void binary_(int n)
{
if(n == 1)
cout<<"2(0)";//如果n= 1,则直接输出2(0)
else if(n == 2)
cout<<"2";//如果n = 2,则直接输出2
else
{
int j = 1, i = 0;
do//调用循环求得不大于n的2的整数次方的最大值j
{
j*=2;
if(j>n)
{
j/=2;
if(j == 2)
cout<<"2";
else
{
cout<<"2(";
binary_(i);
cout<<")";
}
if(n - j != 0)
{
cout<<'+';
binary_(n-j);
}
return ;
}
i++;
}
while(1);
}
}
int main(void)
{
int n;
cin>>n;
binary_(n);
return 0;
}