枚举法

看似很low,其实很强大!!!

枚举相关概念及性质

  • 应用范围:基于已有知识进行答案猜测的思想
  • 枚举思想: 猜测

使用枚举需确定三个问题

  1. 问题一 :
    确定解空间,建立简洁的数学模型(可能出现的情况的集合)
  2. 问题二 :
    利用所学知识以及题目中的条件减少变量取值范围
  3. 问题三 :
    依据题目确定正确的搜索顺序(搜索空间的遍历顺序要与模型中条件表达式一致)

枚举法举例

问题:求小于N的最大素数

  1. 问题一
    解空间为:
    (1)正整数
    (2)值大于2
    (3)n不能被[2,n)中任意一个素数整除(注意不是n不能被[2,n)中任意一个整数整除)
  2. 问题二
    优化解空间:
    除2以外的所有偶数,一定不是素数。
    即{2,2 i+1 |1<=i, 2 i+1 < n }
  3. 问题三
    对{2,2 i+1 |1<=i, 2 i+1 < n} 按照从小到大的顺序

请尝试如下题目

百鸡问题
鸡翁一值钱五, 鸡母一值钱三, 鸡雏三值钱一
百钱买百鸡, 问鸡翁, 鸡母, 鸡雏各几何


2019-7-17更新

题解:

  • 先构造可能的解的集合 S={(X,Y,Z)|0<=X,Y,Z<=100}
    X, Y, Z分别代表买公鸡, 母鸡和小鸡的只数
  • 然后验证条件X+Y+Z=100, 5X+3Y+Z/3=100
  • 复杂度: O(100^2)
  • 伪代码
      for (int x=0; x<=100; x++)
    for (int y=0 ; y<=100-x; y++){
    z = 100 - x - y;
    if (z % 3==0) then
    if (5*x+3*y+z/3==100)
    then (x,y,z) is solution
    }

谢谢访问