历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

蓝桥杯第一讲：递归与递推

作者：

Snowing , 2022-02-07 21:34:28 , 所有人可见 , 阅读 368

2

1

递推与递归

递归是将大问题分解为小问题解决，是自上而下的；递推是从小问题着手，逐步解决大问题，是自下而上的。

关于DFS，最重要的是顺序，可以考虑画个递归树理清楚顺序之后再做
指数型枚举
排列型枚举
组合型枚举
基于二进制枚举状态

1.递归实现指数型枚举

一共有n个位置，每个位置可以放，也可以不妨，共$2^n$种方案

//递归实现指数型枚举
#include<bits/stdc++.h>

using namespace std;

const int N = 20;

int n;
bool st[N];

void dfs(int u)
{
    if(u == n + 1) 
    {
        for(int i = 1; i <= n; i++)
            if(st[i]) cout << i << " ";
        cout << endl;

        return;
    }

    st[u] = true;
    dfs(u + 1);
    st[u] = false;

    dfs(u + 1);
}

int main()
{
    cin >> n;

    //一共有n个位置，从第1个位置开始放
    dfs(1);

    return 0;
}

2.递归实现排列型枚举

一共有$n$个位置，要放$n$个数字，每个位置肯定要放，用一个st数组记录每个数字是否被使用

//递归实现排列型枚举
#include<bits/stdc++.h>

using namespace std;

const int N = 15;

int n;
int path[N];
bool st[N];

void dfs(int u)
{
    if(u == n + 1)
    {
        for(int i = 1; i <= n; i++)
            cout << path[i] << " ";
        cout << endl;

        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n;

    dfs(1);

    return 0;
}

3. 递归实现组合型枚举

一共n个数字，有m个位置。

和排列型枚举的区别有两点

位置有m个，不是n个
不考虑顺序（不妨人为规定从小到大枚举）

//递归实现组合型枚举
#include<bits/stdc++.h>

using namespace std;

const int N = 30;

int n, m;
int path[N];
bool st[N];

void dfs(int u)
{
    //与排列型区别1
    if(u == m + 1) 
    {
        for(int i = 1; i <= m; i++)
            cout << path[i] << " ";
        cout << endl;

        return;
    }

    //区别2:枚举起点不是1
    for(int i = path[u - 1] + 1; i <= n; i++)
    {
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n >> m;

    dfs(1);

    return 0;
}

4.n-皇后问题

按行枚举
枚举每个格子放不放（比较原始）

按行DFS

//n皇后
//按行DFS
#include<bits/stdc++.h>

using namespace std;

const int N = 20;

int n;
char g[N][N];

bool col[N], dg[N], udg[N];

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
                cout << g[i][j];
            cout << endl;
        }
        cout << endl;

        return;
    }

    for(int i = 0; i < n; i++)
    {
        if(!col[i] && !dg[u - i + n] && !udg[u + i])
        {
            col[i] = dg[u - i + n] = udg[u + i] = true;
            g[u][i] = 'Q';
            dfs(u + 1);
            col[i] = dg[u - i + n] = udg[u +i] = false;
            g[u][i] = '.';
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            g[i][j] = '.';
    }

    dfs(0);

    return 0;
}

DFS每个位置

注意这里要使用一个变量s来存储DFS过程中已经填充了多少皇后，用来判断是否成立。

注意：不是x==n就代表找到了一个方案，而必须恰好放置了n个皇后，即s==n

//n-皇后问题
//DFS每个位置
#include<bits/stdc++.h>

using namespace std;

const int N = 30;

int n;
char g[N][N];

bool col[N], row[N], dg[N], udg[N];

void dfs(int x, int y, int s)
{
    if(s > n) return;

    if(y == n) y = 0, x++;

    if(x == n)
    {
        if(s == n)
        {
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    cout << g[i][j];
                }
                cout << endl;
            }
            cout << endl;
        }
        return;
    }

    if(!row[x] && !col[y] && !dg[y - x + n] && !udg[x + y])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[y - x + n] = udg[x + y] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[y - x + n] = udg[x + y] = false;
        g[x][y] = '.';
    }

    dfs(x, y + 1, s);
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            g[i][j] = '.';

    dfs(0, 0, 0);

    return 0;
}

5.简单斐波那契

斐波那契数列可以使用递归或者递推的方法求解

