第03课 算法设计 课件

对象数字关系C+C+A=C+10B+A+1=B+10B+1=AC+A=10A+1=10B+1=AA=9B=8C=1ABC未知未知未知？（5+6-3）×3=246×（5-3÷3）=246×（3×3-5）=24（6-3）×（5+3）=243×5+3+6=245×6-3-3=24怎么样才能把所有解法都找出来呢？获得所有可能的答案算法执教者：要在手机联系人里找到某个人，通常情况下，你会怎么做？w分治法（分而治之）把一个复杂的问题分成两个或n个相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解就是子问题的解的合并。分治法（分而治之）首字母分类查找从30张面值不等的钞票中抽出10张，怎样才能获得最多的价值？贪心算法做出当前的最优选择。就是通过局部的最优选择获得整体的最优选择。每次都选择现下的钞票中面值最大的，最后拿到的就是最优解。解析法枚举法分治法贪心算法动态规划算法经过大量的实践，人们发现了算法某些共性的规律，总结了经典的算法思想。合理地选择经典算法思想，可以为具体问题的解决设计出更加精妙的算法。……“鸡兔同笼”问题需要在一定范围内寻找正确解，可以使用枚举法。枚举法的思想是

，如果满足正确解的条件就采纳，否则继续枚举，做到不遗漏、不重复。在班级名单中查找符合条件的名字，通常我们会怎么做？认识枚举法一有序地尝试每一种可能的解9○13

○

7=100填上合适的＋－×÷使得等式成立。玩24点游戏时在头脑中罗列各种可能的算式在一篇文章中摘录好词好句用一串没有标记的钥匙打开教室的门，通常你会怎么做？认识枚举法一如果让计算机通过枚举法，从一串钥匙中找到打开教室对应的那一把钥匙，我们需要告诉计算机什么信息它才能停止查找？如果这把钥匙能打开教室门，就不用再往下尝试了。正确解的判断条件一共有几把钥匙【这样，计算机就知道一共要试几次了】确定枚举的范围枚举法的关键否否是是是枚举法流程图认识枚举法一为什么在登录网站、APP、ATM自动柜员机时，系统要限制用户输入密码的次数？认识枚举法一为什么在登录网站、APP、ATM自动柜员机时，系统要限制用户输入密码的次数？为了保护财产安全，防止犯罪分子利用枚举法的思想破解密码。算法框架的确定二在明确枚举法算法思想的基础上，使用具体的计算模型，合理选择控制结构，可以得到解决具体问题的算法框架，最终解决问题，找到答案。鸡兔同笼计算模型ji+tu=35ji×2+tu×4=940≤ji≤350≤tu≤35确定枚举的范围正确解的判断条件使用循环结构在0-35之间枚举ji或tu。使用分支结构判断是否满足正确解的条件如果……那么……重复执行……兔的只数（tu）鸡的只数（ji）总脚数是否满足正确解条件兔的只数（tu）0123535-035-135-20≤ji≤350≤tu≤35枚举兔的数量，完成表格的填写。ji+tu=35ji×2+tu×4=94确定枚举的范围正确解的判断条件……12……35-1235-35…………707274……94……140×××……√××鸡兔同笼算法的描述三

描述算法时，要精准地描述算法的每一步骤，明确算法的输入和输出。对于大部分算法来说，输入数据是必要的，但是有的算法不需要输入数据或者算法本身给定了初始条件。比如鸡兔同笼的问题，就可以把tu的值初始化为0，因为是从0开始罗列的。枚举兔的数量，“鸡兔同笼”算法描述：1.兔子只数从0开始罗列。2.确定枚举范围：兔子是在罗列范围内吗？3.如果超出罗列范围，那么结束；如果没有超出罗列范围，那么计算鸡的数量。4.正确解的判断条件：兔子和鸡的只数符合条件吗？5.如果符合条件，那么输出兔子和鸡的只数；6.如果不符合条件，那么罗列下一个。算法的描述三

除了枚举兔的数量，还可以枚举哪些数量？兔的脚数48……48……92鸡的脚数（94-4）÷2（94-8）÷2……（94-48）÷2……（94-92）÷2总只数4645……35……23是否满足正确解条件××……√……×枚举法1.枚举法的思想是

地尝试

的解。2.枚举法的关键是①

。