算法的概念PPT课件.ppt

1、1.1.1算法的概念算法的概念（1）烧水泡茶问题：）烧水泡茶问题：解：烧水泡茶可分下面四步完成：解：烧水泡茶可分下面四步完成：第一步：洗好开水壶；第一步：洗好开水壶；第二步：灌好凉水，放在火上，等待水开；第二步：灌好凉水，放在火上，等待水开；第三步：洗好茶杯，茶杯里放好茶叶；第三步：洗好茶杯，茶杯里放好茶叶；第四步：水开后再冲水泡茶。第四步：水开后再冲水泡茶。（2）解二元一次方程组：2121xyxy 111222?a xb yca xb yc 一般二元一次方程组的解法步骤思考思考 在数学中，算法通常是指按照一定在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步规则解决某一类问题的

2、明确和有限的步骤。现在，算法通常可以编成计算机程骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。序，让计算机执行并解决问题。1.1.算法的概念算法的概念讲授新课2.2.算法的基本特征算法的基本特征: :明确性明确性、可行性、有限性、可行性、有限性、数据输入、信息输出、不唯一性。数据输入、信息输出、不唯一性。明确性明确性: :算法的每一步要做什么必须是明确的，算法的每一步要做什么必须是明确的，不能含糊不清、模棱两可不能含糊不清、模棱两可. . 可行性可行性: :算法的每一个步骤都能够通过基本运算法的每一个步骤都能够通过基本运算有效地进行算有效地进行, ,并得到确定的结果；对于相同的

3、并得到确定的结果；对于相同的输入输入, ,无论谁执行算法无论谁执行算法, ,都能够得到相同的最终都能够得到相同的最终结果结果有限性有限性: :算法必须由有限步组成算法必须由有限步组成, ,至少对某些输至少对某些输入入, ,算法应在有限多步内结束算法应在有限多步内结束, ,并给出计算结果并给出计算结果如果需要在无限步完成，就失去了实际意义。如果需要在无限步完成，就失去了实际意义。信息输出信息输出:一个算法至少要有一个有效的信一个算法至少要有一个有效的信息输出息输出,这就是问题求解的结果这就是问题求解的结果.不唯一性不唯一性:求解某一个题的解法不一定是唯求解某一个题的解法不一定是唯一的一的, 对于

4、一个问题可以有不同的算法对于一个问题可以有不同的算法.数据输入数据输入: :算法一定要根据输入的初始数据或算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤给定的初值才能正确执行它的每一步骤. .3.描述算法的一般步骤：描述算法的一般步骤： 输入数据输入数据.（若数据已知时，应用赋值；若数（若数据已知时，应用赋值；若数 据为任意未知时，应用输入）据为任意未知时，应用输入） 数据处理数据处理. 输出结果输出结果.4.4.算法的描述算法的描述: : 描述算法可以有不同的方式描述算法可以有不同的方式, ,常用的有常用的有自自然语言、程序框图、程序设计语言、伪代码然语言、程序框图、程序设

5、计语言、伪代码等等. .(1)(1)自然语言自然语言(2)(2)程序框图程序框图(3)(3)程序设计语言程序设计语言1.1.21.1.2程序框图程序框图中讲解中讲解1.21.2基本算法语句基本算法语句中讲解中讲解 自然语言就是人们日常使用的语言自然语言就是人们日常使用的语言, ,可以是汉语、可以是汉语、英语或数学语言等英语或数学语言等. .用自然语言描述算法的优点是通俗用自然语言描述算法的优点是通俗易懂易懂, ,当算法中的操作步骤都是顺序执行时比较容易理当算法中的操作步骤都是顺序执行时比较容易理解解. .缺点是如果算法中包含判断和转向缺点是如果算法中包含判断和转向, ,并且操作步骤并且操作步骤

6、较多时较多时, ,就不那么直观清晰了就不那么直观清晰了. .（1）设计一个算法，判断）设计一个算法，判断7是否为质数；是否为质数；（2）设计一个算法，判断）设计一个算法，判断35是否为质数；是否为质数；算法分析算法分析:(1)根据质数的定义，可以这样判断：依次用根据质数的定义，可以这样判断：依次用26除除7,如果它们中有一个能整除如果它们中有一个能整除7,则则7不是质数，否则是质数。不是质数，否则是质数。根据以上分析，可写出如下的算法：根据以上分析，可写出如下的算法：第一步，用第一步，用2除除7,得到余数得到余数1,因为余数不为因为余数不为0,所以所以2不能整除不能整除7.第二步，用第二步，用

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,因为余数不为因为

