算法的概念课件.ppt

1、1.1.1算法的概念,随着科学技术的日新月异,算法学也得到了前所未有的发展,现在已经发展到了各个领域.有遗传算法,排序算法,加密算法,蚁群算法等,与生物学,计算机科学等有着很广泛的联系,尤其是在现在的航空航天中,更是有着更广泛的应用. 很多复杂的运算都是借助计算机和算法来完成的,在高端科学技术中有着很重要的地位.,把大象放进冰箱里需要几步？,1、把冰箱门打开 2、把大象装进去 3、把冰箱门关上,2000春晚小品钟点工,假如你参加一个猜商品价格的活动,只要在规定时间内大体猜出某商品的价格,就可获得该件商品（每猜一次，主持人会提醒你报价是高了还是低了）.现有一商品,价格在01400元之间,采取怎样

2、的策略才能在较短时间内说出大体答案呢?,第一步:报“700”；,第二步:若主持人说高了(说明答案在0700之间),就报“350”,否则(答数在350700之间)报“525”；,第三步:重复第二步的报数方法取中间数,直至得到大体答案., 解决实际问题需要程序和步骤，解决数学问题同样需要程序和步骤,第一步:2得: 5x=1 ,第二步: 解得:,第三步:-2得: 5y=3 ,第四步: 解得:,第五步:得到方程组的解为,你能写出与教材解法不同的求解步骤吗？,你能写出求一般二元一次方程组的步骤吗？,第三步:,第四步:解（4）得,第五步:得到方程组的解为,第一步:,第二步:解（3）得,一般地, 按照一定规

3、则解决某一类问题的明确和有限的步骤称为算法。,从广义的角度来看,并不是只有“计算”的问题才有算法,日常生活中处处都有.如乐谱是乐队演奏的算法,菜谱是做菜肴的算法,棋谱是下棋的算法.,它是解决某一类问题的程序或步骤；这些程序或步骤必须是明确有效的，而且能够在有限步之内完成；算法的设计尽量简单、步骤尽量少。,一.算法的概念,二.算法的基本特征:,明确性:算法中的每一步都应该是确定的,并且能有效地执行且得到确定的结果.,有限性:一个算法的步骤是有限的，它应在有限步操作之后停止，而不能是无限的,程序性:算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后续步骤，只有执行完前一步才能进行

4、下一步，并且每一步都要准确无误.,1下列关于算法的说法正确的是（ ） （A）某算法可以无止境地运算下去 （B）一个问题的算法步骤可以是可逆的 （C）完成一件事情的算法有且只有一种 （D）设计算法要本着简单、方便、可操作的原则,D,2下列运算中不属于我们所讨论算法范畴的是（ ）. A. 已知圆的半径求圆的面积 B. 从一副扑克牌随意抽取3张扑克牌抽到 24点的可能性 C. 已知坐标平面内的两点求直线的方程 D. 加减乘除运算法则,B,3.有人对歌德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了如下操作步骤：,第一步：检验6=3+3,第二步：检验8=3+5,第三步：检验10=5+5,。,

5、利用计算机不断地进行下去！,三.算法的表示方式：,自然语言就是人们日常使用的语言,可以是汉语、英语或数学语言等.用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和循环,并且操作步骤较多时,就不那么直观清晰了.,(1)自然语言（算法语言）,(2)程序框图,(3)程序设计语言,1.1.2程序框图中讲解,1.2基本算法语句中讲解,第一步：用2除7，得到余数1,所以2不能整除7.,第二步：用3除7，得到余数1,所以3不能整除7.,例1:（1）设计一个算法，判断7是否为质数？,第三步：用4除7，得到余数3,所以4不能整除7.,第四步：用5除7，得