递归可以用记忆化搜索优化
递推其实本质上就是动态规划

1.递归

//简单斐波那契数列递归求解
#include<bits/stdc++.h>

using namespace std;

const int N = 50;
int f[N];

int foo(int x)
{
    if(f[x] != 0) return f[x];
    if(x == 1) f[x] = 0;
    else if(x == 2) f[x] = 1;
    else f[x] = foo(x - 1) + foo(x - 2);

    return f[x];
}

int main()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        cout << foo(i) << " ";
    cout << endl;

    return 0;
}

2.递推

//简单斐波那契数列递推求解
#include<bits/stdc++.h>

using namespace std;

const int N = 50;

int n;

int main()
{
    cin >> n;

    int a = 0, b = 1;//f(1),f(2)
    for(int i = 1; i <= n; i++)
    {
        cout << a << " ";
        int fn = a + b;
        a = b;
        b = fn;
    }

    cout << endl;
    return 0;
}

6.费解的开关

使用二进制枚举第一行的改变状态，之后的每一行便都被唯一确定，只需要检查最后一行即可。

==每尝试一种方案前，记得备份g，尝试完，记得还原==

//费解的开关 二进制枚举
#include<bits/stdc++.h>

using namespace std;

const int N = 10;

char g[N][N], backup[N][N];

int dx[5] = {-1,0,1,0,0}, dy[5] = {0,1,0,-1,0};
void turn(int x, int y)
{
    for(int i = 0; i < 5; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;

        g[a][b] = '0' + '1' - g[a][b];
    }
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        for(int i = 0; i < 5; i++) cin >> g[i];

        int res = 10;
        for(int op = 0; op < 32; op++)
        {
            memcpy(backup, g, sizeof g);//一定要记得备份！不然后果很惨啊

            int step = 0;

            for(int i = 0; i < 5; i++)
            {
                int x = op >> i & 1;
                if(x == 1)
                {
                    turn(0, i);
                    step++;
                }
            }

            for(int i = 1; i < 5; i++)
            {
                for(int j = 0; j < 5; j++)
                {
                    if(g[i - 1][j] == '0')
                    {
                        turn(i, j);
                        step++;
                    }
                }
            }

            bool flag = true;
            for(int i = 0; i < 5; i++)
            {
                if(g[4][i] == '0') flag = false;
            }

            if(flag)
            {
                res = min(step, res);
            }

            memcpy(g, backup, sizeof g);
        }

        if(res > 6) res = -1;
        cout << res << endl;
    }

    return 0;
}

7.翻硬币

超级简化版的开灯问题，直接判断第一个状态，然后后面的依次递推即可

//翻硬币
#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
string s, t;

void turn(int x)
{
    s[x] = 'o' + '*' - s[x];
    s[x - 1] = 'o' + '*' - s[x - 1];
}

int main()
{
    cin >> s >> t;
    n = s.size();

    int res = 0;

    for(int i = 0; i < n - 1; i++)
    {
        if(s[i] != t[i]) 
        {
            turn(i + 1);
            res++;
        }
    }

    cout << res << endl;

    return 0;
}

8.飞行员兄弟

这道题目，真的很暴力！不过因为数据范围不大，是可以过掉的。枚举有一下两种方式：

二进制枚举
DFS枚举

二进制枚举

//飞行员兄弟
//二进制枚举
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 10;

char g[N][N], backup[N][N];

void turn_one(int x, int y)
{
    g[x][y] = '+' + '-' - g[x][y];
}

void turn(int x, int y)
{
    turn_one(x, y);
    for(int i = 0; i < 4; i++)
    {
        turn_one(i, y);
        turn_one(x, i);
    }
}

int main()
{
    for(int i = 0; i < 4; i++) cin >> g[i];

    int res = 20;
    vector<PII> vec;

    for(int op = 0; op < 1 << 16; op++)
    {
        memcpy(backup, g, sizeof g);

        int step = 0;
        vector<PII> tmp;

        for(int i = 0; i < 16; i++)
        {
            int x = op >> i & 1;
            if(x == 1)
            {
                turn(i / 4, i % 4);
                tmp.push_back({i / 4, i % 4});
                step++;
            }
        }

        bool flag = true;
        for(int i = 0; i < 4; i++)
        {
            for(int j = 0; j < 4; j++)
            {
                if(g[i][j] == '+') flag = false;
            }
        }
        if(flag)
        {
            if(step < res)
            {
                res = step;
                vec = tmp;
            }
        }

        memcpy(g, backup, sizeof g);
    }

    cout << res << endl;
    for(auto x : vec)
        cout << x.first + 1 << " " << x.second + 1 << endl;

    return 0;
}