8、余数不为0,所以所以2不能整除不能整除35.第二步，用第二步，用3除除35,得到余数得到余数2,因为余数不为因为余数不为0,所以所以3不能整除不能整除35.第三步，用第三步，用4除除35,得到余数得到余数3,因为余数不为因为余数不为0,所以所以4不能整除不能整除35.第四步，用第四步，用5除除35,得到余数得到余数0,因为余数为因为余数为0,所以所以5能整除能整除35.因此，因此，35不是质数不是质数 .想一想想一想. .任意给定一个大于任意给定一个大于1 1的整数的整数n, ,试设计试设计一个程序或步骤对一个程序或步骤对n是否为质数做出判定是否为质数做出判定. .第一步：判断第一步：判断n是

9、否等于是否等于2.2.若若n=2=2，则，则n是质数；是质数；若若n2 2，则执行第二步，则执行第二步. .第二步第二步: :依次从依次从2 2（n1）检验是不是）检验是不是n的因的因数，即整除数，即整除n的数的数, ,若有这样的数，则若有这样的数，则n不是质不是质数；若没有这样的数，则数；若没有这样的数，则n是质数是质数. .评析评析: :这是判断一个大于这是判断一个大于1 1的整数的整数n是否为质是否为质数的最基本算法数的最基本算法. .讲授新课例例2.2.用二分法设计一个求方程用二分法设计一个求方程 x2-2=0 的近似根的近似根的算法的算法. .第一步：令第一步：令f(x)=x2-2，

10、因为，因为f(1)0,所所以设以设a=1,b=2.第二步：令第二步：令m= , 判断判断f(m)是否为是否为0.若是，若是，则则m为所求；若否，则继续判断为所求；若否，则继续判断f(a)f(m)大于大于0还是小于还是小于0.2ab 算法分析算法分析:回顾二分法解方程的过程回顾二分法解方程的过程,并假设所并假设所求近似根与精确解的差的绝对值不超过求近似根与精确解的差的绝对值不超过0.005,则不难设计出以下步骤：则不难设计出以下步骤：讲授新课第三步：若第三步：若f(a)f(m) 0，则令，则令a=m；否则，令；否则，令b=m.第四步第四步:判断判断 |a-b|0.005是否成立？若是，则是否成立

11、？若是，则a或或b(或任意值或任意值)为满足条件的近似根；若否，为满足条件的近似根；若否，则返回第二步则返回第二步.评析评析: :实际上实际上, ,上述步骤就是在求上述步骤就是在求 的近似值的近似值. .2 2讲授新课于是开区间中的实数都是满足假设条件的于是开区间中的实数都是满足假设条件的原方程的近似根原方程的近似根.1.1.任意给定一个正实数任意给定一个正实数, ,设计一个算法求以这个设计一个算法求以这个数为半径的圆的面积数为半径的圆的面积. .第一步第一步:输入任意一个正实数输入任意一个正实数r；第二步第二步:计算圆的面积计算圆的面积: S=r2;第三步第三步:输出圆的面积输出圆的面积S.

12、课堂练习2.2.任意给定一个大于任意给定一个大于1 1 的正整数的正整数n,n,设计一个算设计一个算法求出法求出n n的所有因数的所有因数. .第一步：依次以第一步：依次以2(n-1)为除数去除为除数去除n,检检查余数是否为查余数是否为0,若是若是,则是则是n的因数的因数;若不若不是是,则不是则不是n的因数的因数.第二步：在第二步：在n的因数中加入的因数中加入1和和n.第三步：输出第三步：输出n的所有因数的所有因数.课堂练习3.3.你要乘火车去外地办一件急事你要乘火车去外地办一件急事, ,请你写出从请你写出从自己房间出发到坐在车厢内的三步主要算法自己房间出发到坐在车厢内的三步主要算法. .第一

