《算法和算法的描述(胡前贵).ppt》由会员分享，可在线阅读，更多相关《算法和算法的描述(胡前贵).ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、霍山中学胡前贵信息技术（选修信息技术（选修1 1）算法与程序设计）算法与程序设计第一章第二节第一章第二节算法和算法的描述计算机解决问题的过程计算机解决问题的过程分析问题分析问题设计算法设计算法编写程序编写程序调试程序调试程序霍山中学胡前贵学习、学习、生活中的算法生活中的算法过河游戏过河游戏问题如下：有一个牧羊人带着一头羊问题如下：有一个牧羊人带着一头羊,一只狼和一颗大白一只狼和一颗大白菜准备过河菜准备过河,他找到一只很小的船他找到一只很小的船,每次只能带一样东西过每次只能带一样东西过去去,可是如果让狼与羊单独在一起可是如果让狼与羊单独在一起,狼会吃羊狼会吃羊,让羊与白菜单让羊与白菜单独在一起独
2、在一起,羊会吃白菜，牧羊人应如何过河？羊会吃白菜，牧羊人应如何过河？霍山中学胡前贵结合过河游戏，思考并回答如下问题：结合过河游戏，思考并回答如下问题：1、这个方案总共有多少步？、这个方案总共有多少步？3、通过以上例子，我们能不能总结出什么是算法？、通过以上例子，我们能不能总结出什么是算法？2、第二步和第三步可以改变先后顺序，其它顺序还能、第二步和第三步可以改变先后顺序，其它顺序还能不能颠倒，比如说：第一步先过狼？不能颠倒，比如说：第一步先过狼？理解算法理解算法过河方案：过河方案：第一步：人和羊过河，人返回，留下羊；第一步：人和羊过河，人返回，留下羊；第二步：人和狼过河，人和羊返回，留下狼；第二
3、步：人和狼过河，人和羊返回，留下狼；第三步：人和菜过河，人返回，留下菜；第三步：人和菜过河，人返回，留下菜；第四步：人和羊过河。第四步：人和羊过河。霍山中学胡前贵算法算法的概念的概念通俗地说：算法就是用计算机解决某通俗地说：算法就是用计算机解决某一问题的一问题的步骤和方法，步骤和方法，是能被是能被机械地机械地执行执行的动作或指令的的动作或指令的有穷集合有穷集合。霍山中学胡前贵现实生活中的算法现实生活中的算法用银行自动取款机取款算法1插入银行卡2输入密码后按确定3若密码不正确，返回23选择取款项4输入金额后按确定5将钱取出6取回银行卡超市，收银员操作的算法1拿起顾客的挑选食品2用扫描器把条形码扫
4、描进计算机3若一个顾客的商品位扫描完继续第2步4计算机处理数据：单价、数量、总价5计算机打印给顾客总花费6顾客付钱营业员收钱找钱霍山中学胡前贵算法的特征算法的特征设给定的两个正整数m=112和n=64，利用辗转相除法，求它们的最大公约数。我们已经了解了算法的概念，接下来我们一起研究一下算法具备什么样的特征，以欧几里得算法为例，我们思考并归纳出算法特征：算法如下：（1）112除以64，余数为；（2）除以，余数为；（3）除以，余数为。答：112和64的最大公约数为。霍山中学胡前贵算法算法的特征的特征输入输入有穷性有穷性确定性确定性能行性能行性输出输出输入两个整数m和n（一个算法有零个或多个输入）输
5、出两个数的最大公约数（算法有一个或多个输出）有限个步骤之后完成最大公约数的计算步骤（1）中明确规定“m除以n”，而不能有类似“m除以n或n除以m”有两种可能的做法。算法的每个步骤都必须是基本的、能精确进行的。一个算法应该具有以下五个方面的重要特征：霍山中学胡前贵算法的描述：请用自然语言描述欧几里得算法算法的描述：请用自然语言描述欧几里得算法2、若r=0,则输出结果n,算法结束；否则，继 续步骤（3）。3、令m=n，n=r，并返回步骤（1）继续进行。1、以除以，令所得的余数为。霍山中学胡前贵这种描述方法通俗易懂，但有其局限性：语句一般很长、容易造这种描述方法通俗易懂，但有其局限性：语句一般很长、
6、容易造成歧义、复杂算法比较难清晰表示出来，也不方便翻译成计算机成歧义、复杂算法比较难清晰表示出来，也不方便翻译成计算机可以直接执行的程序设计语言。可以直接执行的程序设计语言。请问还有其他描述算法的方法吗？请问还有其他描述算法的方法吗？有没有更加清晰简洁的描述方式吗有没有更加清晰简洁的描述方式吗？自然语言描述算法的优缺点自然语言描述算法的优缺点霍山中学胡前贵开始开始r=0输入正整数输入正整数m和和nm=n，n=r输出输出n的值的值结束结束用流程图描述欧几里得算法用流程图描述欧几里得算法r=m除以除以n的余数的余数是是否否霍山中学胡前贵用流程图描述的算法清晰简洁，用流程图描述的算法清晰简洁，容易表
7、达复杂的算法，有利于转容易表达复杂的算法，有利于转化成不同的程序设计语言化成不同的程序设计语言用流程图描述算法的优点用流程图描述算法的优点霍山中学胡前贵流程图基本图形及其功能流程图基本图形及其功能霍山中学胡前贵用伪代码描述算法用伪代码描述算法用自然语言描述算法，通俗易懂，但有其局限性：容易造成歧义、用自然语言描述算法，通俗易懂，但有其局限性：容易造成歧义、语句一般很长、复杂算法比较难清晰表示出来，也不方便翻译成语句一般很长、复杂算法比较难清晰表示出来，也不方便翻译成程序设计语言程序设计语言用流程图描述的算法清晰简洁，容易表达复杂的算法，有利于转用流程图描述的算法清晰简洁，容易表达复杂的算法，有
8、利于转化成不同的程序设计语言化成不同的程序设计语言我们设计算法，目的是让计算机去处理数据，最终将计算的结果我们设计算法，目的是让计算机去处理数据，最终将计算的结果呈现给我们，为了更为方便地向程序设计语言过渡，人们也经常呈现给我们，为了更为方便地向程序设计语言过渡，人们也经常用伪代码描述算法：用伪代码描述算法：INPUT m，nR=m mod nDO while r0 m=r n=r r=m mod nLoopPRINT n霍山中学胡前贵描述算法的一些方法描述算法的一些方法自然语言自然语言流程图流程图伪代码伪代码NNS S框图框图PADPAD图图以上形式描述的算法，都不能直接被计算机执行，最终都
9、要转化成以上形式描述的算法，都不能直接被计算机执行，最终都要转化成计算机程序让计算机去执行。计算机程序让计算机去执行。霍山中学胡前贵 由求最大公约数问题、过河问题我们可以得知，由求最大公约数问题、过河问题我们可以得知，一个问题，可能有多种算法一个问题，可能有多种算法 ，应该通过分析、比较、，应该通过分析、比较、挑选一种最优的算法。一个好算法必须用到科学的方挑选一种最优的算法。一个好算法必须用到科学的方法法 ，应该好好学习各学科处理问题的科学方法。，应该好好学习各学科处理问题的科学方法。算法的择优算法的择优霍山中学胡前贵问题一：著名数学家华罗庚“烧水泡茶”的两个算法。算法一 第一步：烧水；第二步
10、：水烧开后，洗刷茶具；第三步：沏茶。算法二 第一步：烧水；第二步：烧水过程中，洗刷茶具；第三步：水烧开后沏茶。问题二：模仿第一节中调试程序的操作，运行P13探究（求两个整数9147485和5147480的最大公约数）两个程序，比较它们的效率，把观察到的现象填在表1-6中。算法的择优算法的择优霍山中学胡前贵小结小结算法的概念算法的特征算法的描述算法就是解决某一问题的步骤和方法输入、输出、确定性、有穷性、可行性输入、输出、确定性、有穷性、可行性自然语言、流程图、伪代码等自然语言、流程图、伪代码等下节课我们将开始学习下节课我们将开始学习用程序设计语用程序设计语言实现自己的算法言实现自己的算法，让计算机帮我们，让计算机帮我们解决现实生活中的难题解决现实生活中的难题霍山中学胡前贵课后讨论课后讨论 李汝珍笔上镜花缘中有这么一个故事：有一位才女叫米兰芬，有一天她和众姐妹在宗伯府聚会，来到小鳌山楼上观灯。楼下的灯有两种，一种是一个大球缀二个小球，一种是一大球缀四个小球。知道楼下有大灯球360个，小灯球1200个。让米兰芬计算，楼下的两面种灯各有多少盏？你能帮助米兰芬姑娘吗？霍山中学胡前贵THE ENDTHE ENDThanks very muchThanks very much