DFS枚举

在递归出口处理完逻辑后一定不要忘记return这句话，血泪😰

//飞行员兄弟
//DFS枚举
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 20;

char g[N][N];

int res = 100;
vector<PII> vec;

void turn_one(int x, int y)
{
    g[x][y] = '+' + '-' - g[x][y];
}

void turn(int x, int y)
{
    turn_one(x, y);
    for(int i = 0; i < 4; i++)
    {
        turn_one(i, y);
        turn_one(x, i);
    }
}

void dfs(int x, int y, int step, vector<PII> record)
{
    if(y == 4) y = 0, x++;

    if(x == 4)
    {
        bool flag = true;
        for(int i = 0; i < 4; i++)
        {
            for(int j = 0; j < 4; j++)
            {
                if(g[i][j] == '+') flag = false;
            }
        }
        if(flag)
        {
            if(step < res)
            {
                res = step;
                vec = record;
            }
        }
        return;//一定不要忘记写，虽然它很小，不然会SF
    }

    turn(x, y);
    record.push_back({x, y});
    dfs(x, y + 1, step + 1, record);
    turn(x, y);
    record.pop_back();

    dfs(x, y + 1, step, record);

}

int main()
{
    for(int i = 0; i < 4; i++) cin >> g[i];

    dfs(0, 0, 0, vec);

    cout << res << endl;
    for(auto x : vec) 
        cout << x.first + 1 << " " << x.second + 1 << endl;

    return 0;
}

9.带分数

这道题目更加暴力了

做法1：直接枚举1~9的全排列，然后分成三份，对每种情况进行计算判断
做法2：双重DFS枚举a和c，然后计算出来b，进行判断

枚举全排列做法

//带分数
//枚举所有的全排列
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 20;

int n;
int path[N];
bool st[N];

int res = 0;

int get(int l, int r)
{
    int res = 0;
    for(int i = l; i <= r; i++) res = res * 10 + path[i];
    return res;
}

bool check(int a, int b, int c)
{
    if(a == 0 || b == 0 || c == 0) return false;

    if(n * c != a * c + b) return false;

    return true;
}
void dfs(int u)
{
    if(u == 10)
    {
        //拆分成三分
        //[1,i], [i+1,j], [j+1,9]
        for(int i = 1; i <= 7; i++)
        {
            for(int j = i + 1; j <= 8; j++)
            {
                int a = get(1, i), b = get(i + 1, j), c = get(j + 1, 9);

                if(check(a, b, c)) res++;
            }
        }
    }

    for(int i = 1; i <= 9; i++)
    {
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n;

    dfs(1);

    cout << res << endl;

    return 0;
}

双重DFS枚举做法

//带分数
//双重DFS
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 20;

int n;
bool st[N], backup[N];

int res = 0;

bool check(int a, int c)
{
    LL b = n * (LL)c - (LL)a * c;//n*c可能爆int

    if(a == 0 || b == 0 || c == 0) return false;

    memcpy(backup, st, sizeof st);

    while(b)
    {
        int x = b % 10;
        b /= 10;
        if(x == 0 || backup[x]) return false;
        backup[x] = true;
    }

    for(int i = 1; i <= 9; i++)
    {
        if(backup[i] == false) return false;
    }

    return true;
}

void dfs_c(int u, int a, int c)
{
    if(u == 10) return;

    if(check(a, c)) res++;

    for(int i = 1; i <= 9; i++)
    {
        if(!st[i])
        {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            st[i] = false;
        }
    }
}

void dfs_a(int u, int a)
{
    if(u == 10) return;//直接return

    //对每一个dfs_a,都要dfs_c一下
    dfs_c(u, a, 0);

    for(int i = 1; i <= 9; i++)
    {
        if(!st[i])
        {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);
            st[i] = false;
        }
    }
}

int main()
{
    cin >> n;

    dfs_a(1, 0);

    cout << res << endl;

    return 0;
}

0 评论

App 内打开