6、到余数2,所以5不能整除7.,第五步：用6除7，得到余数1,所以6不能整除7.,因此，7是质数.,例1:（2）设计一个算法，判断35是否为质数？,第一步：用2除35，得到余数1,所以2不能整除35.,第二步：用3除35，得到余数2,所以3不能整除35.,第三步：用4除35，得到余数3,所以4不能整除35.,第四步：用5除35，得到余数0,所以5能整除35.,因此，35不是质数.,第一步：给定一个大于2的整数n；,第二步：令i=2；,第三步：用i除n，得到余数r；,第五步：判断“i(n-1)”是否成立.若是，则n是质数,结束算法；否则，返回第三步.,第四步：判断“r=0”是否成立.若是，则n 不

7、是质数,结束算法；否则，将i的值增加1，仍用i表示.,你能写出“判断整数n(n2)是否为质数”的算法吗？,教材P5:练习1.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,第一步：,第二步：,第三步：,给定一个正实数r；,计算S=r2;,得到圆的面积S.,教材P5：练习2.任意给定一个大于1的正整数n，设计一个算法求出n的所有因数.,第一步：,第二步：,第三步：,依次用2 （n 1）除 n ，,检查余数是否为0；,若是，则是 n 的因数；,若不是，则不是 n 的因数；,在 n 的因数中加入 1 和 n；,输出n的所有因数.,练习3:写出过P(a1,b1)、Q(a2,b2)两点直线

8、斜率的算法：,第一步：,第二步：,第三步：,取出横坐标a1，a2，纵坐标b1，b2；,若a1=a2,输出斜率不存在；,若a1a2,计算,第四步：,输出结果。,练习4.写出求一元二次方程 ax2+bx+c=0 的根的算法.,第一步:计算=b2-4ac.,第三步:输出x1, x2或无实数解的信息.,第二步:如果0,则原方程无实数解 ; 否则(0)时，,练习5：写出求1+2+3+4+5+6的一个算法。,解：算法1： 第一步：计算1+2得到3； 第二步：将第一步中的运算结果3与3相加得到6 第三步：将第二步中的运算结果6与4相加得到10 第四步：将第三步中的运算结果10与5相加得到15 第五步：将第四

9、步中的运算结果15与6相加得到21,算法2： 第一步：取n=6； 第二步：计算 第三步：输出运算结果。,算法3： 第一步： 将原式变形(1+6)+(2+5)+(3+4)=37； 第二步： 计算37； 第三步：输出运算结果。,例2.用二分法设计一个求方程 x2-2=0（x0） 的近似根的算法.(精确度为0.005),第一步：,第二步：,第三步：,第四步：,第五步：,令 ，,给定精确度d.,确定区间a，b，,满足f(a)f(b)0.,取区间中点,若f(a)f(m)0,则含零点的区间为,否则，含零点的区间为,将新得到的含零点的区间仍记为a,b;,判断|a-b|d是否成立或f(m)是否等于0.,若是，

10、则m是方程的近似解；,否则，返回,a,m,m，b.,第三步.,分析问题,对于区间a,b 上连续不断、且f(a)f(b)0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法.,二分法:,对于方程 ,给定d=0.005.,此步骤也是求的近似值的一个算法.,练习6:为了加强居民的节水意识,某市制订了以下生活用水收费标准:每户每月用水未超过7m3时,每立方米收费1.0元,并加收0.2元的城市污水处理费;超过7m3的部分,每立方米收费1.5元,并加收0.4元的城市污水处理费,请你写出某户居民每月应交纳的水费y(元)与用水量x(m3)之间的函数关系,然后设计一个求该函数值的算法.,解:y与x之间的函数关系为:,(当0 x7时) (当x7时),解:y与x之间的函数关系为:,(当0 x7时) (当x7时),求该函数值的算法分析:,第一步:输入每月用水量x; 第二步:判断x是否不超过7.若是,则y=1.2x;若否,则y=1.9x-4.9. 第三步:输出应交纳的水费y.,小结：,算法的特征是什么？,明确性,程序性,有限性,算法的概念：算法通常指可以用来解决的某 一类问题的步骤或程序，这些步骤或程序必须