算法及其实现.ppt

算法及其实现魏玉凤内容导航算法的概念算法的择优算法的描述有三个牧师和三个野人过河，只有一条有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险你能不能找数，那么牧师就会有危险你能不能找出一种安全的渡河方法让牧师和野人都出一种安全的渡河方法让牧师和野人都到了河对岸呢？到了河对岸呢？ 益智小游戏野人过河小组讨论•牧师如何过河？•有几种过河的方法？•每种方法的步骤？（要经历几步？）可能方法：•①①两个野人先过河，两个野人先过河， 一个野人回来；　　一个野人回来；　　•②②再两个野人过河，一再两个野人过河，一个野人回来；　　个野人回来；　　•③③两个牧师过河，一个两个牧师过河，一个野人和一个牧师回来；　　野人和一个牧师回来；　　•④④两个牧师过河，一个两个牧师过河，一个野人回来；　　野人回来；　　•⑤⑤两个野人过河，一个两个野人过河，一个野人回来；　　野人回来；　　•⑥⑥两个野人过河两个野人过河 第一步第一步:1:1人人,1,1鬼鬼, ,过河过河. . 第二步第二步:1:1人回人回, , 第三步第三步:2:2鬼鬼, ,过河过河 第四步第四步:1:1鬼回鬼回, , 第五步第五步:2:2人人, ,过河过河 第六步第六步:1:1人人,1,1鬼，回鬼，回. . 第七步第七步:2:2人过河人过河. . 第八步第八步:1:1鬼，回鬼，回. . 第九步第九步:2:2鬼鬼, ,过河过河 第十步第十步:1:1鬼，回鬼，回 第十一步第十一步:2:2鬼鬼, ,过河过河方法一方法二1.算法的概念•过河的方案就是这道趣味题的算法。

请同学们记住一句话：算法就是解决算法就是解决问题的方法和步骤问题的方法和步骤 •所谓“算法”就是解题方法的精确描述算法描述的是一种有穷的动作序列，即算法是由有限个步骤组成的上面这个小游戏告诉我上面这个小游戏告诉我们，们，要解决一个问题需要设要解决一个问题需要设计有限计有限个步骤来完成，这就是个步骤来完成，这就是算法在算法中，每一步动作在算法中，每一步动作的表示的表示形式并没有规定的格式，形式并没有规定的格式，可以可以是抽象的，也可以是具是抽象的，也可以是具体的算法的定义算法实战，案例拓展•李汝珍笔上《镜花缘》中有这么一个故事：有一位才女叫米兰芬，有一天她和众姐妹在宗伯府聚会，来到小鳌山楼上观灯楼下的灯有两种，一种是一个大球缀二个小球，一种是一大球缀四个小球知道楼下有大灯球360个，小灯球1200个让米兰芬计算，楼下的两种灯各有多少盏？　　•你能帮助米兰芬姑娘吗？ 《镜花缘》是一部与《西游记》、《封神榜》、《聊斋志异》同辉璀璨、带有浓厚神话色彩、浪漫幻想迷离的中国古典长篇小说 生活中的算法•概念：解决问题的方法和步骤•生活实例：菜谱、乐谱、产品使用说明书…•总结：同一个问题，解决算法可能有多同一个问题，解决算法可能有多种种，，有的步骤较为简单，而有的较为复杂。

一般情况下，尽可能采用简单省时的和步骤少的方法去解决问题，这就要求我们设计、选择合适的算法来解决问题2.算法的设计与择优算法的设计与择优 以“泡茶”为例，说明设计和选择合适的、优化的算法的重要性洗开水壶灌凉水拿茶叶洗茶杯洗茶壶泡茶喝烧开水•要想泡茶喝，当时的要想泡茶喝，当时的情况是：开水没有，情况是：开水没有，水壶要洗，茶壶和茶水壶要洗，茶壶和茶杯要洗；火已经生了，杯要洗；火已经生了，茶叶也有了，怎么泡茶叶也有了，怎么泡茶喝？茶喝？“泡茶”过程的步骤：洗开水壶洗茶壶洗茶杯拿茶叶灌凉水烧开水泡茶喝“泡茶”算法1洗开水壶灌凉水洗茶壶洗茶杯拿茶叶烧开水泡茶喝“泡茶”算法2tt•算法2最省时间保证算法正确的同时，要考虑算法的质量，设计出最优算法比一比，谁最快？•小明每天早上起床后，需要花费：淘米一分钟，烧早饭八分钟，漱口一分钟，洗脸一分钟，整理被子一分钟，早锻炼四分钟，然后吃早饭上学你觉得做好这几件事最快要几分钟？• 齐国的大将田忌很喜欢赛马有一回他和齐威王约定，进行一次比赛他们把各自的马分成上、中、下三等比赛的时候，上等马对上等马，中等马对中等到马，下等马对下等马由于齐威王每个等级的马都比田忌的强，三场比赛下来，田忌都失败了。

田忌觉得很扫兴，垂头丧气地准备离开马场这时，田忌发现，他的好朋友孙膑也在人群里孙膑招呼田忌过来，拍着他的肩膀，说：“你再同他赛一次，我有办法让你取胜• 赛马又开始了孙膑让田忌先用下等马对齐威王的上等马，第一场输了 接着进行第二场比赛孙膑让田忌拿上等马对齐威王的中等马，胜了第二场齐威王有点心慌了第三场，田忌拿中等马对齐威王的下等马，又胜了一场这下，齐威王目瞪口呆了比赛结果，田忌胜两场输一场，赢了齐威王还是原来的马，只是调换了一下出场顺序，就可以转败为胜可孙膑帮助田忌反败为胜的根本原因是什么呢？ 算法择优拓展《史记》田忌赛马•田忌反败为胜的关键就在于就在于采用了正确的策略策略就是总体上的程序性、步骤性的东西，是一种算法在这个故事中孙膑提出的赛马策略是比赛取得胜利的最优算法3、算法的表示•为了表示一个算法，可以用不同的形式，常用的算法表示形式有：自然语言、流程图和计算机语言自然语言、流程图和计算机语言三种•3种形式的算法可以相互转换•3种算法优缺点比较：算法优点缺点自然语言通俗易懂文字较多，易产生“歧义”流程图形象直观流程图符号运用易出错计算机语言编写方便比较抽象流程图基本符号的含义：•开始、结束框 ，表示算法的开始或结束。

•输入、输出框 ，表示输入、输出数据•判断框 ,表示条件判断及产生分支的情况•处理框 ，框中指出的是要处理的内容•流程线 ，有向线段，用于控制流程方向以“煮方便面”为例，分别给出算法的自然语言描述和流程图煮方便面算法：煮方便面算法：（（1）放入凉水）放入凉水（（2）开火）开火（（3）水烧开后放入面）水烧开后放入面（（4）加入调料和配料）加入调料和配料（（5）面熟出锅）面熟出锅 自然语言自然语言开始放入凉水开火水烧开后放入面加入调料和配料面熟出锅结束流程图•自主探究：给出下图算法，判断该算法的功能开始输入变量X、Y的值X>Y?Max=XMax=Y输出变量Max的值结束YN算法功能：求出两数的最大值，并输出探究任务：同学之间相互讨论，设计一个算法,对任意输入的三个整数X、Y和Z，找出其中的最大值，画出算法的流程图•设计思想：先比较X和Y，得到一个较大的值MAX，再用MAX与Z比较，将两者中较大的值作为结果输出即可。