华师一附中OI组

标题: P1010 幂次方 [打印本页]

---

作者: admin    时间: 2018-5-3 11:28
标题: P1010 幂次方
https://www.luogu.org/problemnew/show/P1010

题目描述
任何一个正整数都可以用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(n≤20000)。

输出格式：
符合约定的n的0，2表示(在表示中不能有空格)

输入输出样例
输入样例#1：
1315
输出样例#1：
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

---

作者: admin    时间: 2018-5-3 13:46
沙发

1. 
   
2. #include<iostream>
   
3. using namespace std;
   
4. void ms(int x)
   
5. {
   
6.     ///求出x=2^m+n的m和n
   
7.     int m=0,n=0,s=1;
   
8.     while (x>=s){s=s*2;m++;} ///越过后再回头是一种做法
   
9.     m--;s=s/2;
   
10.     n=x-s;
    
11.     ///分情况递归
    
12.     if (m==0) cout<<"2(0)";
    
13.     else if (m==1) cout<<"2";
    
14.     else
    
15.     {
    
16.         cout<<"2(";
    
17.         ms(m);  ///递归
    
18.         cout<<")";
    
19.     }
    
20. 
    
21.     if (n>0)
    
22.     {
    
23.         cout<<'+';    ///分解剩下的那个小尾巴
    
24.         ms(n);
    
25.     }
    
26. }
    
27. int main()
    
28. {
    
29.     for (int x=1; x<=20; x++)
    
30.     {
    
31.         ms(x);
    
32.         cout<<endl;
    
33.     }
    
34.     return 0;
    
35. }
    
36. 
    
37. 
    

复制代码

---

作者: admin    时间: 2018-5-5 19:39
做题过程：
经过分析，每个数字x都可以分解成2^m+n的唯一形式，因为要求m最大。然后递归就是
主程序
void  ms(int x)
{
   分解出m和n
   再递归  m=0,1 无法递归。
   n=0不需要递归
}
写出这一段的框架备用

---

作者: admin    时间: 2018-5-5 19:42
怎么求出m呢？仿照s=1+2+4+7+***的那个题，就是求出2^m<=x的最大m
一种常规做法。不断的乘，直到大于，然后减1。
while (x>=s){s=s*2;m++;} ///越过后再回头是一种做法
    m--;s=s/2;
n就是x-2^m
这段代码填入

---

作者: admin    时间: 2018-5-5 19:43
拼凑出程序，还要自己检查，这个很好办，自己运行x=1--100，手动检查若无问题，即做法正确。

---

作者: admin    时间: 2018-5-5 19:47
当然，有创新者，发现N<=20000，意思就是不会超过2^15，于是打个1-2^15的表，然后查表的结果，这也是做法之一，就不吐代码了。

1. #include <iostream>
   
2. using namespace std;
   
3. string s[16];
   
4. int i,x,a[16];
   
5. int main()
   
6. {
   
7.     ///这也太搞笑了吧！！！
   
8.     s[0]="2(0)";       ///1
   
9.     s[1]="2";          ///2
   
10.     s[2]="2(2)";       ///4
    
11.     s[3]="2(2+2(0))";   ///8
    
12.     s[4]="2(2(2))";
    
13.     s[5]="2(2(2)+2(0))";
    
14.     s[6]="2(2(2)+2)";
    
15.     s[7]="2(2(2)+2+2(0))";
    
16.     s[8]="2(2(2+2(0)))";
    
17.     s[9]="2(2(2+2(0))+2(0))";
    
18.     s[10]="2(2(2+2(0))+2)";
    
19.     s[11]="2(2(2+2(0))+2+2(0))";
    
20.     s[12]="2(2(2+2(0))+2(2))";
    
21.     s[13]="2(2(2+2(0))+2(2)+2(0))";
    
22.     s[14]="2(2(2+2(0))+2(2)+2)";
    
23.     cin>>x;
    
24.     i=0;
    
25.     while (x>0)
    
26.     {
    
27.         a[i]=x%2;
    
28.         x=x/2;
    
29.         i++;
    
30.     }
    
31.     i=15;
    
32.     while (a[i]==0) i--;
    
33.     cout<<s[i];
    
34.     i--;
    
35.     for (; i>=0; i--)
    
36.         if (a[i]==1) cout<<'+'<<s[i];
    
37.     return 0;
    
38. }
    

复制代码

---

作者: 倚窗倾听风吹雨    时间: 2018-7-4 20:09

1. #include<iostream>
   
2. using namespace std;
   
3. int i,n,s,a[20001]={},j=0;
   
4. int cf(int a,int b)
   
5. {
   
6.     int c=2;
   
7.     for(int x=2;x<=b;x++)c*=2;
   
8.     if(b==0)c=1;
   
9.     return c;
   
10. }
    
11. void kj(int e)
    
12. {
    
13.     int k=1,y;
    
14.     if(e==0)return;
    
15.     i=0;
    
16.     j++;
    
17.     do i++;
    
18.     while(cf(2,i)<=e);
    
19.     y=--i;
    
20.     a[j]=y;
    
21.     if(a[j]==0)cout<<"2(0)";
    
22.     if(a[j]==1)cout<<"2";
    
23.     if(a[j]>1)
    
24.     {
    
25.         cout<<"2(";
    
26.         kj(a[j]);
    
27.         cout<<")";
    
28.     }
    
29.     if(e!=cf(2,y))
    
30.     {
    
31.         cout<<"+";
    
32.         kj(e-cf(2,y));
    
33.     }
    
34. }
    
35. int main()
    
36. {
    
37.     cin>>n;
    
38.     kj(n);
    
39. }

复制代码

---

作者: universehyf    时间: 2018-11-24 17:53

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cmath>
   
4. using namespace std;
   
5. #define FOR(i,a,b) for(register int i=a;i<=b;++i)
   
6. #define For(i,a,b) for(register int i=a;i>=b;--i)
   
7. void dg(int x)
   
8. {
   
9.     if(x==0) {cout<<0;return;}
   
10.     if(x==2) {cout<<2;return;}
    
11.     int logg=floor(log(x)*1.00/log(2.00));
    
12.     ///cout<<endl<<x<<" "<<logg<<endl;
    
13.     bool flag=0;
    
14.     For(i,logg,0) if((1<<i)&x)
    
15.     {
    
16.         if(flag) cout<<"+";flag=1;
    
17.         if(i==1)cout<<"2";
    
18.         else{cout<<"2(";dg(i);cout<<")";}
    
19.     }
    
20. }
    
21. int main()
    
22. {
    
23.     int n;scanf("%d",&n);
    
24.     dg(n);return 0;
    
25. }

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2