蓝桥杯 ALGO-12 算法训练幂方分解

问题描述
任何一个正整数都可以用2的幂次方表示。例如：
137=27+23+20
同时约定方次用括号来表示，即ab 可表示为a（b）。
由此可知，137可表示为：
2（7）+2（3）+2（0）
进一步：7= 22+2+20 （21用2表示）
3=2+20
所以最后137可表示为：
2（2（2）+2+2（0））+2（2+2（0））+2（0）
又如：
1315=210 +28 +25 +2+1
所以1315最后可表示为：
2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
输入格式
输入包含一个正整数N（N<=20000），为要求分解的整数。
输出格式
程序输出包含一行字符串，为符合约定的n的0，2表示（在表示中不能有空格）

分析：递归即可，注意递归边界是1,返回"1"，最后输出的时候过滤掉即~

#include <iostream>
#include <vector>
using namespace std;
string dfs(int n) {
    if (n == 1) return "1";
    if (n == 0) return "0";
    string ans;
    vector<int> v;
    int cnt = 0;
    while (n) {
        if (n % 2 == 1) v.push_back(cnt);
        n /= 2;
        cnt++;
    }
    for (int i = v.size() - 1; i >= 0; i--) {
        ans += "2(" + dfs(v[i]) + ")";
        if (i != 0) ans += "+";
    }
    return ans;
}
int main() {
    int n;
    cin >> n;
    string ans = dfs(n);
    for (int i = 0; i < ans.size(); i++) {
        if (ans[i + 1] == '1') i += 3;
        cout << ans[i];
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

string dfs(int n) {

if (n == 1) return "1";

if (n == 0) return "0";

string ans;

vector<int> v;

int cnt = 0;

while (n) {

if (n % 2 == 1) v.push_back(cnt);

n /= 2;

cnt++;

}

for (int i = v.size() - 1; i >= 0; i--) {

ans += "2(" + dfs(v[i]) + ")";

if (i != 0) ans += "+";

}

return ans;

}

int main() {

int n;

cin >> n;

string ans = dfs(n);

for (int i = 0; i < ans.size(); i++) {

if (ans[i + 1] == '1') i += 3;

cout << ans[i];

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版