华师一附中OI组

标题: 2的幂分解（NOIP1998） [打印本页]
作者: diggersun    时间: 2015-10-31 23:54
标题: 2的幂分解（NOIP1998）
本帖最后由 diggersun 于 2015-11-1 00:05 编辑

任何一个正整数都可以用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    时间: 2015-11-1 00:03
这个题考虑用递归来做，那么递归有两个出口，一个是1，一个是2，其他的数字都可以化成2^X1+2^X2+2^X3+***的形式，



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2