本文主要是介绍【CSP考题扩展】暴力枚举(2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【P1157 组合的输出】
题目链接
解题思路
-
主函数 (
main): 读取两个整数 n n n 和 r r r，分别代表总数和要组合的元素数。然后，它初始化两个向量nums和arr。nums用于存储从 1 到 n n n 的所有数字，而arr用于存储当前的组合，它的大小与 r r r 相等。 -
组合函数 (
combine): 这是实现组合逻辑的函数。它接收四个参数：nums、start、r和arr。nums：包含所有可用数字的向量。start：当前递归开始选择数字的起始位置。r：还需要选择的数字数量。arr：存储当前组合的向量。
如果
r等于 0，这意味着已经选择了足够的元素来形成一个组合，因此它将当前的组合arr打印出来。如果还需要选择元素（
r大于 0），函数将遍历从start到nums.size() - r的数字（这样做是为了确保有足够的元素可以选择以填满剩余的位置），并对每个可能的数字执行以下操作：- 将该数字放入当前组合的相应位置。
- 递归调用
combine函数，更新起始位置和剩余需要选择的元素数。
完整代码
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;void combine(vector<int>& nums, int start, int r, vector<int>& arr) {if (r == 0) {for (size_t i = 0; i < arr.size(); i++) {cout << setw(3) << arr[i]; }cout << endl;return;}for (int i = start; i <= nums.size() - r; i++) { // 修改循环条件，确保有足够的数字可以选择arr[arr.size() - r] = nums[i]; // 直接修改当前位置的元素combine(nums, i + 1, r - 1, arr); // 选择下一个数}
}int main() {int n, r;cin >> n >> r;vector<int> nums(n);vector<int> arr(r);for (int i = 1; i <= n; i++) {nums[i - 1] = i; }combine(nums, 0, r, arr);return 0;
}
【P1706 全排列问题】
题目链接
解题思路（1）：
-
初始化排列: 首先，代码通过创建一个大小为n的向量
perm来开始，这个向量被初始化为包含1到n的数字，这是因为我们需要生成从1到n的所有可能的排列。这个初始排列代表着最小的字典序排列。 -
打印初始排列: 在生成任何其他排列之前，初始排列（按字典序最小）首先被打印出来。这是通过
printPermutation函数实现的，该函数遍历排列中的每个数字，并使用setw(5)来确保每个数字都有5个字符的宽度，这符合题目输出格式的要求。 -
生成和打印所有排列: 代码使用
while循环和next_permutation函数来生成并打印所有可能的排列。在每次循环中，next_permutation都会将向量perm修改为下一个字典序更大的排列，直到所有排列都被生成。每次生成新排列后，都会使用printPermutation函数来打印它。
next_permutation函数详解：
next_permutation是C++标准库中的一个函数，用于重新排列范围内的元素到下一个字典序更大的排列。如果这样的排列存在，函数返回true；如果这是可能的排列中的最后一个（也就是没有字典序更大的排列），函数返回false。- 工作原理：
next_permutation首先从范围的最后开始向前查找，直到找到一对连续的元素，其中前一个小于后一个。这对元素标记了需要重新排列的范围的边界。然后，函数再次从范围的末尾开始，寻找第一个大于前面找到的较小元素的元素，并与之交换。最后，函数逆置原先找到的较小元素后面的所有元素，以确保我们获得的是下一个字典序排列。
- 工作原理：
完整代码（1）
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>using namespace std;// 用于打印一个排列
void printPermutation(const vector<int>& perm) {for (int num : perm) {cout << setw(5) << num; // 每个数字占5个字符宽度}cout << endl;
}int main() {int n;cin >> n; vector<int> perm(n);for (int i = 0; i < n; ++i) {perm[i] = i + 1; // 初始化向量，使其包含1到n}printPermutation(perm); // 先打印初始排列while (next_permutation(perm.begin(), perm.end())) { // 使用 next_permutation 在while循环中生成并打印从1到n的全排列printPermutation(perm);}return 0;
}
解题思路（2）
-
主函数(
main):- 通过
cin >> n;获取用户输入的整数n，这个整数表示要生成从1到n的全排列。 - 接着调用
dfs(0);开始深度优先搜索（DFS），以生成所有可能的排列。这里从第0位开始搜索，尽管实际上排列中的位是从1开始的，这样做是为了在递归中处理方便。
- 通过
-
深度优先搜索函数(
dfs):- 这个函数用于生成全排列，并采用递归的方式实现。
dfs函数接收一个参数k，表示当前正在尝试填充第k+1位（因为数组索引从0开始，但排列从1开始）。- 如果
k == n，意味着已经成功生成了一个从1到n的排列，因为每个数字都被使用了一次，此时会调用printPermutation()函数打印当前的排列。 - 如果
k < n，则循环从1到n，尝试每个数字。如果某个数字i尚未被使用（即isUsed[i]为0），则执行以下步骤：- 将
i标记为已使用，即isUsed[i] = 1。 - 将这个数字
i放入当前排列的第k+1位，即currentPermutation[k + 1] = i。 - 递归调用
dfs(k + 1)来填充下一位。 - 回溯：递归调用返回后，撤销
i的使用标记，即isUsed[i] = 0，以便这个数字可以在其他位置被使用。
- 将
-
打印排列函数(
printPermutation):- 当一个排列完成时，这个函数被调用来输出排列。
- 它通过循环，对于排列中的每一个位置，使用
cout << setw(5) << currentPermutation[i];来打印出每个数字，其中setw(5)确保每个数字占据5个字符宽的空间，以保持输出整齐。 - 打印完一个排列后，使用
cout << endl;换行，以便开始打印下一个排列。
完整代码（2）
#include <iostream> // 替代 #include<bits/stdc++.h>，仅包含输入输出相关功能
#include <iomanip>
using namespace std;int n, isUsed[100], currentPermutation[100]; // `isUsed`用于判断某个数是否已经被使用，`currentPermutation`用于存储当前的排列void printPermutation() {for (int i = 1; i <= n; i++) {cout << setw(5) << currentPermutation[i];}cout << endl;
}void dfs(int k) { // 深度优先搜索函数，当前填充第k位if (k == n) { // 如果已填满所有位printPermutation(); // 打印当前排列return;}for (int i = 1; i <= n; i++) { // 尝试每个可能的数字1-nif (!isUsed[i]) { // 如果当前数字尚未使用isUsed[i] = 1; // 标记为已使用currentPermutation[k + 1] = i; // 将当前数字放入排列中dfs(k + 1); // 继续填充下一个位置isUsed[i] = 0; // 回溯，撤销当前数字的使用标记}}
}int main() {cin >> n; dfs(0); // 从第0位开始进行深度优先搜索return 0;
}
这篇关于【CSP考题扩展】暴力枚举(2)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
