王道机试指南8递归分治

例题8.1n的阶乘（清华复试上机）

#include<iostream>
#include<cstdio>
using namespace std;
long long func(int n){
    if(n == 0) return 1;
    else{
        return n * func(n - 1);
    }
}
int main(){
    int n;
    while(cin >> n){
        cout << func(n) << endl;
    }
    return 0;
}  

习题8.1杨辉三角（西北工业大学上机）

#include<iostream>
#include<cstdio>
using namespace std;
int YangHui(int i, int j){
    if(j == 1) return 1;
    else if(i == j) return 1;
    else return YangHui(i-1, j-1) + YangHui(i-1, j);
}
int main(){
    int n;
    while(cin >> n){
        int a[n][n];
        for(int i = 2;i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(j <= i) cout << YangHui(i, j) << " ";
            }
            cout << endl;
        }
    }
    
    return 0;
}  

习题8.2全排列（北京大学上机）

使用dfs来进行全排列

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

string str;
string res;
bool used[6];

void Dfs(int cur)
{
    if (cur == str.length())
    {
        cout << res << endl;
        return;
    }
    for (int i = 0; i < str.length(); ++i)
    {
        if (!used[i])
        {
            //放入
            used[i] = true;
            res[cur] = str[i];
            Dfs(cur + 1);
            used[i] = false;
        }
    }
}

int main()
{
    while (cin >> str)
    {
        sort(str.begin(), str.end());
        res = str;
        memset(used, false, sizeof(used));
        Dfs(0);
        cout << endl;
    }
}

例题8.3Fibonacci（上海交通大学上机）

#include<iostream>
#include<cstdio>
using namespace std;
int fib(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}
int main(){
    int n;
    while(cin >> n){
        cout << fib(n) << endl;
    }
    return 0;
}  
 

例题8.4（北京大学复试上机）

#include<iostream>
#include<cstdio>
using namespace std;
int m, n;
int count = 0;
int func(int m, int n){
    if(m > n){
        return 0;
    }else{
        return 1 + func(2 * m, n) + func(2 * m + 1, n);
    }
    
}
int main(){
    while(cin >> m >> n){
        cout << func(m, n) << endl;
    }
    return 0;
}  

习题8.3 2的幂次方（上海交通大学上机）

#include<iostream>
#include<cstdio>
#include<string>
#include<stack>
#include<vector> 
#include<cmath>
using namespace std;

void func(int n){
    vector<int> v;
    //转换为二进制
    while(n != 0){
        v.push_back(n % 2 );
        n /= 2;
    }
    bool first = true;//判断是不是输出“+”，除了第一个外，其他输出前都要输出“+”
    for(int i = v.size() - 1; i >= 0; i--){//循环内隐含了递归边界
        if(v[i] == 1){
            if(!first){
                cout << "+";
            }
            first = false;
            //如果是0或1位直接输出，不是0或1则递归调用
            if(i == 0){
                cout << "2(0)";
            }
            else if(i == 1){
                cout << "2";
            }
            else{
                cout << "2(";
                func(i);
                cout << ")";
            }
        }
        
    }
}
int main(){
    int n;
    while(cin >> n){
        func(n);
        cout << endl;
    }
    return 0;
}