3.找出n个自然数（1，2，3，…，n）中取r个数的组合。采用分治策略，写出相应问题的递归算法及c程序。

好的，这是一个经典的组合问题，可以采用递归和分治的思想来解决。以下是递归算法的伪代码：

void combination(int n, int r, int index, vector<int>& temp, vector<vector<int>>& res) {
    if (temp.size() == r) {  // 达到指定的组合长度
        res.push_back(temp);  // 存储当前组合
        return;
    }
    for (int i = index; i <= n; i++) {  // 枚举当前位置的数字
        temp.push_back(i);  // 添加当前数字到组合中
        combination(n, r, i+1, temp, res);  // 递归下一个数字的组合
        temp.pop_back();  // 回溯，移除当前数字
    }
}

接下来是C++的实现代码：

#include <iostream>
#include <vector>
using namespace std;

void combination(int n, int r, int index, vector<int>& temp, vector<vector<int>>& res) {
    if (temp.size() == r) {
        res.push_back(temp);
        return;
    }
    for (int i = index; i <= n; i++) {
        temp.push_back(i);
        combination(n, r, i+1, temp, res);
        temp.pop_back();
    }
}

int main() {
    int n = 5, r = 3;
    vector<int> temp;
    vector<vector<int>> res;
    combination(n, r, 1, temp, res);
    for (auto comb : res) {
        for (auto num : comb) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

输出结果为：

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

其中，`res`存储了所有符合要求的组合，可以根据需要进行处理。