总时间限制: 1000ms 内存限制: 65536kB描述
任何一个正整数都可以用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)
来源NOIP1998复赛 普及组 第一题
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<cmath>
5 void work(int n)
6 {
7 if(n==1)
8 {
9 printf("2(0)");
10 return;
11 }//初始判断条件,如果n为1或2则直接输出
12 else if(n==2)
13 {
14 printf("2");// 2的一次方
15 return;
16 }
17 else
18 {
19 int j=1,i=0;//j每次乘2,如果大于了n就分解结束,
20 //i为当前次数(指数)
21 do
22 {
23 j=2*j;
24 if(j>n)
25 {
26 j/=2;//回退到当j<n时
27 if(i==1)//这步非常重要,确定是否需要继续 2()
28 printf("2");
29 else
30 {
31 printf("2(");
32 work(i);
33 printf(")");
34 }
35 if(n-j!=0)
36 { //如果n分解之后还有剩余的数,那么继续分解
37 printf("+");
38 work(n-j);
39 }
40 return;
41 }
42 else
43 i++;
44 } while(1);
45 }
46 }
47 int main()
48 {
49 int n;
50 scanf("%d",&n);
51 work(n);
52 }