《算法的概念课件.ppt》由会员分享，可在线阅读，更多相关《算法的概念课件.ppt（34页珍藏版）》请在三一办公上搜索。
1、1.1.1算法的概念,（1）烧水泡茶问题：,解：烧水泡茶可分下面四步完成：第一步：洗好开水壶；第二步：灌好凉水，放在火上，等待水开；第三步：洗好茶杯，茶杯里放好茶叶；第四步：水开后再冲水泡茶。,（2）解二元一次方程组：,思考,在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。,1.算法的概念,讲授新课,2.算法的基本特征:明确性、可行性、有限性、数据输入、信息输出、不唯一性。,明确性:算法的每一步要做什么必须是明确的，不能含糊不清、模棱两可.,可行性:算法的每一个步骤都能够通过基本运算有效地进行,并得到确定的结果；对于
2、相同的输入,无论谁执行算法,都能够得到相同的最终结果,有限性:算法必须由有限步组成,至少对某些输入,算法应在有限多步内结束,并给出计算结果如果需要在无限步完成，就失去了实际意义。,信息输出:一个算法至少要有一个有效的信息输出,这就是问题求解的结果.,不唯一性:求解某一个题的解法不一定是唯一的, 对于一个问题可以有不同的算法.,数据输入:算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤.,3.描述算法的一般步骤： 输入数据.（若数据已知时，应用赋值；若数 据为任意未知时，应用输入） 数据处理. 输出结果.,4.算法的描述:,描述算法可以有不同的方式,常用的有自然语言、程序框图、程
3、序设计语言、伪代码等.,(1)自然语言,(2)程序框图,(3)程序设计语言,1.1.2程序框图中讲解,1.2基本算法语句中讲解,自然语言就是人们日常使用的语言,可以是汉语、英语或数学语言等.用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和转向,并且操作步骤较多时,就不那么直观清晰了.,（1）设计一个算法，判断7是否为质数；,（2）设计一个算法，判断35是否为质数；,算法分析:(1)根据质数的定义，可以这样判断：依次用26除7,如果它们中有一个能整除7,则7不是质数，否则是质数。根据以上分析，可写出如下的算法：第一步，用2除7,得到余数
4、1,因为余数不为0,所以2不能整除7.第二步，用3除7,得到余数1,因为余数不为0,所以3不能整除7.第三步，用4除7,得到余数3,因为余数不为0,所以4不能整除7.第四步，用5除7,得到余数2,因为余数不为0,所以5不能整除7.第五步，用6除7,得到余数1,因为余数不为0,所以6不能整除7.因此，7是质数 .,(2) 类似地，可写出“判断35是否为质数”的算法：第一步，用2除35,得到余数1,因为余数不为0,所以2不能整除35.第二步，用3除35,得到余数2,因为余数不为0,所以3不能整除35.第三步，用4除35,得到余数3,因为余数不为0,所以4不能整除35.第四步，用5除35,得到余数0
5、,因为余数为0,所以5能整除35.因此，35不是质数 .,想一想.任意给定一个大于1的整数n,试设计一个程序或步骤对n是否为质数做出判定.,第一步：判断n是否等于2.若n=2，则n是质数；若n2，则执行第二步.,第二步:依次从2（n1）检验是不是n的因数，即整除n的数,若有这样的数，则n不是质数；若没有这样的数，则n是质数.,评析:这是判断一个大于1的整数n是否为质数的最基本算法.,讲授新课,例2.用二分法设计一个求方程 x2-2=0 的近似根的算法.,第一步：令f(x)=x2-2，因为f(1)0,所以设a=1,b=2.,第二步：令m= , 判断f(m)是否为0.若是，则m为所求；若否，则继续
6、判断f(a)f(m)大于0还是小于0.,算法分析:回顾二分法解方程的过程,并假设所求近似根与精确解的差的绝对值不超过0.005,则不难设计出以下步骤：,讲授新课,第三步：若f(a)f(m) 0，则令a=m；否则，令b=m.,第四步:判断 |a-b|0.005是否成立？若是，则a或b(或任意值)为满足条件的近似根；若否，则返回第二步.,评析:实际上,上述步骤就是在求 的近似值.,讲授新课,于是开区间中的实数都是满足假设条件的原方程的近似根.,1.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,第一步:输入任意一个正实数r；,第二步:计算圆的面积: S=r2;,第三步:输出圆的面积S
7、.,课堂练习,2.任意给定一个大于1 的正整数n,设计一个算法求出n的所有因数.,第一步：依次以2(n-1)为除数去除n,检查余数是否为0,若是,则是n的因数;若不是,则不是n的因数.,第二步：在n的因数中加入1和n.,第三步：输出n的所有因数.,课堂练习,3.你要乘火车去外地办一件急事,请你写出从自己房间出发到坐在车厢内的三步主要算法.,第一步:去车站；,第二步:买车票;,第三步:凭票上车对号入座.,课堂练习,4.一个农夫带着一条狼、一头山羊和一篮蔬菜要过河,但只有一条小船.乘船时,农夫只能带一样东西.当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃菜.请设计一个算法,使
8、农夫能安全地将这三样东西带过河.,第一步:农夫带羊过河;,第二步:农夫独自回来;,第三步:农夫带狼过河;,第四步:农夫带羊回来;,第五步:农夫带蔬菜过河;,第六步:农夫独自回来;,第七步:农夫带羊过河.,现在河的岸边有三个人和三个鬼，河上只有一条小船，船上最多能坐两个“人”，在河的任何一边，当鬼的个数比人多时，鬼就会吃掉人。请问如何才能使人和鬼都平安的到达对岸。,人鬼过河：,解： 要想使人鬼都安全过河，需要下面11步。,1,2,3,5,7,9,11,4,6,8,10,【1】用自然语言描述求一元二次方程 ax2+bx+c=0 的根的算法.,第一步:计算=b2-4ac;,第二步:如果0,则原方程无
9、实数解 ;否则(0)时，,第三步:输出x1, x2或无实数解的信息.,1.解方程(方程组)不等式的算法,题型探究,【2】写出解 x2-4x+30 的算法.,第一步:求出对应方程的根1,3;,第二步:确定根的大小1 3 ;,第三步:写出解集x|1x3.,题型探究,【6】写出一个能找出在a,b,c,d四个数中最大的数的算法.,第一步:输入a,b,c,d四个数;,第二步:max=a;,第三步:如果bmax,则max=b;,第四步:如果cmax,则max=c;,第五步:如果dmax,则max=d;,第六步:输出max.,题型探究,点评:算法要求“按部就班”地做,每做一步都有唯一的结果,且有限步之后总能
10、得到结果.,1.知识结构,算法的概念,算法的步骤,算法的特点,算法,课堂小结,2.算法的特点:思路简单清晰,叙述复杂,步骤繁琐,计算量大,完全依靠人力难以完成.而这些恰恰就是计算机的特长,它能不厌其烦地完成枯燥的、重复的繁琐的工作. 正因为这些,现代算法的作用之一就是使计算机代替人完成某些工作,这也是我们学习算法的重要原因之一.,课堂小结,3.设计算法的注意事项: (1)认真分析问题,联系解决此问题的一般数学方法;(2)综合考虑此类问题中可能涉及的各种情况;(3)借助有关的变量或参数对算法加以表达;(4)将解决问题的过程划分为若干个步骤;(5)然后用简练的语言将各个步骤表示出来.,课堂作业,课
11、本预习1.1.2程序框图,再见,1.算法的优化:对于同一个问题,有时可以有不同的解题方法和步骤.有的方法只需要较少的步骤,而有些方法则可能需要较多的步骤.一般情况下,尽可能采用简单省时的和步骤少的方法去解决问题.因此,为了有效地解决问题,不仅需要保证算法正确,还要考虑算法的质量,这就要求人们设计或选择合适的算法.,备课资料,我国著名数学家华罗庚在数学普及读物统筹方法平话及补充中,以“泡茶”为例,阐述了设计和选择合适的、优化的算法的重要性.,开水没有,水壶要洗,茶壶和茶杯要洗;火已生了,茶叶也有了,要想泡茶喝,怎么办？,甲:洗水壶,灌凉水,烧开水的过程中,洗茶壶、洗茶杯、拿茶叶,等水开了,泡茶喝
12、.,乙:洗水壶,洗茶壶和茶杯、拿茶叶,一切就绪,再灌水烧水,等水开了,泡茶喝.,丙:洗水壶,灌凉水,烧水,等水开了,急急忙忙找茶叶,洗茶壶,洗茶杯,泡茶喝.,洗开水壶,洗茶壶,洗茶杯,拿茶叶,泡茶喝,烧开水,烧开水,洗茶壶,洗茶杯,拿茶叶,洗开水壶,灌凉水,泡茶喝,烧开水,洗开水壶,灌凉水,泡茶喝,洗茶壶,洗茶杯,拿茶叶,灌凉水,三种方法所用时间的比较,显然是方法甲最省时间.水壶不洗,不能烧开水,因而洗水壶是烧开水的先决条件.没开水、不取茶叶、不洗茶壶和茶杯,不能泡茶,因而这些又是泡茶的先决条件.要提高效率,就要充分利用“等水开”的这段时间并行地进行其它工作,如洗茶杯、拿茶叶.,甲,乙,丙,2
13、.算法的分类:,(1)对于数值性问题,(如解方程,不等式,套用公式,累加,累乘等)可以建立数学模型,通过数学 语言来描述问题;设计算法时,可以采用数学分析的方法进行处理,直接运用其中的现成的固定算法,也可以根据实际问题情景设计算法.,(2)对于非数值性问题,应建立过程模型,通过过程模型来描述算法;在设计算法时,可以根据过程模型分析进行处理,也可以选择一些成熟的办法进行处理(例如排序、资料检索、事务管理、数据处理等).,【1】在9枚外观完全一样的金币中,有一枚是假的,并且已知它比真金币稍轻.现有一个没有砝码的天平,你能设计一个算法把假金币找出来吗?,第一步:将9枚金币平均分成三组,将其中两组放在
14、天平的两边. 如果天平平衡, 则假的金币必定在另外一组;如果天平不平衡,则假的金币必定在较轻的一组;,第二步:将有假金币的一组金币中,取出两枚金币,分别放在天平的两边.如果天平平衡,则假的金币必定是剩余的;如果天平不平衡,则假的金币必定在较轻的一边.,【2】“鸡兔同笼”是我国隋朝时期的数学著作孙子算经中的一个有趣而具有深远影响的题目:“今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何.用方程组的思想不难解决这一问题,请你设计一个这类问题的通用算法.,第一步:输入总头数H，总脚数F； 第二步:计算鸡的个数 x=(4*HF)/ 2；第三步:计算兔的个数 y=(F2*H)/2； 第四步:输出
15、x , y,解: 鸡兔同笼,设鸡兔总头数为H ,总脚数为F,求鸡兔各有多少只.算法如下：,【3】已知一个学生的语文成绩为89,数学成绩为96,外语成绩为99.求他的总分和平均成绩的一个算法为：第一步:取A=89 ,B =96 ,C=99 ；,第四步 输出计算的结果,第二步: _；,第四步:输出计算的结果,计算总分D=A+B+C,第三步: _；,计算平均成绩E=,【4】写出交换两个大小相同的杯子中的液体(A 水、 B 酒) 的两个算法,S1:找一个大小与A相同的空杯子C;S2:将A 中的水倒入C中;S3:将B中的酒精倒入A中;S4:将C中的水倒入B中,结束.,S1:找两个空杯子C和DS2:将A中的水倒入C 中,将B中的酒倒入D中；S3:将C中的水倒入B中,将D中的酒倒入A 中,结束.,点评：一个算法往往具有代表性,能解决一类问题,如,例一可以 引申为:交换两个变量的值.,【5】著名数学家华罗庚“烧水泡茶的两个算法算法一：第一步: 烧水;第二步: 水烧开后,洗刷茶具；第三步: 沏茶.算法二：第一步:烧水;第二步: 烧水过程中,洗刷茶具;第三步 水烧开后沏茶.这两个算法的区别在哪里？哪个算法更高效？,第二个算法更高效.因为节约时间.,课件部分内容来源于网络，如对内容有异议或侵权的请及时联系删除！此课件可编辑版，请放心使用！,.,
