蓝桥备赛|常用算法之枚举法

vlambda
2022-03-25

蓝桥备赛|常用算法之枚举法

上次我们讲到蓝桥杯比赛比较常用的模拟法，这次我们来说一说另一种常用的方法：枚举法。说起暴力，我们大家最先想到一定是枚举，但是枚举真的是一门技术，怎么样把所有情况一个不落下的枚举出来是比较难的，所以我们今天给大家讲解一下枚举法。

枚举算法的思想：

将问题的所有可能成为答案的解一一列举，然后根据问题所给出的条件判断此解是否合适，如果合适就保留，反之则舍弃。

枚举算法解题的基本思路：

1.确定枚举解的范围，以及判断条件

2.选取合适枚举方法，进行逐一枚举，此时应注意能否覆盖所有的可能的解

3.在枚举时使用判断条件检验，留下所有符合要求的解。

枚举算法的一般步骤：

1.根据题目确定枚举的范围，并选取合适的枚举方式，不能遗漏任何一个真正解，同时避免重复。

2.为了提高解决问题的效率，看题目是否存在优化，将可能成为解的答案范围尽可能的缩小。

3.根据问题找到合理并、准确好描述并且好编码的验证条件。

4.枚举并判断是否符合第三步确定的的条件，并保存符合条件的解。

5.按要求输出枚举过程中留下的符合条件的解。

同样的，我们用蓝桥杯的真题来做讲解：

2019年省赛题目描述小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。请问，在 1 到 n 中，所有这样的数的和是多少输入描述输入格式：输入一行包含两个整数 n（1≤n≤10^4）。输出描述：输出一行，包含一个整数，表示满足条件的数的和。

问题分析：

本题我们只需要枚举出在n的范围内含有2、0、1、9的情况即可，枚举完成后求和。在此我们给出多种思路，读者可自行选择。

//C++解法，数字本身#include <iostream>using namespace std;bool check(int n){ while(n){ int s = n % 10; n /= 10; if(s == 1 || s == 2 || s == 9 || s == 0){ return true; break; } } return false;}int main(){ int m,sum = 0; cin>>m; for(int i = 1 ; i <= m ;i++){ if(check(i)) sum += i; } cout<<sum; return 0;}

//Java解法，Stringimport java.util.Scanner;public class Main { public static boolean check(int n){ String s = String.valueOf(n); for (int i = 0; i < s.length(); i++) { if(s.charAt(i)=='2'||s.charAt(i)=='0'||s.charAt(i)=='1'||s.charAt(i)=='9')return true; } return false; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); //在此输入您的代码... int n = scan.nextInt(); int ans=0; for (int i = 1; i <=n; i++) { if(check(i))ans+=i; } System.out.println(ans);
 scan.close(); }}

#Python解法，思路同C++n=int(input())l=['2','0','1','9']s=0def check(x): for i in str(x): if i in l: return True return False
for i in range(1,n+1): if check(i): s+=iprint(s)