2025-8-11-C++ 学习 暴力枚举（2）

2025-8-11-C++ 学习 暴力枚举（2）

  暴力枚举，continue。

P1036 [NOIP 2002 普及组] 选数

题目描述

已知 $n$ 个整数 $x_1,x_2,\cdots ,x_n$，以及 $1$ 个整数 $k$（$k<n$）。从 $n$ 个整数中任选 $k$ 个整数相加，可分别得到一系列的和。例如当 $n=4$，$k=3$，$4$ 个整数分别为 $3,7,12,19$ 时，可得全部的组合与它们的和为：

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：$3+7+19=29$。

输入格式

第一行两个空格隔开的整数 $n,k$（$1\le n\le 20$，$k<n$）。

第二行 $n$ 个整数，分别为 $x_1,x_2,\cdots ,x_n$（$1\le x_i\le 5\times 10^6$）。

输出格式

输出一个整数，表示种类数。

输入输出样例 #1

输入 #1

4 3
3 7 12 19

输出 #1

1

说明/提示

【题目来源】

NOIP 2002 普及组第二题

提交代码

#include <iostream>
#include <vector>
#include <cmath>using namespace std;// 判断一个数是否为素数
bool isPrime(int num) {if (num < 2) return false;if (num == 2) return true;if (num % 2 == 0) return false;for (int i = 3; i <= sqrt(num); i += 2) {if (num % i == 0) return false;}return true;
}// 递归生成组合并计算符合条件的数量
void countCombinations(const vector<int>& nums, int index, int k, int currentSum, int selected, int& result) {// 如果已经选了k个数，判断和是否为素数if (selected == k) {if (isPrime(currentSum)) {result++;}return;}// 如果剩余元素不够选，直接返回if (index + (k - selected) > nums.size()) {return;}// 不选当前元素countCombinations(nums, index + 1, k, currentSum, selected, result);// 选当前元素countCombinations(nums, index + 1, k, currentSum + nums[index], selected + 1, result);
}int main() {int n, k;cin >> n >> k;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}int result = 0;countCombinations(nums, 0, k, 0, 0, result);cout << result << endl;return 0;
}

P1157 组合的输出

题目描述

排列与组合是常用的数学方法，其中组合就是从 $n$ 个元素中抽出 $r$ 个元素（不分顺序且 $r\le n$），我们可以简单地将 $n$ 个元素理解为自然数 $1,2,\dots ,n$，从中任取 $r$ 个数。

现要求你输出所有组合。

例如 $n=5,r=3$，所有组合为：

$123,124,125,134,135,145,234,235,245,345$。

输入格式

一行两个自然数 $n,r(1<n<21,0\le r\le n)$。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

注意哦！输出时，每个数字需要 $3$ 个场宽。以 C++ 为例，你可以使用下列代码：

cout << setw(3) << x;

输出占 $3$ 个场宽的数 $x$。注意你需要头文件 iomanip。

输入输出样例 #1

输入 #1

5 3

输出 #1

1  2  31  2  41  2  51  3  41  3  51  4  52  3  42  3  52  4  53  4  5

提交代码

#include <iostream>
#include <iomanip>
#include <vector>using namespace std;// 递归生成组合
void generateCombinations(int n, int r, int start, vector<int>& current) {// 如果当前组合的大小达到r，输出该组合if (current.size() == r) {for (int num : current) {// 每个数字占3个字符宽度cout << setw(3) << num;}cout << endl;return;}// 从start开始选择下一个数字，确保组合递增且不重复for (int i = start; i <= n; ++i) {current.push_back(i);// 下一个数字要比当前数字大，保证组合递增generateCombinations(n, r, i + 1, current);current.pop_back(); // 回溯}
}int main() {int n, r;cin >> n >> r;// 特殊情况处理：当r=0时，没有组合需要输出if (r == 0) {return 0;}vector<int> current;generateCombinations(n, r, 1, current);return 0;
}

P1706 全排列问题

题目描述

按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 $n$。

输出格式

由 $1\sim n$ 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 $5$ 个场宽。

输入输出样例 #1

输入 #1

3

输出 #1

1    2    31    3    22    1    32    3    13    1    23    2    1

说明/提示

$1\le n\le 9$。

提交代码

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>using namespace std;// 递归生成全排列
void generatePermutations(int n, vector<int>& current, vector<bool>& used) {// 如果当前排列长度等于n，输出该排列if (current.size() == n) {for (int num : current) {// 每个数字占5个字符宽度cout << setw(5) << num;}cout << endl;return;}// 尝试添加每个未使用过的数字for (int i = 1; i <= n; ++i) {if (!used[i]) {used[i] = true;          // 标记为已使用current.push_back(i);    // 添加到当前排列generatePermutations(n, current, used);  // 递归生成后续排列current.pop_back();      // 回溯：移除最后一个数字used[i] = false;         // 回溯：标记为未使用}}
}int main() {int n;cin >> n;vector<int> current;          // 存储当前排列vector<bool> used(n + 1, false);  // 标记数字是否已使用generatePermutations(n, current, used);return 0;
}