【一个月备战蓝桥算法】递归与递推

字典序

在刷题和计算机科学领域，字典序（Lexicographical order）也称为词典序、字典顺序、字母序，是一种对序列元素进行排序的方式，它模仿了字典中单词的排序规则。下面从不同的数据类型来详细解释字典序：

字符串的字典序

在字典中，单词是按照字母的先后顺序排列的。对于两个字符串，字典序的比较规则如下：

• 比较过程：从两个字符串的第一个字符开始逐个比较，如果对应位置的字符不同，则字符 ASCII 码值小的字符串排在前面；如果对应位置字符相同，则继续比较下一个位置的字符，直到出现不同字符或者其中一个字符串结束。

• 示例：

  • 比较 "apple" 和 "banana"，因为第一个字符 'a' 的 ASCII 码值小于 'b'，所以 "apple" 在字典序中排在 "banana" 前面。

  • 比较 "apple" 和 "app"，前三个字符都相同，但 "app" 先结束，所以 "app" 在字典序中排在 "apple" 前面。

整数序列的字典序

对于整数序列，同样可以按照字典序进行比较：

• 比较过程：将整数序列看作由数字组成的字符串，从序列的第一个元素开始逐个比较元素的大小，如果对应位置的元素不同，则元素值小的序列排在前面；如果对应位置元素相同，则继续比较下一个位置的元素，直到出现不同元素或者其中一个序列结束。

• 示例：

  • 比较序列 [1, 2, 3] 和 [2, 1, 3]，第一个元素 1 小于 2，所以 [1, 2, 3] 在字典序中排在 [2, 1, 3] 前面。

  • 比较序列 [1, 2, 3] 和 [1, 2]，前两个元素都相同，但 [1, 2] 先结束，所以 [1, 2] 在字典序中排在 [1, 2, 3] 前面。

在刷题中的应用

在很多算法题中，字典序常常作为排序的依据或者要求输出的结果满足字典序的要求，例如：

• 全排列问题：要求输出给定序列的所有全排列，并且按照字典序输出。例如，对于序列 [1, 2, 3]，其全排列按照字典序输出为 [1, 2, 3]、[1, 3, 2]、[2, 1, 3]、[2, 3, 1]、[3, 1, 2]、[3, 2, 1]。

• 子集问题：可能要求输出所有子集，并且按照字典序排列。

代码示例（C++ 实现全排列并按字典序输出）

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> nums = {1, 2, 3};do {for (int num : nums) {std::cout << num << " ";}std::cout << std::endl;} while (std::next_permutation(nums.begin(), nums.end()));return 0;
}

这些代码示例展示了如何生成全排列并按字典序输出，在刷题中可以根据具体需求对代码进行调整。

