Recursive Insert sort

递归解决，假设前n个已经排好序，当然，插入得时候可以二分插入。

#include <bits/stdc++.h>
using namespace std;

void recursive_insert_sort(int arr[], int n) {
    if (n > 1) {
        recursive_insert_sort(arr, n - 1);
        int tmp, i = n - 1;
        while (i >= 1 && arr[i] < arr[i - 1]) {
            tmp = arr[i];
            arr[i] = arr[i - 1];
            arr[i - 1] = tmp;
            i--;
            }
        }
}

int main() {
    int n, num[10];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &num[i]);
    recursive_insert_sort(num, n);
    for (int i = 0; i < n; i++) printf("%d ", num[i]);
    return 0;
}

Recursive Knapsack

递归求背包，前面都选择最优，然后最后一个选择当前价值最高。

#include <bits/stdc++.h>  
using namespace std;  

int recursive_knapsack(const vector<int>& w, const vector<int>& v, int index, int capacity) {  
    if (index < 0 || capacity <= 0) return 0;  

    int res = recursive_knapsack(w, v, index - 1, capacity);  
    if (w[index] < capacity) {  
        res = max(res, v[index] + recursive_knapsack(w, v, index - 1, capacity - w[index]));  
    }  
    return res;  
}  

int main() {  
    int n, C;  
    cin >> n >> C;  
    vector<int> w(n), v(n);  
    for (int i = 0; i < n; i++) cin >> w[i];  
    for (int i = 0; i < n; i++) cin >> v[i];  
    cout <<  "背包最大价值为" <<recursive_knapsack(w, v, n - 1, C) << endl;  
}

Recursive Fibonacci

公式模板

#include <bits/stdc++.h>
using namespace std;

int recursive_fibonacci(int n) {
    if (n <= 1) return n;
    return recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2);
}

int main() {
    int n;
    cin >> n;
    cout << recursive_fibonacci(n);
}

Recursive Hanoi

把n-1个从src移动到aux，那么剩下最大的直接放到dst，然后把aux上的n-1个放到dst就可以了。

#include <bits/stdc++.h>
using namespace std;

void recursive_hanoi(int n, char src, char aux, char dst) {
    // 如果只剩一个盘子，直接放过去
    if (n == 1) {
        printf("%d %c->%c\n", n, src, dst);
        return;
    }
    // 那n-1个盘子借助目标盘子放到辅助盘子上，这一就只剩一个了;
    recursive_hanoi(n - 1, src, dst, aux);
    // 只剩一个直接移动过去;
    printf("%d %c->%c\n", n, src, dst);
    // 然后把n-1个盘子放到目标盘子，就完成了
    recursive_hanoi(n - 1, aux, src, dst);
}

int main() {
    int n;
    cin >> n;
    recursive_hanoi(n, 'A', 'B', 'C');
    return 0;
}

Recursive Basic Calculator

这个题目并不复杂，下面的题解是粘过来的。
这里还是想说一下，这个思路的核心还是通过”()”前的符号来确定括号内的数字的符号，这样就变成了去括号的纯加减法。

#include <bits/stdc++.h>  
using namespace std;  

class Solution {  
public:  
    int calculate(string s) {  
        int ans = 0;  
        int num = 0;  
        int sign = 1;  
        stack<int> stack{{sign}};  

        for (const char c : s)  
            if (isdigit(c))  
                num = num * 10 + (c - '0');  
            else if (c == '(')  
                stack.push(sign);  
            else if (c == ')')  
                stack.pop();  
            else if (c == '+' || c == '-') {  
                ans += sign * num;  
                sign = (c == '+' ? 1 : -1) * stack.top();  
                num = 0;  
            }  

        return ans + sign * num;  
    }  
};  

int main() {  
    Solution test = *new Solution;  
    cout << test.calculate("(1+(4+5+2)-3)+(6+8)");  
}