《穷举法解决问题》课件.ppt

情景导入情景导入•暑假我带着一个有三位数字的密码行李箱去旅行，旅行途中发现自己忘记了开锁的密码，但我还记得第一位密码是"7"，后面两位数字已经不记得，我该怎么办？ 模 拟§3.2 用穷举法解决问题用穷举法解决问题安徽师大附中安徽师大附中 叶国平叶国平什么是穷举法什么是穷举法•穷举法：也叫枚举法，列举法，它将求解对象一一列举出来，然后逐一加以分析、处理、并验证结果是否满足给定的条件，枚举完所有对象，问题将最终得以解决用穷举法解决问题的步骤用穷举法解决问题的步骤•Step1：分析问题•Step2：确定要枚举的求解对象，同时确定求解对象的枚举范围•Step3：一一枚举，然后加以分析、处理、验证举例：水仙花数举例：水仙花数•已知水仙花数满足以下两个条件p水仙花数是一个三位正整数p这个三位数刚好等于各个位上的数字立方和p例如：153就是一个水仙花数•编程输出所有的水仙花数举例：水仙花数举例：水仙花数•分析问题：假设这个三位数为m，那么p百位上的数字a为：p十位上的数字b为：p个位上的数字c为：•m满足的条件为:pm为三位数pm=a^3+b^3+c^3a=m\100b=(m-a*100)\10c=m mod 10举例：水仙花数举例：水仙花数•确定枚举的求解对象：p每一个三位数m•确定求解对象的枚举范围p100≤m≤999•验证的条件pm=a^3+b^3+c^3开始开始m=100m<=999?m=a3+b3+c3?输出输出m是是m=m+1否否求出百位数字求出百位数字a求出十位数字求出十位数字b求出个位数字求出个位数字c是是结束结束否否举例：水仙花数举例：水仙花数Private Sub Command1_Click() Dim m As Integer Dim a, b, c As Integer For m = _____ To _____'枚举三位数枚举三位数m a = m \ 100 '计算百位数字计算百位数字a b = (m - 100 * a) \ 10'计算十位数字计算十位数字b c = m Mod 10 '计算个位数字计算个位数字c If m = __________________ Then '验证条件验证条件 Print m & "是水仙花数" End If Next mEnd Sub运行程序100999a ^ 3 + b ^ 3 + c ^ 3举例：水仙花数举例：水仙花数•分析问题：假设这个三位数m的百位上数字为a，十位上数字为b，个位上数字为c，则：p这个三位数m=•a，b，c满足的条件为:p1≤a≤9p0≤b≤9p0≤c≤9pm=a^3+b^3+c^3a*100+b*10+c举例：水仙花数举例：水仙花数Ø确定枚举的求解对象：p百位数字ap十位数字bp个位数字cØ验证的条件pa*100+b*10+c=a^3+b^3+c^3Ø确定求解对象的范围p1≤a≤9p0≤b≤9p0≤c≤9Private Sub Command1_Click() Dim m As Integer Dim a, b, c As Integer For a = _____ To _____ '枚举百位数字枚举百位数字a For b=______ To ______ '枚举十位数字枚举十位数字b For c=______ To ______ '枚举个位数字枚举个位数字c m=a*100+b*10+c If m = __________________ Then '验证条件验证条件 Print m & "是水仙花数" End If Next c Next b Next aEnd Sub19a ^ 3 + b ^ 3 + c ^ 30909探究任务：百钱百鸡探究任务：百钱百鸡•用100元钱买100只鸡，公鸡，母鸡，小鸡都要有。

公鸡5元1只，母鸡3元1只，小鸡1元3只请问公鸡，母鸡，小鸡各应该买多少只？•编程输出每一种方案探究任务：百钱百鸡探究任务：百钱百鸡•分析问题：假设公鸡有a只，母鸡有b只，小鸡有c只，则a，b，c满足的条件为：pa,b,c均大于0pa+b+c=100p5*a+3*b+c/3=100探究任务：百钱百鸡探究任务：百钱百鸡Ø确定枚举的求解对象p公鸡只数ap母鸡只数bp小鸡只数cØ确定求解对象的范围p1≤a≤20p1≤b≤33p1≤c≤100Ø验证条件pa+b+c=100p5*a+3*b+c/3=100Private Sub Command1_Click() Dim a, b, c As Integer For a = ____ To ____ '枚举公鸡只数枚举公鸡只数 For b = ____ To ____ '枚举母鸡只数枚举母鸡只数 For c = ____ To _____ '枚举小鸡只数枚举小鸡只数 If (a + b + c = 100 And 5 * a + 3 * b + c \ 3 = 100) Then Print "公鸡："; a; "只", Print "母鸡："; b; "只", Print "小鸡："; c; "只" End If Next c Next b Next aEnd Sub运行程序/' '此行有一处错误此行有一处错误1201331100实践探究，深化思维实践探究，深化思维 •学校科技文化节之英语演讲大赛就要开始了，高二年级共有M=328名学生参赛。

比赛规则规定先进行小组比赛，然后取小组前三名进行决赛因此，组委会需要对参赛选手进行分组请按下面的分组规则设计算法，求解可能的分组方案供组委会参考p每组最少10人，最多30人p如果不能平均分组，则各小组间人数之差不得多于1人实践探究，深化思维实践探究，深化思维 •假设将M=328人进行分组，其中小组人数为15，则分组方案有______种，分别为：p___组____人/组，____组____人/组p___组____人/组，____组____人/组p___组____人/组，____组____人/组•假设将M=328人进行分组，分的组数为15组，则分组方案有______种，分别为：p___组____人/组，____组____人/组321420151714615815131612211322演讲比赛分组演讲比赛分组Ø确定枚举的求解对象：p小组的人数X或p小组的组数NØ确定求解对象的枚举范围p ≤N≤1132√演讲比赛分组演讲比赛分组Ø进行分组：pM=328分成N组p设X=M \ N，R=M mod N，如果R=0说明能平均分配；否则，将余数R人就要平均分配到R个组中，每组多分1个人，这样：pR=0时，分成N组，每组X个人；pR≠0时，分成N组，其中有 ______ 组X人，有 R 组 X+1+1人N-RPrivate Sub Command1_Click() Dim M, N,X, R As Integer M = 328 For N = ____ To _____ '枚举分得的组数枚举分得的组数 R = M Mod N X= M \ N If R = 0 Then Print "分成" & N; "组：平均每组" & X & "人。

" Else Print "分成" & N; "组：其中有" & N - R & "组每组" & X; "人，有" & R & "组每组" & X+1 & "人" End If Next NEnd Sub运行程序1132归纳总结归纳总结 •用穷举法解决问题的关键： p①确定需要枚举的所有求解对象 p②找出求解对象的枚举范围p③分析出满足问题所需的条件 •具体方法：p针对关键①，可以确定循环层数；p针对关键②，可以确定循环初值和终值；p针对关键③，可以确定循环体内的选择语句归纳总结归纳总结 •提出问题：我们使用信用卡在柜员机上取钱时，为什么系统要限制输入密码的次数？ 。