枚举
#include <iostream>
using namespace std;
void dfs(int n, string& res)
{
bool flag = false;
for (int i = 14; i >= 0; i -- )
if (n >> i & 1)
{
if (flag) res += '+';
flag = true;
if (!i) res += "2(0)";
else if (i == 1) res += "2";
else res += "2(", dfs(i,res), res += ")";
}
}
int main()
{
int n;
while (cin >> n) {
string res; dfs(n,res);
cout << res << endl;
}
return 0;
}
非枚举通用做法:
正常来说可以从高位枚举到低位,但是在位数不确定的情况下,可以用栈+递归
C++ 代码
#include <iostream>
#include <stack>
using namespace std;
void dfs(int n, string& ans) {
if(n <= 0) return;
int m = 0, k = 1;
stack<pair<int,int>> stk;
while(n > 0) {
if(n&1) stk.push({m,k});
m++; n >>= 1; k <<= 1;
}
bool flag = false;
while(stk.size()) {
auto p = stk.top(); stk.pop();
int t = p.first, x = p.second;
if(flag) ans += "+";
flag = true;
if(x == 2) ans += "2";
else if(x == 1) ans += "2(0)";
else ans += "2(", dfs(t,ans), ans += ")";
}
}
int main(void) {
int n;
while(scanf("%d", &n) == 1) {
string ans; dfs(n,ans);
cout << ans << endl;
}
return 0;
}