片头
嗨~小伙伴们，大家好！现在我们来到实训篇啦~本篇章涉及算法知识，比基础篇稍微难一点，我会尽量把习题讲的通俗易懂。准备好了吗？咱们开始咯！
第1题 递归实现指数型枚举
我们先画个图~
从图中，我们看到，每个位置都有2种选择，选或者不选。如果不选，那么该位置记为×；如果要选，该位置记为✔， 整个结构是一层一层递归的，是一个递归搜索树。
题目告诉我们，输入的整数n的范围：1<=n<=15，因此，我们可以定义一个长度为N的数组st[N]，N为16，多开一个空间，记录每个位置的状态：0表示还没考虑，1表示选它，2表示不选它。
刚开始的时候，每个位置默认都是“不选”状态，一直递归到最后一层，最后恢复现场；回到调用的地方，继续往下执行；再一次选择的时候，是“被选”状态，一种递归到最后一层，最后恢复现场。
代码如下：
//递归实现指数型枚举
//从 1~n 这n个整数中随机选取任意多个，输出所有可能的选择方案。
//输入一个整数n。
//输出每行输出一种方案。
//同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
//对于没有选任何数的方案，输出空行。
//数据范围 1 < n < 15
const int N = 16;
int n;
int st[N];//表示这个位置的状态,
//0表示还没考虑,1表示选它,2表示不选它
void Func(int k) {
//越界
if (k > n) {
for (int i = 1; i <= n; i++) {
if (st[i] == 1)
printf("%d ", i);
}
cout << endl;
return;
}
//第一次都是不选
st[k] = 2;
Func(k + 1); //递归到下一层
st[k] = 0; //恢复现场
//第二次选
st[k] = 1;
Func(k + 1);//递归到下一层
st[k] = 0; //恢复现场
}
int main() {
cin >> n;
Func(1); //k初始值为1,表示从第1个位置开始
return 0;
}运行结果如下：
第2题 递归实现排列型枚举
emmm，咱们先来画一个图~
我们可以采用：依次枚举每个位置放哪个数。
题目已知，输入的整数 1<=n<=9，定义长度为N的数组st[N]，N为10，多开一个空间，记录每个位置的状态：0 表示还没放数，1~n 表示放了哪个数。
对于每一个位置，有1~n种选择，如果前面的数被用了，那么后面就不能再使用这个数字。因此，我们可以定义一个bool型的数组used[N]，用来记录这个数是否被用过。
我们还要保证按照从小到大的顺序，因此，先排较小的数，再排较大的数，保证后一个数比前一个数大。定义一个for循环，依次循环遍历。
代码如下：
//递归实现排列型枚举
//把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
//输入格式一个整数n。
//输出按照从小到大的顺序输出所有方案，每行1个。
//首先，同一行相邻两个数用一个空格隔开。
//其次，对于两个不同的行，对应下标的数--比较，字典序较小的排在前面。
//数据范围 1≤n < 9
//输入样例:
// 3
//输出样例 :
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1
const int N = 10;
int n;
int st[N]; //当前位置的状态
//0 表示还没放数，1~n表示放了哪个数
bool used[N]; //true表示用过，false表示还没用过
void Func(int k) {
//边界
if (k > n) {
for (int i = 1; i <= n; i++) {
printf("%d ", st[i]);
}
cout << endl;
return;
}
//依次枚举每个分支，即当前位置可以填哪些数
for (int i = 1; i <= n; i++)
{
if (!used[i]) { //如果这个数字没有被用过
st[k] = i; //当前这个位置填入数字
used[i] = true; //标记这个数字被用过了
Func(k + 1); //递归到下一层
st[k] = 0; //恢复现场
used[i] = false; //恢复现场
}
}
}
int main() {
cin >> n;
Func(1);
return 0;
}运行结果如下：
第3题 递归实现组合型枚举
这道题，仍然需要画图~
代码如下：
//递归实现组合型枚举
//从 1~n 这 n个整数中随机选出 m 个，输出所有可能的选择方案。
//输入两个整数 n, m, 在同一行用空格隔开。
//输出按照从小到大的顺序输出所有方案，每行1个。
//首先，同一行内的数升序排列，相邻两个数用一个空格隔开!
//其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面(例如1357排在1368前面)
//数据范围 n > 0 ， 0 < m < n ， n + (n - m)≤25
//输入样例 :
//5 3
//输出样例 :
// 1 2 3
// 1 2 4
// 1 2 5
// 1 3 4
// 1 3 5
// 1 4 5
// 2 3 4
// 2 3 5
// 2 4 5
// 3 4 5
const int N = 30;
int ways[N];
int n, m;
void dfs(int k, int start) {
if (k > m) //如果k>m,那么刚好选了m个数,打印输出
{
for (int i = 1; i <= m; i++) {
printf("%d ", ways[i]);
}
puts("");
return;
}
for (int i = start; i <= n; i++) {
ways[k] = i; //填入数
dfs(k + 1, i + 1); //递归到下一层
ways[k] = 0; //恢复现场
}
}
int main() {
cin >> n >> m;
dfs(1, 1);//最开始从第1个位置开始,start的初始值为1
return 0;
}我们还可以对代码进一步优化：当选中的前 k-1个数 + 剩余的 n-start+1 之和小于 m 的时候，直接退出。
if (k - 1 + n - start + 1 < m) return;
//剪枝: 如果把后面的数都选上，都不够m个，当前的分支就一定无解第4题 简单斐波那契
这道题，我们在基础篇已经讲过。可以先定义一个数组，把斐波那契数列存进去，再遍历。
代码如下：
//简单斐波那契
//以下数列0 1 1 2 3 5 8 13 21...被称为裴波纳契数列。
//这个数列从第3项开始，每一项都等于前两项之和。
//输入一个整数N，请你输出这个序列的前N项。
//输入一个整数N。
//输出在一行中输出斐波那契数列的前N项，数字之间用空格隔开。
//数据范围 0 < N < 46
//输入样例: 5
//输出样例 : 0 1 1 2 3
const int N = 50;
int main() {
int n;
cin >> n;
int a[N];
a[0] = 0;
a[1] = 1;
a[2] = 1;
for (int i = 3; i <= 46; i++) {
a[i] = a[i - 1] + a[i - 2];
}
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
cout << endl;
return 0;
}我们还可以将代码优化：
int main() {
int n;
cin >> n;
int a = 0;
int b = 1;
for (int i = 0; i <= n - 1; i++) //i的范围: 0~n-1
{
cout << a << " ";//必须先打印a的值
//如果先执行c=a+b,那么a原来的值会被覆盖掉
int c = a + b;
a = b;
b = c;
}
return 0;
}我们画个图，理解一下优化代码：
| i | a | b |
| 0 | f(0) = 0 | f(1) = 1 |
| 1 | f(1) = 1 | f(2) = 1 |
| 2 | f(2) = 1 | f(3) = 2 |
| 3 | f(3) = 2 | f(4) = 3 |
| 4 | f(4) = 3 | f(5) = 5 |
| 5 | f(5) = 5 | f(6) = 8 |
| ... | ... | ... |
| n-2 | f(n-2) | f(n-1) |
| n-1 | f(n-1) | f(n) |
| n | f(n) | f(n+1) |
观察上表，我们发现
当 i == 0 时，a的值为f(0)=0；
当 i == 1 时，a的值为f(1)=1；
当 i == 2 时，a的值为f(2)=1；
当 i == 3 时，a的值为f(3)=2；
当 i == 4 时，a的值为f(4)=3；
......
当 i == n-1 时，即可输出a的值f(n-1)。
你可能会问：为啥不把打印a放在最后面？哈哈，如果把这行代码放最后面，a原来的值会被覆盖掉，所以必须把 cout<<a<<" "; 这行代码放最前面。
或者这样写也可以：
for (int i = 1; i <= n; i++) //i的范围: 1~n
{
cout << a << " ";//必须先打印a的值
//如果先执行c=a+b,那么a原来的值会被覆盖掉
int c = a + b;
a = b;
b = c;
}第5题 翻硬币
对于这道题，咱们先画个图~
因此，我们发现，每次都是翻转相邻2个硬币，我们可以每相邻2个硬币共用1个开关。
我们可以定义2个数组，分别表示初始状态和目标状态，2个数组必须长度相同。定义计数器count，用来记录总共操作步数。从初始数组的第一个元素开始比较，如果和目标数组对应位置的元素不一样，那么改变当前元素的状态，并且计数器+1。
代码如下：
//翻硬市
//小明正在玩一个“翻硬币”的游戏.
//桌上放着排成一排的若干硬币。我们用"表示正面，用。表示反面(是小写字母，不是零)
//比如，可能情形是: **oo***oooo
//如果同时翻转左边的两个硬币，则变为 : oooo***oooo
//现在小明的问题是 : 如果已知了初始状态和要达到的目标状态
//每次只能同时翻转相邻的两个硬币, 那么对特定的局面，最少要翻动多少次呢 ?
//我们约定 : 把翻动相邻的两个硬币叫做一步操作。
//输入格式
//两行等长的字符串，分别表示初始状态和要达到的目标状态
//输出格式
//1个整数，表示最小操作步数
//数据范围
//输入字符串的长度均不超过100.
//数据保证答案一定有解。
const int N = 110;
char start[N];
char aim[N];
void turn(int a) {
if (start[a] == '*')
start[a] = 'o';
else
start[a] = '*';
}
int main() {
cin >> start; //输入初始状态
cin >> aim; //输入目标状态
int len = strlen(start); //计算字符串长度
int count = 0; //统计翻转次数
for (int i = 0; i < len; i++) {
if (start[i] != aim[i]) //如果当前位置的值二者不相同,
//那么将start位置的值改变
{
turn(i);
turn(i + 1);
count++; //次数+1
}
}
cout << count << endl;
return 0;
}第6题 汉诺塔
咱们可以先画个图，理解一下什么是汉诺塔问题规则：
Hanoi塔问题规则
- 每次只能移动1个圆盘；
- 圆盘可以插在X、Y和Z中的任一塔座上；
- 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
如图所示是一个3阶的Hanoi塔演示（从左往右依次为X、Y、Z塔）：
Hanoi塔分析
①当 n==1 阶汉诺塔时，将唯一的圆盘从塔座X直接移动到塔座Z。
②当 n>1 时（动图展示为 n==3），需要利用Z作为辅助塔，总是设法将X塔的最后一个圆盘n移动到Z塔下，则必然要将 1~n-1 个圆盘移动到Y塔上
③此时Y塔作为最初的X塔的状态，X塔作为Z塔的最初状态，X塔是辅助塔，应该将当前Y塔下的最后1个圆盘 n-1 移动到Z塔上。
④若 n>3，则不断在②和③循环执行，直到将所有的圆盘全部有移动到Z塔上
⑤当还剩最后1个圆盘时，则执行第1个步骤，直接将圆盘移动到Z塔。
如上步骤一般，当 n>1 总是在步骤②、③重复，且Z塔与X塔交换成为辅助塔。所以，我们可以使用递归来处理这种重复步骤。
//汉诺塔
//定义汉诺塔递归函数
//n: 盘子的数量
//source: 起始柱
//target: 目标柱
//auxiliary: 辅助柱
void hanota(int n, char source, char target, char auxiliary) {
//基本情况: 如果只有1个盘子,直接移动到目标柱
if (n == 1) {
cout << "将盘子 1 从 " << source << " 移动到 " << target << endl;
return; //递归终止
}
//递归步骤1: 将前 n-1 个盘子从起始柱移动到辅助柱(借助目标柱)
hanota(n - 1, source, auxiliary, target);
//将第n个盘子(最大的盘子)从起始柱移动到目标柱
cout << "将盘子 " << n << " 从 " << source << " 移动到 " << target << endl;
//递归步骤2: 将前 n-1 个盘子从辅助柱移动到目标柱(借助起始柱)
hanota(n - 1, auxiliary, target, source);
}
int main() {
int n = 3;
cout << "解决 " << n << " 个盘子的汉诺塔问题: " << endl;
//调用汉诺塔函数, A 是起始柱, C是目标柱, B是辅助柱
hanota(n, 'A', 'C', 'B');
return 0;
}
第7题 奇妙变换
这道题，我们只需要按照题目要求，编写代码即可。注意：这里的元素类型为长整型long long，如果为int整型，容易溢出。
#include <iostream>
using namespace std;
const int mod = 998244353;
long long func(long long n){
if(n<=10) return n*(n-1);
else{
long long ans = 2*n*func(n-6);
ans %= mod;
return ans;
}
}
int main()
{
long long n;
cin >> n;
long long ret = func(n);
cout << ret << endl;
return 0;
}第8题 全排列的价值
我们举个例子，比如：“3”的全排列
假设有5个数，分别为“1”，“3”，“2”，“5”，“4”，全排列的价值为8
做过逆序对问题的话，明显可以看出对于任意一个排序，其价值等于逆序对的数量。考虑使用dp来进行递推，我们定义f(n)为1~n的全排列中所有排列的价值之和，明显可以得到f(1)=0，f(2)=1。
关键在于：如何从f(n-1)递推得到f(n)的值？我们以n为4时进行举例，仔细观察3的全排列：
此时，我们在这些排列的基础上插入”4“，无论在哪个排列中插入”4“，都有4个插入的位置，比如插入第1个排列（1，2，3）时可以得到下面4种情况：
我们每个排列只看元素4带来的贡献分别为 0+1+2+3 = 6，对于3的任何一个排列我们插入"4"带来的价值都一样，这是因为我们在n-1的全排列插入n时，排列中的元素都严格小于n，所以我们当n插入的位置之前有几个元素，则带来的价值就是几。
根据该推导可知：当在n-1的任何一个排列插入n时，n带来的贡献则为，也就是从1累加到n-1，我们可以使用高斯求和计算。当然，这只是1个排列带来的价值，对于n而言，它的全排列的数量为n！，我们设g(n)为n的全排列的数量，也就是n的阶乘。
我们上述只考虑了n给我们带来的价值，我们当然还必须考虑其他数，对于排列（1，2，3），在插入4后有四种情况，它自己也变成了4份，价值也相应变成了4倍，"3" 的任何一个排列的价值都是如此。由此我们可以得知，当从f(n-1)递推到f(n)时，f(n-1)会变成n倍。根据上述的推导我们可以得到递推转移公式：
答案很大，在推导过程中，需要进行取模
typedef long long ll;
const int MOD = 998244353; //定义模数
vector<long long> f(1000010, 0);//f数组,存储结果
vector<long long> g(1000010, 0);//g数组,存储阶乘
//初始化g数组,计算阶乘
void init(int n) {
long long h = 1;
for (int i = 1; i <= n; i++) {
h = h * i % MOD; //计算阶乘并取模
g[i] = h;
}
}
//全排列的价值
int main() {
int n;
cin >> n; //输入n
f[1] = 0; //初始化f[1]
init(n); //初始化g数组
//动态规划计算f[i]
for (int i = 2; i <= n; i++) {
f[i] = (f[i - 1] * i % MOD + (long long)i * (i - 1) / 2 % MOD * g[i - 1] % MOD) % MOD;
}
cout << f[n] << endl; //输出结果
return 0;
}第9题 数正方形
对于本道题，咱们需要画图理解~
观察上图，我们可以发现，
①nn点阵，边长(n-1)×(n-1)
②1×1的正方形，填 (n-1)^2个
③2×2的正方形中，有一个卡着中间的1个独特正方形，加上本身，一共2个每个单元，能填(n-2)^2个
④同理，3×3的正方形中间可以卡2个独特的正方形，加上本身，一共3个每个单元，能填(n-3)^2个
⑤一直到 (n-1)×(n-1)的正方形中间可以卡 n-2 个独特的正方形，加上本身，一共 n-1 个每个单元，这就是第1个 i 的范围，从1~n-1
⑥后面(n-1)^2就是总共的单元个数，乘以每个单元有多少个，即为for循环代码含义。
我们看看当 n=6 时，也就是边的个数 => n-1 = 5 情况：
看到题给示例不同大小的画法，一个思路是，把正方形划分成不同维度的单元块去找，有助于我们聚焦于更易于计算的子问题。
考虑一个 n×n 的点阵，其边长为 (n-1)×(n-1)。
那我们先取 1×1 大小的单元，在这个 n×n 的点阵里，就像一块小积木一样，全图四处划动，显然单元有 (n-1)×(n-1) 种存在的方式，而每个单元内部最多只能画出1个正方形。因此，对于 1×1 这个维度在全图中就有 1×(n-1)×(n-1) 种画法。
2×2 大小的单元，有 (n-2)×(n-2) 种取法，对于每个 2×2 单元的内部，能画出一个 2×2 的边框正方形，还能画出一个斜着放的正方形，那么对于每个单元有2种画法，对于 2×2 这个维度在全图中就是 2×(n-2)×(n-2) 种画法。
3×3 大小的单元，取法 (n-3)×(n-3) 种，对于每个 3×3 单元的内部，可以有3种画法，全图总共 3×(n-3)×(n-3) 种画法。
..........
(n-1)×(n-1) 的单元，把整个图框满了，只能有1种取法，对于这个单元，内部易知有 n-1 种画法，对于 (n-1)×(n-1) 这个维度在全图就是 (n-1)×1×1 种画法。
从 1 到 i 对每个 i × i 的单元遍历求和：ans += i×(n-i)×(n-i)
每一步都取余一次就可以得到答案了。
#include <iostream>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int main()
{
ll n; // n*n 点阵
cin >> n;
ll ans = 0;
for (int i = 1; i <= n - 1; i++) {
ans += i * (n - i) * (n - i);
ans %= mod;
}
cout << ans << endl;
return 0;
}片尾
今天我们学习了递归以及相关的算法知识，希望看完这篇文章对友友们有所帮助！！！
求点赞收藏加关注！！！
谢谢大家！！！
