2024年CSP-J暑假冲刺训练营(3)：递归

一、递归

1. 意义

递归算法： 一种函数不断调用自身来解决更小规模问题的算法，直到达到基本情况或结束条件。递归可以将复杂的问题分解成更小的子问题，从而简化解决方案。

2. 要素

• 边界： 没有了边界就会一直进行死循环。
• 向边界靠近： 不靠近边界也会一直进行死循环。

二、典型例题

1. 全排列

#include <iostream>
using namespace std;int n;
int a[10];
bool used[10];void dfs(int step) {if (step > n) {for (int i = 1; i <= n; i++) {cout << a[i] << " ";}cout << endl;return;}for (int i = 1; i <= n; i++) {if (used[i] == 0) {a[step] = i;used[i] = 1;dfs(step+1);used[i] = 0;}}
}int main() {cin >> n;dfs(1);return 0;
}

2. 数字组合

#include <iostream>
using namespace std;int n, m;
int a[15];
bool used[15];void dfs(int step, int last) {if (step > m) {for (int i = 1; i <= m; i++) {cout << a[i] << " ";}cout << endl;return;}for (int i = last+1; i <= n; i++) {if (used[i] == 0) {a[step] = i;used[i] = 1;dfs(step+1, i);used[i] = 0;}}
}int main() {cin >> n >> m;dfs(1, 0);return 0;
}

三、例题

1. 素数环

#include <iostream>
using namespace std;int n, cnt;
int a[20];
bool vis[20];bool isPrime(int x) {if (x <= 1) return 0;for (int i = 2; i * i <= x; i++)if (x % i == 0)return 0;return 1;
}void dfs(int step) {if (step > n  && isPrime(a[1]+a[n])) {for (int i = 1; i <= n; i++)cout << a[i] << " ";cnt++;cout << endl;return;}for (int i = 1; i <= n; i++) {if (vis[i] == 0 && (step == 1 || isPrime(i+a[step-1]))) {a[step] = i;vis[i] = 1;dfs(step+1);vis[i] = 0;}}
}int main() {cin >> n;dfs(1);cout << cnt;return 0;
}

2. 素数环变形

从电脑输入 $n$ 个正整数，求这个 $n$ 个乱序的正整数，能组成多少个素数环的形式，输入的所有数在每组素数环情况中都要用到。

#include <iostream>
#include <algorithm>
using namespace std;int cnt, n, p[20], a[20];
bool vis[20];bool isPrime(int x) {if (x <= 1) return false;for (int i = 2; i * i <= x; i++)if (x % i == 0)return false;return true;
}void dfs(int step) {if (step == n+1) {if (!isPrime(a[1]+a[n])) return;for (int i = 1; i <= n; i++)cout << a[i] << " ";cnt++;cout << endl;return;}for (int i = 1; i <= n; i++) {if (!vis[i]) {if (step==1 || isPrime(a[step-1]+p[i])) {a[step] = p[i];vis[i] = true;dfs(step+1);vis[i] = false;}}}
}int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> p[i];sort(p+1,p+n+1);dfs(1);cout << cnt;return 0;
}