题目描述
每个正数都可以用指数形式表示。
例如,137=27+23+20。
让我们用 a(b) 来表示 ab。
那么 137 可以表示为 2(7)+2(3)+2(0)。
因为 7=22+2+20,3=2+20,所以 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)
算法1
(dfs) $O()$
刚开始写得不简洁。y总讲了以后,确实可以很简洁
时间复杂度
参考文献
python3 代码
nums = []
while True:
try:
nums.append(int(input()))
except:
break
def dfs(n: int) -> str:
res = ""
for i in range(14, -1, -1):
if (n >> i) & 1:
if len(res) > 0:
res += "+"
if i == 0:
res += "2(0)"
if i == 1:
res += "2"
else:
res += "2(" + dfs(i) + ")"
return res
for x in nums:
print(dfs(x))
C++ 代码
#include<bits/stdc++.h>
using namespace std;
string dfs(int n)
{
string res = "";
for (int i = 14; i > -1; i --)
{
if ((n >> i) & 1)
{
if (res.size())
res += "+";
if (i == 0)
res += "2(0)";
else if (i == 1)
res += "2";
else
res += "2(" + dfs(i) + ")";
}
}
return res;
}
int main()
{
int n;
while (cin >> n)
cout << dfs(n) << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla