暴力枚举

在数学和计算机科学理论中,一个集的枚举是列出某些有穷序列集的所有成员的程序,或者是一种特定类型对象的计数。这两种类型经常(但不总是)重叠。

何钦铭,颜晖 .C语言程序设计(第3版):高等教育出版社,2015

枚举

在算法竞赛中,枚举常常用来解决最简单的问题。列出这个问题的全部可能的解(符合一个条件),并在之后的判定中,检验每个可能的解是否是问题的最终需要的正确解(符合全部条件)。

作为最直观也是最易于上手的方法,枚举法 可以解决这样的问题:

  • 需要枚举的范围是有限的,而且往往不会特别特别大。
  • 拥有明确且固定的检验条件。

Sample 【2016年 第七届 蓝桥杯 省赛 C/C++ 大学A组 第 1 题】
某君新认识一网友。当问及年龄时,他的网友说:“我的年龄是个 2 位数,我比儿子大27岁,如果把我的年龄的两位数字交换位置,刚好就是我儿子的年龄。”
请你计算:网友的年龄一共有多少种可能情况?
提示:30岁就是其中一种可能哦。
请填写表示可能情况的种数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

首先,需要枚举的范围是有限的。由于某君网友的年龄是个 2 位数,因此年龄的范围是 [10,99] 内的所有整数(int)。
其次,有明确固定的检验条件。枚举年龄的个位与十位交换,如果比原数字小 27,那么它就是真正的解。
因此,这套方法在代码中实现的结构就可以明确为:枚举范围循环+条件判断语句

到目前为止,这个问题的代码便很容易写出来了。这里给出 C/C++ 和 Java 的两个版本的代码:

#include <stdio.h>

int main()
{
    int var = 0; // 记录所有解的个数

    // 循环枚举的范围
    for(int i = 10; i <= 99; i++){
        // 条件判断
        if(i - (i % 10 * 10 + i / 10) == 27){
            var++;
        }
    }
    printf("%dn", var);
    return 0;
}

C++ 版本

class Main{
    public static void main(String[] argv){
        int var = 0; // 记录所有解的个数

        // 循环枚举的范围
        for(int i = 10; i <= 99; i++){
            // 条件判断
            if(i - (i % 10 * 10 + i / 10) == 27){
                var++;
            }
        }
        System.out.println(var);
    }
}

Java 版本

下面将会展示部分例题。

你可以考虑如何实现并完成代码编辑和运行。所给的原始代码并非标准答案。

你需要注意的是,在暴力破解的题目中,一般能尽快写出代码为好。在遇到长难复杂的情况,考场的计算机所搭载的 CPU 可能并不会很快得出答案,但是也不会影响你继续使用其它编译器做题。因此,保证你能获得的代码不至于消耗特别长时间的情况下,只要可以得出正解的代码,便已经达标。

页面: 1 2 3 4 5 6

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注