1.2.1算法是“灵魂”

,主讲教师：丁志敏,143团第一中学,1.2.1算法是“灵魂”,教科版选修算法与程序设计,2019,目标,Study,01,进一步理解什么是算法,02,知道算法的多样性,03,能够对设计算法作出简单的评价,04,学会三种描述算法的方法,Partone,TRANSITIONPAGE,01,情景引入,课堂玩起来.,农夫过河问题,话说一位农夫带着一只狼、一只羊和一框蔬菜过河，无奈船小，农夫每次只能运送一样东西，考虑到狼吃羊、羊吃菜，因此运送的顺序至关重要。农夫怎么才可以让狼、羊、菜安全过河呢？,请同学们设计方案，帮助农夫实现“羊、狼、疏菜共同渡河”的愿望。,边玩边思考问题,01,02,03,方案总共有多少步？,顺序可以颠倒吗？,什么是算法?,各小组讨论后，先做到心中有数，暂不要说出答案！,Parttwo,TRANSITIONPAGE,02,新授,笔记做起来,新课讲授,1.算法概念,算法是解决问题的方法和步骤。,解决问题的过程，就是实现算法的过程。算法独立于任何具体的程序设计语言，一个算法可以用多种程序设计语言来实现。,计算机科学家尼克劳斯沃思,算法+数据结构=程序,知识扩展,世界上最早的算法,目前所知的世界上最早的算法是写在考古学家发掘出来的粘土板上的，这此粘土板的制作年代大约是在公元前3000年公元前1500年,也就是大约35005000年以前。考古学家是在靠近古代城市巴比伦的地方发现这些粘土板的，那里离现在的巴格达不远。巴比伦人发明了六十进制系统，我们现在关于时、分、秒的记法和关于角度的记法就是从他们那里学来的。为了做数学用表，巴比伦人需要解代数方程，他们的做法是写个求解的“算法”。在算法中，基本上都是对实际数目的计算。在算法的最后还写上一句短语，这个短语可以粗略地翻译为“这是一个过程”，这也是最早出现的关于程序设计语言的记号。,2.描述算法,用自然语言描述算法,用流程图描述算法,用伪代码描述算法,用自然语言表达算法，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。,流程图，也称为程序框图，它是算法的一种图形化表示方法。,伪代码是介于自然语言和计算机程序语言之间的一种算法描述。,算法描述之自然语言描述,步骤1：人和羊过河，人返回，留下羊,步骤2：人和狼过河，人和羊返回，留下狼,步骤3：人和菜过河，人返回，留下菜,步骤4：人和羊过河,优点：通俗易懂,缺点：缺乏直观性和简洁性,算法描述之流程图描述,历史典故“韩信点兵”秦朝末年，楚汉相争。有一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是，韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出1名；接着命令士兵5人一排，结果多出2名；他又命令士兵7人一排，结果又多出4名。韩信马上向将士们宣布：我军有1117名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振,最终打败楚军。请思考，韩信是如何算出总人数的呢？,分析问题,设所求的最小数为X，则X应满足：X整除3余1、x整除5余2、X整除7余4。,解题步骤（算法）,1、令X为1；2、如果X整除3余1，X整除5余2，X整除7余4，这就是题目要求的数，输出X的值（跳转4）；3、将X的值加1，然后调转2；4、如果算出，输出X值，否则跳转2；5、结束。,认识流程图符号,开始,输出X的值,X=X+1,X被3、5、7整除余数为1、2、4,用流程图描述算法,算法描述之伪代码描述,PrivateSubCommand1_Click()DimXAsInteger,YAsIntegerX=1DoIfXMod3=1AndXMod5=2AndXMod7=4ThenPrint“韩信统御最少兵数X=：;XExitDoEndIfX=X+1LoopEndSub,Mod是模运算，也叫求余运算。,算法描述之伪代码描述,PrivateSubCommand1_Click()DimXAsInteger,YAsIntegerX=1DoIfXMod3=1AndXMod5=2AndXMod7=4ThenX=X+105*10口决：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知Print韩信统御士兵数：;XExitDoEndIfX=X+1LoopEndSub,讨论交流,三种算法描述方法的比较,Partthree,TRANSITIONPAGE,03,综合训练,算法的优化,实践,一次数学课上，老师让学生练习算数。于是让他们一个小时内算出1+2+3+4+5+6+100的得数。全班只有高斯很快给出了答案，因为他想到了用（1+100）+（2+99）+（3+98）+（50+51）一共有50个101，所以50101就是1加到一百的得数。后来人们把这种简便算法称作高斯算法。模仿学过的用计算机程序解决问题的方法，设计一个算法，尝试求解高斯算法问题：1+2+3+4+5+6+100=？请分别用自然语言、流程图、伪代码表示。,高斯算法问题,借鉴前面的思路,1、令X为1；2、如果X整除3余1，X整除5余2，X整除7余4，这就是题目要求的数，输出X的值（跳转4）；3、将X的值加1，然后调转2；4、如果算出，输出X值，否则跳转2；5、结束。,Step1:将N的初始值赋为1,S的初始值赋为0；Step2:如果N小于等于100,转到Step3；Step3:将S加N的和赋给S；Step4:将N的值加1,转到Step2。,用伪代码描述,PrivateSubCommand1_Click()DimsAsString,nAsInteger,iAsIntegerFori=1To100n=n+iNextiPrint1+2+3+100=,nEndSub,用流程图描述,用自然语言描述,高斯算法问题,流程图描述,寻找更加优化的算法来解决问题提高执行效率,开始,结束,Partfour,TRANSITIONPAGE,04,作品评价,大家谈,小组作品量化评价表,个人目标自评表,Partfive,TRANSITIONPAGE,04,课堂小结,巩固提高,课堂小结,自然语言描述算法,通俗易懂，但缺乏直观性和简洁性，且易产生歧义。,流程图描述算法,形象、直观，易理解。,伪