《第03课 算法设计 课件》由会员分享，可在线阅读，更多相关《第03课 算法设计 课件（18页珍藏版）》请在金锄头文库上搜索。
1、,对象,数字,关 系,C+C+A=C+10,B+A+1=B+10,B+1=A,C+A=10,A+1=10,B+1=A,A=9,B=8,C=1,A,B,C,未知,未知,未知,？,（,5+6-3,）,3=24,6,（,5-33,）,=24,6,（,33-5,）,=24,（,6-3,）,（,5+3,）,=24,35+3+6=24,56-3-3=24,怎么样才能把所有解法都找出来呢？,获得所有可能的答案,算法,执教者：,要在手机联系人里找到某个人，通常情况下，你会怎么做？,w,分治法（分而治之）,把一个复杂的问题分成两个或,n,个相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的
2、直接求解，原问题的解就是子问题的解的合并。,分治法（分而治之）,首字母分类查找,从,30,张面值不等的钞票中抽出,10,张，怎样才能获得最多的价值？,贪心算法,做出当前的最优选择。就是通过局部的最优选择获得整体的最优选择。,每次都选择现下的钞票中面值最大的，最后拿到的就是最优解。,解析法,枚举法,分治法,贪心算法,动态规划算法,经过大量的实践，人们发现了算法某些共性的规律，总结了经典的算法思想。合理地选择经典算法思想，可以为具体问题的解决设计出更加精妙的算法。,“鸡兔同笼”问题需要在一定范围内寻找正确解，可以使用,枚举法,。,枚举法的思想是,，如果满足正确解的条件就采纳，否则继续枚举，做到不遗
3、漏、不重复。,在班级名单中查找符合条件的名字，通常我们会怎么做？,认识枚举法,一,有序地尝试每一种可能的解,9,13,7=100,填上合适的,使得等式成立。,玩,24,点游戏时在头脑中罗列各种可能的算式,在一篇文章中摘录好词好句,用一串没有标记的钥匙打开教室的门，通常你会怎么做？,认识枚举法,一,如果让计算机通过枚举法，从一串钥匙中找到打开教室对应的那一把钥匙，我们需要告诉计算机什么信息它才能停止查找？,如果这把钥匙能打开教室门，,就不用再往下尝试了。,正确解的判断条件,一共有几把钥匙,【,这样，计算机就知道一共要试几次了,】,确定枚举的范围,枚举法的,关键,否,否,是,是,是,枚举法流程图,
4、认识枚举法,一,为什么在登录网站、,APP,、,ATM,自动柜员机时，系统要限制用户输入密码的次数？,认识枚举法,一,为什么在登录网站、,APP,、,ATM,自动柜员机时，系统要限制用户输入密码的次数？,为了保护财产安全，防止犯罪分子利用枚举法的思想破解密码。,算法框架的确定,二,在明确枚举法算法思想的基础上，使用具体的计算模型，合理选择控制结构，可以得到解决具体问题的算法框架，最终解决问题，找到答案。,鸡兔同笼计算模型,ji+tu=35,ji2+tu 4=94,0,ji,35 0,tu,35,确定枚举的范围,正确解的判断条件,使用循环结构在,0-35,之间枚举,ji,或,tu,。,使用分支结
5、构判断是否满足正确解的条件,如果,那么,重复执行,兔的只数（,tu,）,鸡的只数（,ji,）,总脚数,是否满足正确解条件,兔的只数（,tu,）,0,1,2,35,35-0,35-1,35-2,0,ji,35 0,tu,35,枚举兔的数量，完成表格的填写。,ji+tu=35,ji2+tu4=94,确定枚举的范围,正确解的判断条件,12,35-12,35-35,70,72,74,94,140,鸡兔同笼,算法的描述,三,描述算法时，要精准地描述算法的每一步骤，明确算法的输入和输出。对于大部分算法来说，输入数据是必要的，但是有的算法不需要输入数据或者算法本身给定了初始条件。比如鸡兔同笼的问题，就可以把
6、,tu,的值初始化为,0,，因为是从,0,开始罗列的。,枚举兔的数量，“鸡兔同笼”算法描述：,1.,兔子只数从,0,开始罗列。,2.,确定枚举范围,：兔子是在罗列范围内吗？,3.,如果超出罗列范围，那么结束；如果没有超出罗列范围，那么计算鸡的数量。,4.,正确解的判断条件,：兔子和鸡的只数符合条件吗？,5.,如果符合条件，那么输出兔子和鸡的只数；,6.,如果不符合条件，那么罗列下一个。,算法的描述,三,除了枚举兔的数量，还可以枚举哪些数量？,兔的脚数,4,8,48,92,鸡的脚数,（,94-4,）,2,（,94-8,）,2,（,94-48,）,2,（,94-92,）,2,总只数,46,45,35,23,是否满足正确解条件,枚举法,1.,枚举法的思想是,地尝试,的,解。,2.,枚举法的关键是,。,。,有序,每一种可能,确定枚举的范围,正确解的判断条件,
