首页 > 代码库 > 递归--练习9--noi8758 2的幂次方表示

递归--练习9--noi8758 2的幂次方表示

递归--练习9--noi8758 2的幂次方表示

一、心得

找准子问题就好 

二、题目

8758:2的幂次方表示

总时间限制: 
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复赛 普及组 第一题

三、AC代码

 1 /*
 2 noi8758 2的幂次方表示
 3 
 4 找准子问题就好 
 5 */
 6 #include <iostream>
 7 #define Max 21
 8 using namespace std;
 9 //将一个数转化为2进制 
10 void to2(int n,int (&a)[Max]){
11     int i=0;
12     while(n!=0){
13         a[i++]=n%2;
14         n/=2;
15     }
16 }
17 //打印数组
18 void printArray(int a[],int n){
19     for(int i=0;i<=n;i++){
20         cout<<a[i]<<" ";
21         if((i+1)%5==0){
22             cout<<endl;
23         }
24     } 
25     cout<<endl;
26 } 
27 //递归操作
28 void f(int n){
29     int a[Max]={0};
30     to2(n,a);
31     //printArray(a,20);
32     int first=1;
33     
34     
35     for(int i=Max;i>=3;i--){
36         if(a[i]==1){
37             if(first){
38                 cout<<"2(";
39                 f(i);
40                 cout<<")";
41                 first=0;
42             }
43             else{
44                 cout<<"+2(";
45                 f(i);
46                 cout<<")";
47             }
48         }
49         
50     }
51     
52     if(1==a[2]){
53         if(first){
54             cout<<"2(2)";
55             first=0;
56         }
57         else{
58             cout<<"+2(2)";
59         }
60     }
61     if(1==a[1]){
62         if(first){
63             cout<<"2";
64             first=0;
65         }
66         else{
67             cout<<"+2";
68         }
69     }
70     if(1==a[0]){
71         if(first){
72             cout<<"2(0)";
73             first=0;
74         }
75         else{
76             cout<<"+2(0)";
77         }
78     }
79 }
80 int main(){
81     int n;
82     cin>>n; 
83     f(n);
84     cout<<endl;
85     return 0;
86 }

 

递归--练习9--noi8758 2的幂次方表示