学习目标
枚举算法意思示例
枚举重点
[【模拟枚举】水仙花数]
【题意分析】
我们需要找出区间内所有的水仙花数
【思路分析】
用for循环的方式去判断从100到999的每一个数
将当前的数个位、十位、百位求出
判断每一位的数的次方之和是否等于本身
【参考代码】
#include<iostream>
using namespace std;
int main(){
int a,b,c;
for(int i=100;i<=999;i++){
//将当前的数个位、十位、百位求出
a=i/100;
b=i/10%10;
c=i%10;
//判断每一位的数的次方之和是否等于本身
if(a*a*a+b*b*b+c*c*c==i){
cout<<i<<endl;
}
}
return 0;
}
View Code
埃式筛法
埃拉托斯特尼筛法（埃氏筛法）是一种用于找出一定范围内所有素数的古老算法，其基本思想是从小到大遍历自然数，将素数的倍数标记为合数，依此不断筛选，最终得到所有的素数。以下是埃氏筛法的详细步骤：
-
初始化： 从2开始，标记所有自然数为未筛选（或称为未标记）状态。
-
找到下一个未筛选的数： 从当前位置开始，找到下一个未筛选的数，将其标记为素数。
-
标记该素数的倍数： 将该素数的所有倍数标记为合数，因为它们肯定不是素数。这些倍数是当前素数的2倍、3倍、4倍，以此类推。
-
重复步骤2和步骤3： 重复以上步骤，直到达到预定的范围。
-
结束： 当所有的数都被筛选完成后，剩下的未被标记的数即为素数。
这个算法的关键在于，每次找到一个素数时，它的倍数都被标记为合数，从而排除了一大部分非素数。这样，算法的时间复杂度相对较低，是一种高效的素数生成算法。
埃拉托斯特尼筛法的一个优化是，当筛选到某个数时，只需要从它的平方开始标记，因为它的所有小于它的倍数在之前已经被其他数标记过了。
总的来说，埃拉托斯特尼筛法是一种简单而高效的算法，用于找出一定范围内的所有素数。
在实现埃拉托斯特尼筛法时，有一些注意点需要考虑：
-
数组大小： 需要足够大的数组来存储待筛选的数。数组的大小至少应该是筛选范围的上限。这样才能确保在标记合数的过程中不会超出数组的范围。
-
标记倍数时的边界： 在标记某个素数的倍数时，要确保不超出数组的边界。因此，需要谨慎计算倍数的位置，以避免数组越界错误。
-
筛选范围的选择： 当确定一个筛选的范围时，要确保该范围足够大，以包含所需的素数。如果范围选择不当，可能会导致缺少某些素数。
-
算法复杂度： 虽然埃拉托斯特尼筛法是一种高效的算法，但在某些情况下，可能会选择其他更适合特定问题的素数生成算法，例如线性筛法。
综上所述，实现埃拉托斯特尼筛法时，要注意数组大小、边界情况、范围选择以及一些优化细节，以确保算法的正确性和效率。
[【模拟枚举】素数个数]
【题意分析】
需要求出在n的范围内所有的素数，因为n的范围很大，需要用到素数筛的方式
【思路分析】
枚举的方式求解会导致时间超时，使用素数筛的方式，将当前的数的倍数全部标记
定义一个数组用于标记所有的非素数
定义ans统计素数的个数
循环从2开始，判断当前的数是否被标记，将标记+1，并且将所有的素数的倍数标记
【参考代码】
#include <iostream>
using namespace std;
//定义一个数组用于标记所有的非素数
bool prime[2000009];
int main() {
int n;
cin >> n;
//定义ans统计素数的个数
int ans = 0;
//循环从2开始，判断当前的数是否被标记，是素数则将标记+1，并且将所有的素数的倍数标记
for (int i = 2; i <= n; i++) {
if (!prime[i]) {
ans++;
for (int j = 2 * i; j <= n; j += i) {
prime[j] = 1;
}
}
}
cout << ans;
return 0;
}
View Code
MAP容器
迭代器
[【模拟枚举】map遍历]
【题意分析】
将m−>20 的键值对、r−>30 的键值对、a−>40 的键值对存入map，然后遍历map输出map中的所有储存的内容
【思路分析】
用 map 存储这些键值对，由题意可知，键是字符类型，值是整数类型，最后按照格式遍历输出。
定义迭代器
迭代器遍历map数组输出储存的内容
【参考代码】
#include <iostream>
#include <map>
using namespace std;
int main() {
map <char, int> mp;
mp['m'] = 20;
mp['r'] = 30;
mp['a'] = 40;
//定义迭代器
map <char, int> ::iterator it;
//迭代器遍历map数组输出储存的内容
for (it = mp.begin(); it != mp.end(); ++it) {
cout << it->first << " " << it->second << '\n';
}
return 0;
}
View Code
set
迭代器
[【模拟枚举】鲜奶公司百年大庆]
【题意分析】
将不相同的随机数从小到大排好顺序，对于所有的数去重统计数量，先输出数量再然后从小到大排序输出
【思路分析】
用 set 存储这些整数，直接可以达到去重和排序的效果，最后在遍历 set 进行输出即可。
定义set用于储存所有的数
将n个数都插入到set中
输出set中元素的个数
定义迭代器，循环输出set中的所有的数
【参考代码】
#include <iostream>
#include <set>
using namespace std;
int main() {
//定义set用于储存所有的数
set<int> se;
int n;
cin >> n;
//将n个数都插入到set中
for (int i = 0; i < n; i++) {
int x;
cin >> x;
se.insert(x);
}
//输出set中元素的个数
cout << se.size() << '\n';
//定义迭代器，循环输出set中的所有的数
set<int>::iterator it = se.begin();
for (it = se.begin(); it != se.end(); ++it) {
cout << *it << " ";
}
return 0;
}
View Code
[【模拟枚举】三连击]
【题意分析】
找到所有的三连击数，三个数刚好将1-9的数都用一遍，并且形成1：2：3的比例
【思路分析】
for循环枚举第一个数字是多少，其他数字分别是他的2倍，3倍，然后将每一个数字拆分开，判断是否有数字重复用到了。
函数拆解数字的每一位并且存入数组
从最小值123开始枚举到333(333的三倍是999)
清空统计数组
将三个数带入函数分解
定义标记，标记没出现重复的数
如果出现重复，那么标记为true
判断当前的数是否重复，如果没有重复则输出
【参考代码】
#include <iostream>
using namespace std;
int num[10];
//函数拆解数字的每一位并且存入数组
void solve(int x) {
while (x) {
num[x % 10]++;
x /= 10;
}
}
int main() {
//从最小值123开始枚举到333(333的三倍是999)
for (int i = 123; i <= 333; i++) {
//清空统计数组
for (int j = 1; j <= 9; j++) {
num[j] = 0;
}
//将三个数带入函数分解
solve(i);
solve(2 * i);
solve(3 * i);
//定义标记标记没出现重复的数
bool flag = false;
for (int j = 1; j <= 9; j++) {
//如果出现重复，那么标记为ture
if (num[j] != 1) {
flag = true;
break;
}
}
//判断当前的数是否重复，如果没有重复则输出
if (!flag) {
cout << i << " " << 2 * i << " " << 3 * i << '\n';
}
}
return 0;
}
View Code
本节课作业分析：
学系统中有视频解析和讲解哦
标签：set,07,标记,int,枚举,C++,素数,U3,数组 From： https://www.cnblogs.com/jayxuan/p/17936805