枚举算法的比较.pptVIP

虹口高级中学 陈文勤 按照问题本身的性质，一一列举出该问题所有可能的解， 在逐一列举的过程中，检验每个可能解是否为问题的真正解； 若是，则采纳这个解，否则抛弃它。在列举的过程中，既不能遗漏，也不应该重复。 可能解的范围 验证条件 逐一列举，既不遗漏，也不重复 枚举算法的含义 枚举算法的要素 实践体验： 用10元和50元两种纸币共同组成240元，求有哪些组合方式？ Dim X,Y,A For X=4 TO 19 For Y=1 TO 4 If 10*X+50*Y=240 then A=A X “,” Y CHR(13) Else End if Next Y Next X Msgbox A 纸币问题新算法 在这个算法中，有几个列举变量， 解的范围是多少？ 只有一个枚举对象 初值为4，终值为19 验证条件是什么？ Y\1=Y/1 Y是否为整数 纸币问题两种算法的比较 第一种 : 第二种: 纸币问题两种算法的比较 第二种 第一种 列举变量的数量 验证条件 纸币金额总和 是否为240元 50元纸币数量 是否为整数 2个列举变量， 需要使用双重循环结构 1个列举变量， 不需要使用双重循环结构 第一种 : 第二种: 原验证条件:10*X+50*Y=240 Y=(240-10*X)/50 X与Ｙ一一对应 验证50元纸币数量是整数， 即Y为整数 为什么可以减少列举变量？ N N Y 输出：X，Y X=X+1 Y 开始 X=1 X=45 结束 鸡兔同笼问题： 今有鸡兔同笼，有九十四足，问鸡兔各几何？ 对应关系？ 新验证条件？ 减少列举变量的依据 多个变量之间存在一种一一对应的关系 当变量X的值确定后，变量Y只存在唯一一个值； 验证此时变量Y的值是否符合实际需要，从而得到正确的解； 两种算法的特点 不一定需要多重循环 结构 第二种 容易从题目中获得 需要所有列举变量 第一种 验证条件难易度 循环结构复杂度 列举变量的数量 可以通过某种对应关系 从而减少列举变量 需要多重循环结构 需要从已知条件中 推导验证条件 第一种 : 第二种: