• 蓝桥杯---第一讲 递归与递推

    文章目录

    前言

    本篇博客主要打卡记录博主学习蓝桥杯C++AB组辅导课的习题第一章节的题目。

    Ⅰ. 递归实现指数型枚举

    0x00 算法思路

    这一道题主要考查 dfs 算法，然后这一道题就是以位置来进行 搜索 当搜索到最后一个位置的时候就可以 收获结果 然后考虑枚举到的位置 可以选择 选 或者 不选

    0x00 代码书写

    #include

using namespace std;

const int N = 16;

int n;
int st[N]; // 状态，记录每个位置当前的状态：0表示还没考虑，1表示选，2表示不选 

void dfs(int u)
{
	if(u > n)
	{
		for(int i = 1 ; i <= n ; ++ i)
			if(st[i] == 1)
				cout << i << " ";
		cout << endl;
		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); //枚举第一个位置 
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    0x00 思考总结

    这一道题目 就是枚举每一个位置，然后进行选这个数字或者不选这个数字，当枚举到末尾的时候就可以进行收获(打印结果) —> 本质就是枚举每一个位置然后根据选或不选进行的排列组合

    Ⅱ. 递归实现排列型枚举

    0x00 算法思路

    利用一个判断数组st数组，检查是否这个位置的数字我已经使用过了，如果使用过了，就继续，如果没有就直接放到a数组里，递归下一个位置

    0x01代码书写

    #include

using namespace std;

const int N = 11;

int n;
int st[N];//记录这个数字是否被使用过false表示没有，true表示用过
int a[N];//存放数字 方便打印

void dfs(int u)
{
	if(u > n)//(u == n + 1)也是可以的表示枚举到最后一个位置
	{
		for(int i = 1 ; i <= n; ++ i)
			cout << a[i] << " ";
		cout << endl;
		return; 	
	}
	
	for(int i = 1 ; i <= n ; ++ i)
	{
		if(st[i] == false)
		{
			a[u] = i;
			st[i] = true;
			dfs(u + 1);
			st[i] = false; //恢复现场
		}
	}
	return;
}

int main()
{	
	cin >> n;
	
	dfs(1); //枚举第一个位置 
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    0x02 思考总结

    对比上一道题目，上一道是根据选或不选来进行排列组合，这一道题目则是根据n的位置的多少进行排列组合，这里面用到了一个 st 数组来判断这一个数字是否被使用过，从而对这n个位置的数字进行排列组合

    Ⅲ. 简单斐波那契

    0x00 算法思路

    简单的递推公式问题

    0x01 代码书写

    #include 
using namespace std;
int main()
{
    int n;
    cin >> n;

    int a = 0, b = 1;

    for (int i = 0; i < n; i ++ )
    {
        cout << a << ' ';
        int c = a + b;
        a = b;
        b = c;
    }

    cout << endl;

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    Ⅳ. 费解的开关

    0x00 算法思路

    暴力枚举第一行的32—>2的5次方 种情况，然后去统计第一行的五位01串中出现1的数量然后进行turn和step++，
    然后枚举除了最后一行的前面四行，遇到 ‘0’ 就可以对 i + 1 行 j 列 进行 turn 操作，从而使得 i，j 这个位置的灯改变成亮。
    最后去横扫最后一行，看是否有黑的灯，如果有的话，代表我们的操作是无法完成任务的，所以 输出-1
    当发现没有黑的时候，就可以取最小值进行迭代了。

    这里复制粘贴一下Acwing上边的疑惑讲解：
    1.高票题解代码中的 if (k >> j & 1) 究竟什么意思？

    其中，k保存的根本就不是第一行的灯所有可能的状态，不然它第j位都为1了还按它干嘛？ k单纯只是保存了第一行按开关的32种方式，与输入数据无关。

    且大多数题解代码中都规定了k在二进制下某位为1就代表我们选择按下这一位所在编号的开关，你也可以自己规定k在二进制下某位为0才代表我们选择按下这一位所在编号的开关，这都无所谓。

    比如k在二进制下表示为10001，就代表我们选择按第一行编号为0和编号为4的开关，然后对输入数据中第一行这两位执行turn操作。
    贴一个Acwing大佬写的超级详细的题解
    AcWing 95. 费解的开关（有图超详细，看不懂揍我）

    0x01 代码书写

    #include

using namespace std;

const int N = 6;

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)//dfs--->迷宫类模板
{
	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] ^= 1;
	}
}

int main()
{	
	int T;
	cin >> T;
	
	while(T -- )
	{
		for(int i = 0 ; i < 5 ; ++ i)
			for(int j = 0 ; j < 5 ; ++ j)
				cin >> g[i][j];
		
		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)
				if(op >> i & 1)
				{
					step ++;
					turn(0, i);
				}
			
			for(int i = 0 ; i < 4 ; ++ i)
				for(int j = 0 ; j < 5 ; ++ j)//对黑的灯进行turn操作
					if(g[i][j] == '0')
					{
						step ++;
						turn(i + 1 , j);
					}
			bool dark = false;
			for(int i = 0 ; i < 5 ; ++ i)//遍历最后一行看是否存在黑着的灯
				if(g[4][i] == '0')
				{
					dark = true;
					break;
				}
				
			if(!dark) res = min(res,step);
			memcpy(g, backup, sizeof g);
		}
		if(res > 6) res = -1;
		cout << res << endl;
	}
		
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67

    Ⅴ. 递归实现组合型枚举

    0x00 算法思路

    通过枚举第一个位置和开始的数进行dfs操作，当搜索到最后一个位置的时候就可以收获结果了

    0x01 代码书写

    #include

using namespace std;

const int N = 30;

int n, m;
int st[N];


