[NOIP1998 普及组] 幂次方
题目描述
任何一个正整数都可以用 $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$ 的 $0, 2$ 表示(在表示中不能有空格)。
样例 #1
样例输入 #1
1315
样例输出 #1
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
提示
【数据范围】
对于 $100\%$ 的数据,$1 \le n \le 2 \times {10}^4$。
NOIP1998 普及组 第三题
题解:
思路:定义一个power(int k)
,作用是把k分解成2的幂次方相加的形式
可以想到这就是十进制数换二进制的表达,例如$137_{(10)} = 10001001_{(2)}$,可以看到1分别位于第8,4,1位,对应的分解就是$2(7)+2(3)+2(0)$,然而这里还需要对7,3进行进一步的拆分
而对于$k = 1, k = 2, k = 3$,可以发现他们的二进制表达分别是$01, 10, 11$,对应的拆分是$2(0), 2, 2 + 2(0)$,这三个可以作为基准情况单独处理,也就是低2位,一旦1在第3位以上,就需要递归处理,即$k\geq4$
对于十进制转二进制,利用k >> i & 1
就可以检查k的第i + 1位二进制数是不是1了
还有一个是加号的处理,对于一个分解,例如上面的例子$2(7)+2(3)+2(0)$,显然$2(0)$后面是不需要加号的,即只有当输出的不是最低位的1时,才输出加号,这一点可以用lowbit函数来实现,它能找出最低位1代表的十进制数
#include <bits/stdc++.h>
using namespace std;
int lowbit(int x) //给出x最低位的1的十进制值
{
return x & -x;
}
void power(int k) //对k进行2的幂次方和分解
{
if (k == 2)
{
cout << "2";
return;
}
else
{
for (int i = 14; i >= 0; i--)//找出k的二进制表达的所有1的位置,而15位2进制就足以表达2万以内的数
{
if (k >> i & 1)//找出第i位1
{
if (i == 1) //即k=2的情况,直接输出2
{
cout << "2";
}
else if (i == 0) //即k=1的情况,直接输出2(0)
{
cout << "2(0)";
}
else //i >= 1,即k>=4的情况才进行递归求解
{
cout << "2("; //当k>=4时,结果一定是包含在2()内的,所以可以先后输出2和括号
power(i);
cout << ")";
}
if (lowbit(k) != pow(2, i)) //当i不是最低位的1时,才输出加号
{
cout << "+";
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
power(n);
return 0;
}