92.递归实现指数型枚举

 #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 16; // 最大数据范围int statu[N]; // 状态数组 0表示未考虑 1表示选 2表示不选int n; // 标准输入void dfs(int u) // d{if(u > n) // 考虑到了最后一个位置 -- 递归出口{// 打印所有的数for(int i = 0; i <= n; i++){if(statu[i] == 1)printf("%d ", i);}printf("\n");// 打印换行，表示这一次枚举完毕return;// 返回上一层}// 不选的情况statu[u] = 2;dfs(u+1);statu[u] = 0;// 恢复现场// 选的情况statu[u] = 1;dfs(u+1);statu[u] = 0; }int main(){cin >> n;dfs(1); //对第1个数进行考虑return 0;}

 94.递归实现排列型枚举

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;// 数组定义成全局变量，初始值一定是0，如果定义成局部变量，初始值随机
const int N = 10;
int status[N]; // 0表示未填入 1—n表示填入的数
bool used[N];// 标记这个数有没有被用过 true用过 false没有用过
int n;void dfs(int u)
{// 递归出口if(u > n){for(int i = 1; i <= n; i++) printf("%d ", status[i]);puts("");return;}// 依此枚举每个分支，即当前位置可以填哪些数for(int i = 1; i <= n; i++){if(!used[i]) // 当前的数没有用{status[u] = i; // 填入这个数used[i] = true; // 标记已使用dfs(u + 1);// 恢复现场used[i] = false;status[u] = 0;}}}int main()
{scanf("%d", &n);dfs(1);return 0;
}

 93.递归实现组合型枚举

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
int n, m;
const int N = 30;
int status[N];void dfs(int u, int start)
{// （u-1 + n - start + 1 < m）if(u + n - start < m) return; // 剪枝 -- start后面的数加起来都不够凑m个数// 递归出口if(u > m){for(int i = 1; i <= m; i++) printf("%d ", status[i]);puts("");return;}for(int i = start; i <= n; i++){status[u] = i;dfs(u+1, i+1);// 恢复现场status[u] = 0;}
}int main()
{scanf("%d %d", &n, &m);dfs(1, 1);return 0;
}

 1209.带分数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 10;
int ans = 0;int n;
bool status[N]; // 判重数组
bool backup[N];bool check(int a, int c)
{long long b = n * (long long)c - a * c;// a b c 不能为0if(!a || !b || !c) return false;memcpy(backup, status, sizeof(status));while(b){int x = b % 10;b = b / 10;// x在ac中不能出现, x不能为0if(!x || backup[x]) return false;backup[x] = true; }// 看看每个数字是否出现过 -- 必须全部出现for(int i = 1; i <= 9; i++){if(!backup[i]) return false;}return true;
}void dfs_c(int u, int a, int c)
{if(u == n) return;if(check(a, c)) ans++;for(int i = 1; i <= 9; i++){if(!status[i]){status[i] = true;dfs_c(u+1, a, c * 10 +i);status[i] = false;}}}void dfs_a(int u, int a)
{if(a >= n) return; if(a) dfs_c(u, a, 0); // 只要a小于n，每种情况下都有dfs_cfor(int i = 1; i <= 9; i++){if(!status[i]){status[i] = true;dfs_a(u+1, a * 10 + i);status[i] = false; }}
}int main()
{cin >> n;dfs_a(0, 0);  // 当前已经用了多少个数字，  最开始a是0 cout << ans << endl;return 0;
}

 717.简单斐波那契

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int main()
{int n = 0;cin >> n;int F[47];F[0] = 0, F[1] = 1, F[2] = 1;for(int i = 3; i <= n; i++){F[i] = F[i-1] + F[i-2];}for(int i = 0; i < n; i++){cout << F[i] << " ";}return 0;
}

 优化

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int main()
{int n; cin >> n;int a = 0, b = 1;for(int i = 1; i <= n; i++){cout << a << ' ';int fn = a + b;a = b; b = fn;}return 0;
}

1208.翻硬币

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 110;
char start[N], aim[N];void turn(int i)
{if(start[i] == '*') start[i] = 'o';else start[i] = '*';
}int main()
{cin >> start >> aim;int n = strlen(start);// 计算输入长度int ret = 0;for(int i = 0; i < n - 1; i++){if(start[i] != aim[i]){turn(i), turn(i+1);ret++;}}cout << ret << endl;return 0;
}

 116.飞行员兄弟

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>using namespace std;
const int N = 5;
char g[N][N], backup[N][N];
typedef pair<int, int> PII;// 映射函数
int get(int i, int j)
{return i * 4 + j;
}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); // xy在循环中被按了两次，现在调回去
}int main()
{vector<PII> res;// 输入for(int i = 0; i < 4; i++)for(int j = 0; j < 4; j++)cin >> g[i][j];// 枚举所有方案for(int op = 0; op < (1 << 16); op++){vector<PII> temp; // 存储方案memcpy(backup, g, sizeof(g)); // 备份方案// 枚举16个位置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 hash_close = false;// 判断是否全部灯泡已经亮了for(int i = 0; i < 4; i++)for(int j = 0; j < 4; j++)if(g[i][j] == '+')hash_close = true;if(!hash_close){if(res.empty() || res.size() > temp.size() ) res = temp;}memcpy(g, backup, sizeof(backup)); // 恢复方案}cout << res.size() << endl;for (auto op : res) cout << op.first + 1 << ' ' << op.second + 1 << endl;return 0;
}