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

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