111_算法的概念

第一章算法初步,1.1.1算法的概念,1.1算法与程序框图,解：,新课导入,烧水泡茶问题？,我们做任何事情都是在一定条件下按某种顺序执行的一系列操作。解决数学问题也是如此。例如：用加减消元法解二元一次方程组时，就可以按照某一步骤进行操作。,第二步,解得,第三步,-2得5y=3;,第四步,解得,你能写出解一般的二元一次方程组的步骤吗？,第一步,第二步,解（3）得,第四步,解（4）得,第三步,第五步,得到方程组的解为,在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤.现在，算法通常可以编成计算机程序，让计算机执行并解决问题.,2.算法的说明,1.算法的定义,3.算法的基本特征:,明确性:算法对每一个步骤都有确切的、非二义性的规定,即每一步对于利用算法解决问题的人或计算机来说都是可读的、可执行的,而不需要计算者临时动脑筋.,可行性:算法的每一个步骤都在有限时间内完成,并得到确定的结果,有限性:算法包含有限步操作组成,不能无限执行下去。,有输出:一个算法至少要有一个有效的信息输出,这就是问题求解的结果.,不唯一性:求解某一个题的解法不一定是唯一的,对于一个问题可以有不同的算法.,有序性:每一个步骤都是有序排列，执行时先后顺序一定.,通用性:解决一类问题.,例1.(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是质数.,例1.(2)设计一个算法判断35是否为质数.,第一步,用2除35,得到余数1.因为余数不为0，所以2不能整除35.,第二步,用3除35,得到余数2.因为余数不为0，所以3不能整除35.,第三步,用4除35,得到余数3.因为余数不为0，所以4不能整除35.,第四步,用5除35,得到余数0.因为余数为0，所以5能整除35.因此，35不是质数.,任意给定一个大于1的整数n,试设计一个程序或步骤对n是否为质数做出判定.,分析:回顾这个问题的解题过程.,算法步骤:,第一步:判断n是否等于2.,若n=2,则n是质数;,若n2,则执行第二步.,第二步:依次检验2(n-1)这些整数是不是n的约数,即是不是整除n的数.若有这样的数,则n不是质数;若没有这样的数,则n是质数.,例2：用二分法设计一个求方程的近似根的算法,对于区间a,b上连续不断、且f(a)f(b)0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点，进而得到零点或其近似值的方法叫做二分法。,二分法的基本思想：,分析：,第四步,若f(a)f(m)0,则含零点的区间为a,m；否则，含零点的区间为m,b.,第二步,给定区间a,b,满足f(a)f(b)0,第三步,取中间点,第五步,判断f(m)是否等于或者a,b的长度是否小于d，若是，则m是方程的近似解;否则，返回第三步,将新得到的含零点的仍然记为a,b.,第一步,令,给定精确度d.,算法步骤：,当d=0.005时，按照以上算法，可得下面表和图.,于是，开区间（1.4140625,1.41796875）中的实数都是当精确度为0.005时的原方程的近似解.,2.算法的特征是什么？,1.算法的概念,算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必须是明确的和有效的，而且能够在有限步之内完成的.,课堂小结,1.任意给定一个正实数