2的幂分解（NOIP1998）

diggersun

任何一个正整数都可以用2的幂次方表示.例如:137=2^7+2^3+2^0同时约定次方用括号来表示,即a^b可表示为a(b)由此可知,137可表示为:2(7)+2(3)+2(0)进一步:7=2^2+2+2^0 (2^1用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<=20000)输出:符合约定的n的0,2表示(在表示中不能有空格)

1. #include<iostream>
   
2. using namespace std;
   
3. void mysearch(int i)
   
4. {   int r,s;
   
5.     if (i==1) cout<<"2(0)";
   
6.     else if (i==2) cout <<'2';
   
7.     else if (i>2)
   
8.     {
   
9.         s=2;
   
10.         r=0;
    
11.         while (i>=s)
    
12.         {
    
13.             s=s*2;
    
14.             r++;
    
15.         }
    
16.         cout<<"2(";
    
17.         mysearch(r);
    
18.         cout<<')';
    
19.         s=s/2;
    
20.         if (i-s>0)
    
21.         {
    
22.             cout<<'+';
    
23.             mysearch(i-s);
    
24.         }
    
25.     }
    
26. }
    
27. int main()
    
28. {
    
29.     mysearch(100);return 0;
    
30. }
    

复制代码

diggersun

这个题考虑用递归来做，那么递归有两个出口，一个是1，一个是2，其他的数字都可以化成2^X1+2^X2+2^X3+***的形式，