学习目标
枚举算法意思示例
枚举重点
[【模拟枚举】水仙花数]
【题意分析】 我们需要找出区间内所有的水仙花数 【思路分析】 用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; }
埃式筛法
埃拉托斯特尼筛法（埃氏筛法）是一种用于找出一定范围内所有素数的古老算法，其基本思想是从小到大遍历自然数，将素数的倍数标记为合数，依此不断筛选，最终得到所有的素数。以下是埃氏筛法的详细步骤：
-
初始化： 从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; }
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; }
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; }
[【模拟枚举】三连击]
【题意分析】 找到所有的三连击数，三个数刚好将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; }
本节课作业分析：
学系统中有视频解析和讲解哦