13、步第一步:去车站；去车站；第二步第二步:买车票买车票;第三步第三步:凭票上车对号入座凭票上车对号入座.课堂练习4.一个农夫带着一条狼、一头山羊和一篮蔬一个农夫带着一条狼、一头山羊和一篮蔬菜要过河菜要过河,但只有一条小船但只有一条小船.乘船时乘船时,农夫只能带农夫只能带一样东西一样东西.当农夫在场的时候当农夫在场的时候,这三样东西相安无这三样东西相安无事事.一旦农夫不在一旦农夫不在,狼会吃羊狼会吃羊,羊会吃菜羊会吃菜.请设计一请设计一个算法个算法,使农夫能安全地将这三样东西带过河使农夫能安全地将这三样东西带过河.第一步第一步: :农夫带羊过河农夫带羊过河; ;第二步第二步: :农夫独自回来农夫独

14、自回来; ;第三步第三步: :农夫带狼过河农夫带狼过河; ;第四步第四步: :农夫带羊回来农夫带羊回来; ;第五步第五步: :农夫带蔬菜过河农夫带蔬菜过河; ;第六步第六步: :农夫独自回来农夫独自回来; ;第七步第七步: :农夫带羊过河农夫带羊过河. . 现在河的岸边有三个人和三个鬼，河上只有现在河的岸边有三个人和三个鬼，河上只有一条小船，船上最多能坐两个一条小船，船上最多能坐两个“人人”，在河的任，在河的任何一边，当鬼的个数比人多时，鬼就会吃掉人。何一边，当鬼的个数比人多时，鬼就会吃掉人。请问如何才能使人和鬼都平安的到达对岸。请问如何才能使人和鬼都平安的到达对岸。人鬼过河：人鬼过河：解：解

15、： 要想使人鬼都安全过河，需要下面要想使人鬼都安全过河，需要下面11步。步。1235791146810【1】用自然语言描述求一元二次方程用自然语言描述求一元二次方程 ax2+bx+c=0 的根的算法的根的算法.第一步第一步:计算计算=b2-4ac;第二步第二步:如果如果0,则原方程无实数解则原方程无实数解 ;否则否则(0)时，时，,a2bx1 .a2bx2 第三步第三步:输出输出x1, x2或无实数解的信息或无实数解的信息.1.1.解方程解方程( (方程组方程组) )不等式的算法不等式的算法题型探究【2】写出解写出解 x2-4x+30 的算法的算法.第一步第一步:求出对应方程的根求出对应方程的

16、根1,3;第二步第二步:确定根的大小确定根的大小1 3 ;第三步第三步:写出解集写出解集x|1xmax,则则max=b;第四步第四步:如果如果cmax,则则max=c;第五步第五步:如果如果dmax,则则max=d;第六步第六步:输出输出max.题型探究点评点评: :算法要求算法要求“按部就班按部就班”地做地做, ,每做一步都每做一步都有唯一的结果有唯一的结果, ,且有限步之后总能得到结果且有限步之后总能得到结果. .1.1.知识结构知识结构算法的概念算法的概念算法的步骤算法的步骤 算法的特点算法的特点算法算法课堂小结2.2.算法的特点算法的特点: :思路简单清晰思路简单清晰, ,叙述复杂叙述

17、复杂, ,步骤步骤繁琐繁琐, ,计算量大计算量大, ,完全依靠人力难以完成完全依靠人力难以完成. .而这些而这些恰恰就是计算机的特长恰恰就是计算机的特长, ,它能不厌其烦地完成枯它能不厌其烦地完成枯燥的、重复的繁琐的工作燥的、重复的繁琐的工作. . 正因为这些正因为这些, ,现代算现代算法的作用之一就是使计算机代替人完成某些工法的作用之一就是使计算机代替人完成某些工作作, ,这也是我们学习算法的重要原因之一这也是我们学习算法的重要原因之一. .课堂小结3.3.设计设计算法的注意事项算法的注意事项: : (1)(1)认真分析问题认真分析问题, ,联系解决此问题的一般数学联系解决此问题的一般数学方

18、法方法; ;(2)(2)综合考虑此类问题中可能涉及的各种情况综合考虑此类问题中可能涉及的各种情况; ;(3)(3)借助有关的变量或参数对算法加以表达借助有关的变量或参数对算法加以表达; ;(4)(4)将解决问题的过程划分为若干个步骤将解决问题的过程划分为若干个步骤; ;(5)(5)然后用简练的语言将各个步骤表示出来然后用简练的语言将各个步骤表示出来. .课堂作业课本课本预习预习1.1.2程序框图程序框图1.1.算法的优化算法的优化:对于同一个问题对于同一个问题,有时可以有有时可以有不同的解题方法和步骤不同的解题方法和步骤.有的方法只需要较少有的方法只需要较少的步骤的步骤,而有些方法则可能需要较

