课上实例1

#include <iostream>

using namespace std;

int f(int n)
{
    // 边界 
    if (n == 1) return 1;   // 如果n等于1,返回1 
    if (n == 2) return 2;   // 如果n等于2,返回2

    // 否则返回f(n-1)+f(n-2)    
    return f(n - 1) + f(n - 2); 
}

int main()
{
    // 输入一个n 
    int n;
    cin >> n;

    // 返回斐波那契数列第n项 
    cout << f(n) << endl;

    return 0;
}

课上实例2

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

// 定义一个数据范围,N最大到15
// 又因为让下标从1开始,因此N=16 
const int N = 16;

int n;
// 定义一个数组记录每个位置的状态
int st[N];  // 状态,记录每个位置当前的状态:0表示还没考虑,1表示选它,2表示不选它

// st是全局数组,因此不用传参 
void dfs(int u)
{
    // u表示当前枚举到第几位
    // 首先判断边界
    // 当已经枚举完最后一个位置时已经到边界
    // 枚举完u后u会往后挪一位
    // 当u>n时就到达边界 
    if (u > n)
    {
        // 在return之前将方案输出
        // 遍历每一位,查看每一位有没有被选
        for (int i = 1; i <= n; i ++ )
            // 如果当前位置的状态为1表示被选
            if (st[i] == 1)
                // 将其输出 
                printf("%d ", i);
        // 输完方案后输出回车 
        printf("\n");
        // 在边界不能再递归了,需return 
        return;
    }

    // 分支的处理 
    // 在一个结点,分为两种情况做
    // 第一种情况:不选
    st[u] = 2;
    // 递归到下一个位置
    dfs(u + 1);     // 第一个分支:不选
    // 递归结束向上回溯到父结点时
    // 父结点该位的状态应恢复为"还没考虑" 
    // 以便父结点向其它分支递归
    // 本题不需要恢复现场,因为递归时会马上被下面的语句覆盖 
    st[u] = 0;      // 恢复现场

    // 第二种情况:选
    st[u] = 1;
    dfs(u + 1);     // 第二个分支:选 
    st[u] = 0;      // 恢复现场 
}

int main()
{
    // 读入一个n
    cin >> n;

    // 使下标从1开始 
    // 从第一位开始做
    dfs(1);

    return 0;
}

课上实例3

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 16;

int n;
int st[N];

// 保存答案
// 因为每种方案中选择的数不一定等于n,用数组存放不选的位置为0
// 因此输出时不选的位置输出0 
// 故用vector存放
// 当然用数组记录方案也可以在输出时加一个判断,为0时不输出
// 用vector记录方案比直接输出要慢一些 
vector<vector<int>> ways;  

void dfs(int u)
{
    if (u > n)
    {
        // 每次定义一个当前的方案 
        vector<int> way;
        for (int i = 1; i <= n; i ++ )  // 记录方案
            // 如果当前位置的状态为'选' 
            if (st[i] == 1)
                // 则将该数push_back到当前方案中 
                way.push_back(i); 
        // 最终将way放到ways中 
        ways.push_back(way);
        return;
    }

    st[u] = 2;
    dfs(u + 1);
    st[u] = 0; 

    st[u] = 1;
    dfs(u + 1);
    st[u] = 0;
}

int main()
{
    cin >> n;

    dfs(1);

    // 将记录下的方案输出
    for (int i = 0; i < ways.size(); i ++ )
    {
        for (int j = 0; j < ways[i].size(); j ++ ) printf("%d ", ways[i][j]);
        // 回车的简写方式
        // puts()输出字符串+回车
        // 此时字符串为空,因此只输出回车 
        puts("");   
    } 

    return 0;
}

课上实例4

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

// n最大为9
// 让下标从1开始,因此开10 
const int N = 10;

// 变量如果定义为全局变量,初值一定为0
// 如果定义为局部变量,初值为随机值
int n;

// 存放当前状态
int state[N];   // 0表示还没放数,1~n表示放了哪个数
// 存放当前哪个数没被用过
bool used[N];   // true表示用过,false表示还未用过

// state[]和used[]为全局数组,不需要传参 
void dfs(int u)
{
    // 已经枚举完所有位
    if (u > n)  // 边界
    {
        // 打印方案
        for (int i = 1; i <= n; i ++ ) printf("%d ", state[i]); 
        puts("");

        return;
    }

    // 依次枚举每个分支,即当前位置可以填哪些数
    // 从小到大枚举 
    for (int i = 1; i <= n; i ++ )
        // 如果当前数还未使用
        // 说明当前位置可以放该数 
        if (!used[i])
        {
            // 将这一位填上该数
            state[u] = i;
            // 更改数的状态为已被使用
            used[i] = true;
            // 递归到下一结点处理
            dfs(u + 1);

            // 恢复现场
            state[u] = 0;
            used[i] = false;
        }
}

int main()
{
    scanf("%d", &n);

    // 当前枚举到第几位
    // 因数组为全局变量,不需写到参数中
    dfs(1);

    return 0;
}