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

一、心得

找准子问题就好

二、题目

8758:2的幂次方表示

总时间限制:

1000ms

内存限制:

65536kB

描述

任何一个正整数都可以用2的幂次方表示。例如：

137=2⁷+2³+2⁰

同时约定方次用括号来表示，即a^b可表示为a(b)。由此可知，137可表示为：

2(7)+2(3)+2(0)

进一步：7=2²+2+2⁰（2¹用2表示）

3=2+2⁰

所以最后137可表示为：

2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如：

1315=2¹⁰+2⁸+2⁵+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表示（在表示中不能有空格）。

样例输入

样例输出

2(2(2)+2+2(0))+2(2+2(0))+2(0)

来源

NOIP1998复赛普及组第一题

三、AC代码

1 /* 2 noi8758 2的幂次方表示 3  4 找准子问题就好  5 */ 6 #include 
     
       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<
      
       <<" ";21         if((i+1)%5==0){22             cout<
       
        =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<