19、多的步骤而有些方法则可能需要较多的步骤.一一般情况下般情况下,尽可能采用简单省时的和步骤少的尽可能采用简单省时的和步骤少的方法去解决问题方法去解决问题.因此因此,为了有效地解决问题为了有效地解决问题,不不仅需要保证算法正确仅需要保证算法正确,还要考虑算法的质量还要考虑算法的质量,这这就要求人们设计或选择合适的算法就要求人们设计或选择合适的算法.备课资料 我国著名数学家华罗庚在数学普及读物我国著名数学家华罗庚在数学普及读物统统筹方法平话及补充筹方法平话及补充中中, ,以以“泡茶泡茶”为例为例, ,阐述了阐述了设计和选择合适的、优化的算法的重要性设计和选择合适的、优化的算法的重要性. . 开水没有

20、开水没有,水壶要洗水壶要洗,茶壶和茶杯要洗茶壶和茶杯要洗;火已火已生了生了,茶叶也有了茶叶也有了,要想泡茶喝要想泡茶喝,怎么办？怎么办？甲甲:洗水壶洗水壶,灌凉水灌凉水,烧开水的过程中烧开水的过程中,洗茶壶、洗洗茶壶、洗茶杯、拿茶叶茶杯、拿茶叶,等水开了等水开了,泡茶喝泡茶喝.乙乙:洗水壶洗水壶,洗茶壶和茶杯、拿茶叶洗茶壶和茶杯、拿茶叶,一切就绪一切就绪,再再灌水烧水灌水烧水,等水开了等水开了,泡茶喝泡茶喝.丙丙:洗水壶洗水壶,灌凉水灌凉水,烧水烧水,等水开了等水开了,急急忙忙找茶急急忙忙找茶叶叶,洗茶壶洗茶壶,洗茶杯洗茶杯,泡茶喝泡茶喝.洗开洗开水壶水壶洗茶壶洗茶壶洗茶杯洗茶杯拿茶叶拿茶叶泡

21、茶泡茶喝喝烧开水烧开水烧开水烧开水洗茶洗茶壶壶洗茶洗茶杯杯拿茶拿茶叶叶洗开洗开水壶水壶灌凉灌凉水水泡茶泡茶喝喝烧开水烧开水洗开洗开水壶水壶灌凉灌凉水水泡茶泡茶喝喝洗茶洗茶壶壶洗茶洗茶杯杯拿茶拿茶叶叶灌凉灌凉水水 三种方法所用时间的比较三种方法所用时间的比较, ,显然是方法甲最显然是方法甲最省时间省时间. .水壶不洗水壶不洗, ,不能烧开水不能烧开水, ,因而洗水壶是烧因而洗水壶是烧开水的先决条件开水的先决条件. .没开水、不取茶叶、不洗茶壶没开水、不取茶叶、不洗茶壶和茶杯和茶杯, ,不能泡茶不能泡茶, ,因而这些又是泡茶的先决条件因而这些又是泡茶的先决条件. .要提高效率要提高效率, ,就要充

22、分利用就要充分利用“等水开等水开”的这段时的这段时间并行地进行其它工作间并行地进行其它工作, ,如洗茶杯、拿茶叶如洗茶杯、拿茶叶. .甲甲乙乙丙丙2.2.算法的分类算法的分类:(1)(1)对于数值性问题对于数值性问题,(,(如解方程如解方程, ,不等式不等式, ,套用公套用公式式, ,累加累加, ,累乘等累乘等) )可以建立数学模型可以建立数学模型, ,通过数学通过数学 语言来描述问题语言来描述问题; ;设计算法时设计算法时, ,可以采用数学分可以采用数学分析的方法进行处理析的方法进行处理, ,直接运用其中的现成的固定直接运用其中的现成的固定算法算法, ,也可以根据实际问题情景设计算法也可以根

