AcWing_3483_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$,$3=2+2^0$,所以 $137$ 最终可以表示为 $2(2(2)+2+2(0))+2(2+2(0))+2(0)$。
给定一个正数 $n$,请你将 $n$ 表示为只包含 $0$ 和 $2$ 的指数形式。
输入格式
输入包含多组数据。
每组数据占一行,一个正数 $n$。
输出格式
每组数据输出一行,一个指数形式表示。
数据范围
$1≤n≤20000$,
每个输入最多包含 $100$ 组数据。
输入样例:
1315
输出样例:
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
题目大意:
将一个正整数 $n$ 表示为只包含 $0$ 和 $2$ 的指数形式。所以在递归的时候,要特别注意 $2$ 和 $0$ 的打印。注意到 $n$ 最大到 $20000$ ,所以 遍历 $n$ 对应二进制数的每一位时的范围可以大致看成 $0-15$ ,用位运算实现。
注意'+'
以及\n
。
在第一版代码中,递归函数返回类型为void
,不能将cout<<endl
很好地结合起来。第二版,使用容器string
作为返回类型。
第一版,包括第二版,都没有好好考虑什么时候才会输出 $0$ ,实际上,我们不会去特意输出 $0$ ,可能表达的不太准确,实际上,我们只有输出 $1$ 的时候才会输出相应的 $2(0)$ ,在其他时候我们并不输出 $0$ (题目 $1≤n≤20000$ ,不必考虑 $n=0$)。也就是说我们是在输出时,真正需要考虑的是 $1$ 和 $2$ 的指数形式。
对于'+'
只要判断容器之前是否存有字符串,即可判断输出。
初始代码:
#include <iostream>
using namespace std;
void print(int n)
{
if (n == 2)
{
cout << '2';
return;
}
if (n == 0)
{
cout << '0';
return;
}
int cnt, i;
for (cnt = i = 0; i < 31; i++)
cnt += (n >> i) & 1; //需要递归的个数
for (i = 30; i >= 0; i--)
if ((n >> i) & 1)
{
cnt--;
if (i != 1)
{
cout << "2(";
print(i);
cout << ')';
}
else //特判2
cout << '2';
if (cnt > 0) //在最后一个递归打印前,都有'+'
putchar('+');
if (cnt == 0)
break;
}
}
int main()
{
int n;
int i, j, k;
while (cin >> n)
{
print(n);
cout << endl;
}
return 0;
}
修改代码:
#include <iostream>
#include <cstring>
using namespace std;
string dfs(int n)
{
string res;
for (int i = 15; i >= 0; i--)
if (n >> i & 1)
{
if (res.length())
res += '+';
if (!i)
res += "2(0)";
else if (i != 1)
res += "2(" + dfs(i) + ')';
else
res += '2';
}
return res;
}
int main()
{
int n;
while (cin >> n)
cout << dfs(n) << endl;
return 0;
}