枚举算法2.PPT

这里有6杯液体，内有几杯是糖水，其余为白水，由同学通过逐一品尝的方法找出前5杯中盛有糖水的杯子编号 从刚才的实验中，我们可以得出有一类问题可以采用一种有哪些信誉好的足球投注网站方法，在确定的范围内，考虑各种可能的情况，把所有的可能性一个个尝试过来，不遗漏、不重复，并对所得的结果逐一进行判断，过滤掉那些不合要求的，保留那些合乎要求的结果，这种方法叫做枚举法（enumerative algorithm）。 问题:在生活中还有哪些我们可以使用枚举法来解决的问题？ （练习一）用枚举法的思路，编写一个算法,判断并输出前5杯中盛有糖水的杯子编号。 * * 我也能做福尔摩斯——枚举法解题初步 【什么是枚举算法】 ................... P.21 枚举法是指： 按问题本身的性质，一一列举出该问题所有可能的解， 并在逐一列举的过程中，检验每个可能解是否是问题的真正解， 若是，我们采纳这个解，否则抛弃它。 在列举的过程中，既不能遗漏也不应重复。 开始 从第一杯开始 i←1 是不是5杯之内？ i=5 是否是糖水 Y N N 下一杯 i←i+1 Y 输出:i 结束 尝一下 举例：最近警方抓获一批制造发票的犯罪分子，并发现制造发票用的模版，但是由于受到损坏，它的千位和百位的数字已已经模糊不清，如下所示； 另一方面，我们知道这个数能被57 或67除尽。请设计一个算法，找出该单据原有的可能号码及个数。 （问题:）判断上述发票编号18847，16547，13447中哪些符合上述要求并说出理由。 （问题:）符合1□□47的5位数共有多少个？ 10047、10147、10247。。。19947因此得出结论100个 （练习二）请用枚举法的思路，设计一个算法，判断出所有符合 这些条件的5位编号枚举法的解题思路： 请先完成下列问题： 1、设置变量 2、循环变量的取值范围（10047=X=19947）； 分析： (1) 在这个5位数的千位和百位上，填上2个数字，则可以形成一个可能的 5位数解 —— X（10047～19947）。 (2) 将这未知的2个数字看作一个二位数 i ， 则 X=10047+i*100，而i 的取值范围是 [0,99] 。 (3) 判断当 i 取遍 [0,99] 时所得的每个 X 是否是真正解， 即 X 是否能被 57 或 67 整除。 (4) 若 X 是真正解，则输出 X 的值，并在计数器 C (记录解的个数) 中计数。