void dfs(int u, int start)
{
	if(u == m + 1)
	{
		for(int i = 1 ; i <= m ;  ++ i)
			cout << st[i] << " ";
		cout << endl;
		return; 
	}
	
	for(int i = start ; i <= n ; ++ i)
	{
		st[u] = i;
		dfs(u + 1, i + 1);
		st[u] = 0;
	}
}

int main()
{	
	cin >> n >> m;
	
	dfs(1, 1); //枚举第一个位置 
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    Ⅵ. 带分数

    0x00 算法思路

    根据 n = a + b / c 变换 成为 ： cn = ac + n所以可以先确定ac的值进而确定b的值所以有以下思路：

    1. 枚举a的数值
    2. 枚举c的数值
    3. 判断b是否符合条件

    这个题目也用到了全排列的思想—>本节的第二道题目就是全排列题目的代码和思路

    0x01 代码书写

    #include

using namespace std;

const int N = 10;

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

bool check(int a,int c)
{
	long long b = n * (long long)c - a * c;//防止溢出用long long
	memcpy(backup,st,sizeof st);//用备份操作
	
	if(!a || !b || !c) return false;
	
	while(b)//判断b当中的数字是否被使用过了已经
	{
		int x = b % 10;
		b /= 10;
		if(!x || backup[x]) return false;//被使用过了就返回false
		backup[x] = true;
	}
	
	for(int i = 1 ; i <= 9 ; ++ i)//最后再对abc三个数字所选的数字看看是否选完了0~9个数字
		if(!backup[i])
			return false;
	return true;
}

void dfs_c(int u, int a ,int c)
{
	if(u > 9) return; //超过9个数就可以return
	
	if(check(a,c)) ans ++; //发现组合就可以 ++ans
	
	for(int i = 1 ; i <= 9 ; ++ i)//去确定c的值
	{
		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(a >= n) return; //a不能大于n
	if(a) dfs_c(u,a,0);//a不能是0 然后去找c
	
	for(int i = 1 ; i <= 9 ; ++ i)//去确定a的值
	{
		if(!st[i])
		{
			st[i] = true;
			dfs_a(u + 1,a * 10 + i);
			st[i] = false;
		}
	}
	return;
}

int main()
{
	cin >> n;
	
	dfs_a(0, 0);// 去递归搜索 a 一开始选0个数字(用了多少个数)，a是0。
	
	cout << ans << endl;
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75

    Ⅶ. 飞行员兄弟

    0x00 算法思路

    先说结论，在判断是否要对(i, j)位置的把手进行切换时，只需要计算一下第i行和第j列总共7个把手(以下称为(i, j)对应的十字)中闭合的把手数目，如果是奇数个就进行切换，偶数个就不进行切换。(奇数个是该位置的把手进行过切换的充要条件)

    因此我们从上到下从左到右顺次的对16个把手进行上述判断。如果判断结果是奇数个那么说明该位置被切换过，进行记录即可。

    0x01 代码书写

    #include

using namespace std;

#define x first
#define y second

const int N = 5;
typedef pair<int,int> PII;
char g[N][N], backup[N][N];

int get(int x, int y)
{
    return x * 4 + y;
}

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

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

    turn_one(x, y);
}

int main()
{
	for(int i = 0 ; i < 4 ; ++ i) cin >> g[i];
	
	vector<PII> res;
	
	for(int op = 0 ; op < 1 << 16 ; ++ op)
	{
		vector<PII> temp;
		memcpy(backup, g ,sizeof g);
		
		for(int i = 0 ; i < 4 ; ++ i)
			for(int j = 0 ; j < 4 ; ++ j)
			{
				if(op >> get(i, j) & 1)
				{
					temp.push_back({i, j});
					turn_all(i, j);
				}
			}
		
		bool has_closed = false;
		for(int i = 0 ; i < 4 ; ++ i)
			for(int j = 0 ; j < 4 ; ++ j)
			{
				if(g[i][j] == '+')
					has_closed = true;
			}
		
		if(has_closed == false) 
			if(res.empty() || res.size() > temp.size()) res = temp;
		
		memcpy(g,backup,sizeof g);
	}
	cout << res.size() << endl;
	for(auto& op : res) cout << op.x + 1 << " " << op.y + 1 << endl;
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72

    Ⅷ. 翻硬币

    0x00 算法思路

    将硬币和目标的样子进行比较，当发现不一样的时候就进行 turn 翻转即可

    0x01 代码书写

    #include

using namespace std;

const int N=110;
char start[N], aim[N];
int n;

void turn(int i)
{
    if(start[i]=='o') start[i]='*';
    else start[i]='o';
}

int main()
{
    cin >> start >> aim;

    n = strlen(start);

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

    cout << res << endl;

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    总结

    本篇博客主要讲解了递推与递归的算法，也涉及到了 dfs 搜索算法的使用，其实 dfs 算法可以

    1. 先去想dfs的含义，参数的含义
    2. 找到dfs的结束条件进行收获结果
    3. 根据题目要求实现dfs代码

    希望自己可以多多练习，后面蓝桥杯辅导课看完就会去看算法提高课继续提升

  • 相关阅读:
    C++零基础教程（引用）
    七夕节送女朋友啥礼物好？七夕情人节礼物推荐
    Docker | redis集群部署实战
    PMP每日一练 | 考试不迷路-11.12（包含敏捷+多选）
    张驰咨询：一位女CEO讲述六西格玛对她的重要性
    新手如何开始Microstation CE版二次开发
    MySQL 有这一篇就够（呕心狂敲37k字，只为博君一点赞！！！）
    frxJSON用法
    Java_笔记_继承_虚方法表_成员变量方法构造_thisSuper
    MATLAB--pie函数绘制复杂分类饼图（2）--附案例代码
  • 原文地址：https://blog.csdn.net/congfen214/article/details/133520593