23、据实际问题情景设计算法. . ,.数数值值性性问问题题非非数数值值性性问问题题(2)(2)对于非数值性问题对于非数值性问题, ,应建立过程模型应建立过程模型, ,通过过通过过程模型来描述算法程模型来描述算法; ;在设计算法时在设计算法时, ,可以根据过可以根据过程模型分析进行处理程模型分析进行处理, ,也可以选择一些成熟的办也可以选择一些成熟的办法进行处理法进行处理( (例如排序、资料检索、事务管理、例如排序、资料检索、事务管理、数据处理等数据处理等).).【1】在在9枚外观完全一样的金币中枚外观完全一样的金币中,有一枚是假有一枚是假的的,并且已知它比真金币稍轻并且已知它比真金币稍轻.现有一个

24、没有砝码现有一个没有砝码的天平的天平,你能设计一个算法把假金币找出来吗你能设计一个算法把假金币找出来吗?第一步第一步: :将将9 9枚金币平均分成三组枚金币平均分成三组, ,将其中两组将其中两组放在天平的两边放在天平的两边. . 如果天平平衡如果天平平衡, , 则假的金币则假的金币必定在另外一组必定在另外一组; ;如果天平不平衡如果天平不平衡, ,则假的金币则假的金币必定在较轻的一组必定在较轻的一组; ;第二步第二步: :将有假金币的一组金币中将有假金币的一组金币中, ,取出两枚金取出两枚金币币, ,分别放在天平的两边分别放在天平的两边. .如果天平平衡如果天平平衡, ,则假则假的金币必定是剩

25、余的的金币必定是剩余的; ;如果天平不平衡如果天平不平衡, ,则假的则假的金币必定在较轻的一边金币必定在较轻的一边. .【2】“鸡兔同笼鸡兔同笼”是我国隋朝时期的数学著作是我国隋朝时期的数学著作孙子算经孙子算经中的一个有趣而具有深远影响的中的一个有趣而具有深远影响的题目题目:“今有雉兔同笼今有雉兔同笼,上有三十五头上有三十五头,下有九十四下有九十四足足,问雉兔各几何问雉兔各几何.用方程组的思想不难解决这一用方程组的思想不难解决这一问题问题,请你设计一个这类问题的通用算法请你设计一个这类问题的通用算法.第一步第一步:输入总头数输入总头数H，总脚数，总脚数F； 第二步第二步:计算鸡的个数计算鸡的个

26、数 x=(4*HF)/ 2；第三步第三步:计算兔的个数计算兔的个数 y=(F2*H)/2； 第四步第四步:输出输出 x , y解解: 鸡兔同笼鸡兔同笼,设鸡兔总头数为设鸡兔总头数为H ,总脚数为总脚数为F,求求鸡兔各有多少只鸡兔各有多少只.算法如下：算法如下： 【3】已知一个学生的语文成绩为已知一个学生的语文成绩为89,数学成绩数学成绩为为96,外语成绩为外语成绩为99.求他的总分和平均成绩的一求他的总分和平均成绩的一个算法为：个算法为：第一步第一步:取取A=89 ,B =96 ,C=99 ；第四步第四步 输出计算的结果输出计算的结果第二步第二步: _；第四步第四步:输出计算的结果输出计算的结

27、果计算总分计算总分D=A+B+C第三步第三步: _；计算平均成绩计算平均成绩E=3D【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 中中,结束结

28、束.点评：一个算法往往具有代表性点评：一个算法往往具有代表性, ,能解决一类问能解决一类问题题, ,如如, ,例一可以例一可以 引申为引申为: :交换两个变量的值交换两个变量的值. .【5】著名数学家华罗庚著名数学家华罗庚“烧水泡茶的两个算法烧水泡茶的两个算法算法一：算法一：第一步第一步: 烧水烧水;第二步第二步: 水烧开后水烧开后,洗刷茶具；洗刷茶具；第三步第三步: 沏茶沏茶.算法二：算法二：第一步第一步:烧水烧水;第二步第二步: 烧水过程中烧水过程中,洗刷茶具洗刷茶具;第三步第三步 水烧开后沏茶水烧开后沏茶.这两个算法的区别在哪里？哪个算法更高效？这两个算法的区别在哪里？哪个算法更高效？第二个算法更高效第二个算法更高效.因为节约时间因为节约时间.1.1.1算法的概念算法的概念