用穷举法求解问题的基本过程.ppt

粤教版高中信息技术选修一 第四章第四章 4.2.1凌源市实验中学凌源市实验中学 荀小雪荀小雪穷举法的定义 •穷举法，又叫枚举法，它将求解对象一一列举出来，然后逐一加以分析和处理，并验证结果是否满足给定的条件，列举完所有对象，问题将最终得到解决鸡翁一值钱鸡翁一值钱5，鸡母一值钱，鸡母一值钱3，鸡雏三值钱，鸡雏三值钱1百钱买百鸡，问鸡翁、鸡母和鸡雏百鸡，问鸡翁、鸡母和鸡雏各几何？各几何？ 参照穷举法的定义，思考解决百钱买百鸡的思路是什么？1、确定穷举对象、穷举对象范围和判定条件、确定穷举对象、穷举对象范围和判定条件2、一一列举可能的解，验证是否是可能的解、一一列举可能的解，验证是否是可能的解穷举对象•公鸡、母鸡、小鸡的个数 设公鸡数为设公鸡数为X X，母鸡数为，母鸡数为Y Y，小鸡数为，小鸡数为Z Z根据题目意思可知：根据题目意思可知：0 ≤ X ≤ 1000 ≤ X ≤ 1000 ≤ Y ≤ 1000 ≤ Y ≤ 1000 ≤ Z ≤ 1000 ≤ Z ≤ 100根据题目意思上式可优化为：根据题目意思上式可优化为：0 ≤ X ≤ 100 / 50 ≤ X ≤ 100 / 50 ≤ y ≤ 100 / 30 ≤ y ≤ 100 / 30 ≤ Z ≤ 99穷举对象的范围判定条件5 * x + 3 * y + 1 / 3 * z = 100Andx + y + z = 100 公鸡数公鸡数x=0母鸡数母鸡数y=小鸡数小鸡数z=若 5 * x + 3 * y + 1 / 3 * z = 100与 x + y + z = 100这两个条件成立,则输出x,y,z循环过程循环过程3 699900133 公鸡数公鸡数x=1流程图开始定义x,y,zX<=20 ?结 束Y<=33 ?Z<=99 ?百钱百鸡？输出结果NNNNYYYY（四）扩展探究，提高创新（四）扩展探究，提高创新•这个程序有什么地方可以改进？•这样改的理由是什么？•程序如何写？采用穷举法解题的基本思路1、确定穷举对象、穷举范围和判定条件2、一一列举可能的解，找出正确答案穷举法的使用范围 1、穷举范围是有限的，有明显的穷举范围2、有明显的判定条件3、一时找不到合适的解决途径（五）作业•经典题目：鸡兔同笼 一个笼子里有鸡和兔，现在只知道里面一共有35个头，94只脚，问鸡和兔各有多少只？感谢各位评委老师的指导！感谢各位评委老师的指导！制作人：荀小雪制作人：荀小雪单位：凌源市实验中学单位：凌源市实验中学。