5算法的基本概念.ppt

1、一、复习引入,要把大象装冰箱，分几步？哈哈,问：,2.一个农夫带着一只狼、一头山羊和一篮蔬菜要过河，但只有一条小船。乘船时,农夫只能带一样东西。当农夫在场的时候,这三样东西相安无事，一旦农夫不在，狼会吃羊，羊会吃菜。请设计一个方案，使农夫能安全地将这三样东西带过河。,S1:农夫带羊过河;,S2:农夫独自回来;,S3:农夫带狼过河;,S4:农夫带羊回来;,S5:农夫带蔬菜过河;,S6:农夫独自回来;,S7:农夫带羊过河。,3如何发电子邮件？,第二步, 解得,第三步, - 2得 5y=3; ,第四步, 解得,你能写出解一般的二元一次方程组的步 骤吗？,第一步,第二步,解（3）得,思考,第四步,解（

2、4）得,第三步,第五步,得到方程组的解为,第一步：,第二步：,第三步：,-,1.1.1 算法的概念,这些明确的和有效的，而且能够在有限步之内完成的步骤就构成了的算法,算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必须是明确的和有效的，而且能够在有限步之内完成的。,三、概念形成,概念1.算法（algorithm）,注：一般来说，“算法通常可以编成计算机程序” 让计算机执行并解决问题。,2 算法的特征,有穷性： 一个算法应包含有限的操作步骤而不能是 无限的。,确定性： 算法中每一个步骤应当是确定的，而不能应当 是含糊的、模棱两可的。,有效性： 算法中每一个步骤应当能有效地执行，并得

3、到 确定的结果。,(1)自然语言:自然语言就是人们日常使用的语言,可以是汉语、英语或数学语言等.用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和转向,并且操作步骤较多时,就不那么直观清晰了.,(2)程序框图,(3)程序设计语言,1.1.2程序框图中讲解,1.2基本算法语句中讲解,3:描述算法可以有不同的方式,常用的有自然语言、程序框图、程序设计语言、伪代码等.,四、应用举例,例1.写出交换两个大小相同的杯子中的液体(A水、 B酒) 的一个算法。,S1：找一个大小与A相同的空杯子C。,四、应用举例,例1.写出交换两个大小相同的杯子中的液

4、体(A水、 B酒) 的一个算法。,S1：找一个大小与A相同的空杯子C。,S2：将A中的水倒入C中。,四、应用举例,例1.写出交换两个大小相同的杯子中的液体(A水、 B酒) 的一个算法。,S1：找一个大小与A相同的空杯子C。,S2：将A中的水倒入C中。,S3：将B中的酒精倒入A中。,S4:将C中的水倒入B中。,练习1. 给出求1+2+3+4+5+6的一个算法.,解法1.按照逐一相加的程序进行.,第一步:计算1+2,得3;,第二步:将第一步中的运算结果3与3相加得6;,第三步:将第二步中的运算结果6与4相加得10;,第四步:将第三步中的运算结果10与5相加得15;,第五步:将第四步中的运算结果15

5、与6相加得21.,例2.(1)设计一个算法判断7是否为质数.,第一步, 用2除7,得到余数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.(2)设计一个算法判断35是否为质数.,第一步, 用2除35,得到余数1.因为余数不为0， 所以2不能整除35.,第二步, 用3除35,得到余数2.因为余数不为0，

6、所以3不能整除35.,第三步, 用4除35,得到余数3.因为余数不为0， 所以4不能整除35.,第四步, 用5除35,得到余数0.因为余数为0， 所以5能整除35.因此，35不是质数.,变式1: “判断53是否质数”的算法如下： 第1步,用2除53得余数为1,余数不为0,所以2不能整除53; 第2步,用3除53得余数为2,余数不为0,所以3不能整除53; 第52步,用52除53得余数为1,余数不为0,故52不能整除53; 所以53是质数.,上述算法正确吗？说明理由。,变式2:任意给定一个大于1的整数n,试设计一个程序或步骤对n是否为质数做出判定.,分析:回顾这个问题的解题过程.,算法步骤:,第

7、一步:判断n是否等于2.,若n=2,则n是质数;,若n2,则执行第二步.,第二步:依次检验2(n-1)这些整数是不是n的约数,即是不是整除n的数.若有这样的数,则n不是质数;若没有这样的数,则n是质数.,第一步 给定大于2的整数n 第二步 令i =2 第三步 用i 除n得到余数r 第四步 判断“r=0”是否成立. 若是，则n不是质数，算法结束； 否则，将i的值增加1，仍用i表示. 第五步 判断“i(n-1)”是否成立. 若是，则n是质数，算法结束； 否则，返回第三步,算法步骤：,二分法,对于区间a,b 上连续不断、且 f(a)f(b)0的函数y=f(x),通过不断地 把函数f(x)的零点所在的

8、区间一分 为二，使区间的两个端点逐步逼近 零点，进而得到零点或其近似值的 方法叫做二分法.,第四步, 若f(a) f(m) 0,则含零点的区间为a,m；,第二步, 给定区间a,b,满足f(a) f(b)0,第三步, 取中间点,第五步,判断f(m)是否等于或者a,b的长度是否小于d，若是，则m是方程的近似解;否则，返回第三步,将新得到的含零点的区间仍然记为a,b.,否则，含零点的区间为m, b.,算法步骤： 第一步, 令 ,给定精确度d.,当d=0.005时，按照以上算法，可得下面表和图.,于是，开区间（1.4140625,1.41796875）中的实数都是当精确度为0.005时的原方程的近似解

9、.,练习2. 任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,算法步骤:,第一步:给定一个正实数r; 第二步:计算以r为半径的圆的面积S=r2; 第三步:得到圆的面积S.,练习3. 任意给定一个大于 1 的正整数 n ，设计一个算法求出 n 的所有因数.,算法步骤：,第一步, 依次以2 （n 1）为除数除 n ，检查余数是否为0；若是，则是 n 的因数；若不是，则不是 n 的因数；,第二步, 在 n 的因数中加入 1 和 n；,第三步, 输出n的所有因数.,第一步，给定一个大于1的正整数n. 第二步，令i=1. 第三步，用i除n,得到余数r. 第四步，判断“i=0”是否成立。若成立，则i是n的因数；否则，i不是n的因数。 第五步，使i的值增加1，仍用i表示。 第六步，判断”in”是否成立。若是，则结束算法：否则，返回到第三步。 第七步，输出n的所有因数。,练习4. 写出求一元二次方程 ax2+bx+c=0 的根的算法.,第一步,计算=b2-4ac.,第二步,如果0,则原方程无实数解 ;否则(0)时，,第三步:输出x1, x2或无实数解.,小结：,算法的特征是什么？,明确性,有效性,有限