递归分治

一、思想

二、例题

P1010洛谷

image-20211126183421783

三、解题思路

我们很容易发现该题目符合递归思想，将大问题分解成小问题，分解到可以直接解决的时候进行终止

  • 原本的思路：从左端开始遍历即通过位运算将各个位置进行遍历，关键在于对”()”和”+”的处理，括号只在i = 1 的时候是没有的，对于”+”的处理，我将采用在每个后面都加上”+”,最后进行特殊判断，将最末尾的”+”进行删除就OK
  • 改进思路，我们知道”+”只在最后面不能存在，所以我们从后开始遍历，新的答案将加在前面，在当前ans==””时候，我们不加”+”，同时我们从右往左遍历，可以减少遍历次数，同时，将采用do while结构，可以至少进行一次操作。

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
string add(int n, string ans) {
    if (n == 0) {
        return "0";
    } else if (n == 2) {
        return "2";
    } else {
        for (int i = 20; i >= 0; i--) {
            if (n & (1 << i)) {
                //cout << i << endl;
                if (i != 1)
                    ans = ans + "2" + "(" + add(i, "") + ")";
                else
                    ans += "2";
                if (i != 0)
                    ans += "+";
            }
        }
        return ans[ans.length()-1] == '+' ?
            ans.substr(0,ans.length()-1):ans;
    }
}
int main() {
    int num;cin >> num;
    cout << add(num, "");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
string run(int x, int i = 0, string s = string("")) {
    if (x == 0)
        return string("0");
    do
        if (x & 1)
            s = (i == 1 ? "2" : "2(" + run(i) + ")") + (s == "" ? "" : "+") + s; 
    while (++i, x >>= 1);
    return s;
}
int main() {
    int x;
    cin >> x;
    cout << run(x) << endl;
}