首页 > 代码库 > 递归--练习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的幂次方表示
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。