算法和算法的描述(胡前贵).ppt

1、信息技术（选修1）算法与程序设计 第一章第二节,算法和算法的描述,计算机解决问题的过程,分析问题,设计算法,编写程序,调试程序,学习、生活中的算法,过河游戏,问题如下：有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？,结合过河游戏，思考并回答如下问题：,1、这个方案总共有多少步？,3、通过以上例子，我们能不能总结出什么是算法？,2、第二步和第三步可以改变先后顺序，其它顺序还能不能颠倒，比如说：第一步先过狼？,理解算法,过河方案： 第一步：人和羊过河，人返回，

2、留下羊； 第二步：人和狼过河，人和羊返回，留下狼； 第三步：人和菜过河，人返回，留下菜； 第四步：人和羊过河。,算法的概念,通俗地说：算法就是用计算机解决某一问题的步骤和方法，是能被机械地执行的动作或指令的有穷集合。,现实生活中的算法,用银行自动取款机取款算法1插入银行卡2输入密码后按确定 3若密码不正确，返回23选择取款项 4输入金额后按确定 5将钱取出 6取回银行卡,超市，收银员操作的算法1拿起顾客的挑选食品2用扫描器把条形码扫描进计算机3若一个顾客的商品位扫描完继续第2步 4计算机处理数据：单价、数量、总价5计算机打印给顾客总花费6顾客付钱营业员收钱找钱,算法的特征,设给定的两个正整数m

3、=112和n=64，利用辗转相除法，求它们的最大公约数。,我们已经了解了算法的概念，接下来我们一起研究一下算法具备什么样的特征，以欧几里得算法为例，我们思考并归纳出算法特征：,算法如下： （1）112除以64，余数为； （2）除以，余数为； （3）除以，余数为。 答：112和64的最大公约数为。,算法的特征,输入,有穷性,确定性,能行性,输出,输入两个整数m和n（一个算法有零个或多个输入）,输出两个数的最大公约数（算法有一个或多个输出）,有限个步骤之后完成最大公约数的计算,步骤（1）中明确规定“m除以n”，而不能有类似“m除以n或n除以m”有两种可能的做法。,算法的每个步骤都必须是基本的、能精

4、确进行的。,一个算法应该具有以下五个方面的重要特征：,算法的描述：请用自然语言描述欧几里得算法,2、若r=0,则输出结果n,算法结束；否则，继 续步骤（3）。,3、令m=n，n=r，并返回步骤（1）继续进行。,1、以除以，令所得的余数为。,这种描述方法通俗易懂，但有其局限性：语句一般很长、容易造成歧义、复杂算法比较难清晰表示出来，也不方便翻译成计算机可以直接执行的程序设计语言。,请问还有其他描述算法的方法吗？有没有更加清晰简洁的描述方式吗？,自然语言描述算法的优缺点,开始,r=0,输入正整数m和n,m=n，n=r,输出n的值,结束,用流程图描述欧几里得算法,r = m除以n的余数,是,否,用流

5、程图描述的算法清晰简洁，容易表达复杂的算法，有利于转化成不同的程序设计语言,用流程图描述算法的优点,流程图基本图形及其功能,用伪代码描述算法,用自然语言描述算法，通俗易懂，但有其局限性：容易造成歧义、 语句一般很长、复杂算法比较难清晰表示出来，也不方便翻译成 程序设计语言,用流程图描述的算法清晰简洁，容易表达复杂的算法，有利于转化成不同的程序设计语言,我们设计算法，目的是让计算机去处理数据，最终将计算的结果呈现给我们，为了更为方便地向程序设计语言过渡，人们也经常用伪代码描述算法：,INPUT m，n R=m mod n DO while r0 m=r n=r r=m mod n Loop PR

6、INT n,描述算法的一些方法,自然语言,流程图,伪代码,NS框图,PAD图,以上形式描述的算法，都不能直接被计算机执行，最终都要转化成计算机程序让计算机去执行。,由求最大公约数问题、过河问题我们可以得知，一个问题，可能有多种算法 ，应该通过分析、比较、挑选一种最优的算法。一个好算法必须用到科学的方法 ，应该好好学习各学科处理问题的科学方法。,算法的择优,问题一：著名数学家华罗庚“烧水泡茶”的两个算法。 算法一 第一步：烧水； 第二步：水烧开后，洗刷茶具； 第三步：沏茶。 算法二 第一步：烧水； 第二步：烧水过程中，洗刷茶具； 第三步：水烧开后沏茶。 问题二： 模仿第一节中调试程序的操作，运行P13探究（求两个整数9147485和5147480的最大公约数）两个程序，比较它们的效率，把观察到的现象填在表1-6中。,算法的择优,小结,算法的概念,算法的特征,算法的描述,算法就是解决某一问题的步骤和方法,输入、输出、确定性、有穷性、可行性,自然语言、流程图、伪代码等,下节课我们将开始学习用程序设计语言实现自己的算法，让计算机帮我们解决现实生活中的难题,课后讨论,李汝珍笔上镜花缘中有这么一个故事：有一位才女叫米兰芬，有一天她和众姐妹在宗伯府聚会，来到小鳌山楼上观灯。楼下的灯有两