111算法的概念.ppt

1、第一章 算法初步,1.1.1 算法的概念,问： 要把大象装进冰箱，分几步？,第一步 把冰箱门打开; 第二步 把大象放进冰箱; 第三步 把冰箱门关上。,要把大象装进冰箱，分三步,假如你的朋友不会发电子邮件，你能教会他吗？可以按什么步骤操作？,问题情境,“鸡兔同笼”是我国隋朝时期的数学著作孙子算经中的一个有趣而具有深远影响的题目： “今有鸡兔同笼，上有一十七头，下有四十八足，问：鸡兔各几何？”,第一步: -2得: 2y=14 ,第二步: 解得:y=7,第三步:-4得: -2x=-20 ,第四步: 解得:x=10,第五步:得到方程组的解为:,提出问题,【3】写出一般二元一次方程组的解法步骤.,解:第

2、一步,第二步,解（3）得,第三步,第四步,解（4）得,第五步,得到方 程组的解为,算法的概念,算法：,在数学中算法通常指按照一定规则 解决某一类问题的明确和有限的步骤.,现在,算法通常可以编成 计算机程序,让计算机执行并 解决问题.,事实上，我们可以将一般的二元一次方程组的 解法转化成计算机语言，做成一个求解二元一次方 程组的程序。,20 世纪最伟大的科学技术发明-计算机,计算机是对人脑的模拟，它强化了 人的思维智能；,没有软件的支持，超级计算机 只是一堆废铁而已；,软件的核心就是算法 ！,应用举例,例1.(1)设计一个算法判断7是否为质数.,第一步, 用2除7,得到余数1.因为余数不为0，

3、所以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不能整除7.,第四步,

4、 用5除35,得到余数0.因为余数为0， 所以5能整除35.因此，35不是质数.,第一步：给定大于2的整数n. 第二步：令i=2 第三步：用i除n，得到余数t. 第四步：判断“t=0”是否成立.若是，则n不是质数，结束算法；否则，将i的值增加1，仍用i表示. 第五步：判断“i(n-1)”是否成立，若是，则n是质数，结束算法；否则，返回第三步.,第一步，给定大于2的整数n. 第二步,用2去除n，得到余数t.若t=0，则2能够整除n, n 不是质数,算法结束；否则,进入第三步. 第三步,用3去除n，得到余数t.若t=0，则3能够整除n, n 不是质数,算法结束；否则,进入第四步. 第（n-1）步,

5、用（n-1）去除n，得到余数t.若t=0，则（n-1）能够整除n, n 不是质数,算法结束；否则, n是质数.,你能否设计一个算法,判断整数n(n2)是否为质数?,对于区间a,b 上连续不断、且f(a)f(b)0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点或其近似值的方法叫做二分法。,什么叫“二分法”？,第四步, 若f(a) f(m) 0,则含零点的区间为a,m；,第二步, 给定区间a,b,满足f(a) f(b)0,第三步, 取中间点,第五步,判断f(m)是否等于或者a,b的长度是否小于d，若是，则m是方程的近似解;否则，返回

6、第三步,将新得到的含零点的仍然记为a,b.,否则，含零点的区间为m, b.,算法步骤： 第一步, 令 ,给定精确度d.,当d=0.005时，按照以上算法，可得下面表和图.,于是，开区间（1.4140625,1.41796875）中的实数都是当精确度为0.005时的原方程的近似解.,算法的基本特征:明确性、可行性、有限性、 数据输入、信息输出、不唯一性。,明确性:算法的每一步要做什么必须是明确的，不能含糊不清、模棱两可.,可行性:算法的每一个步骤都能够通过基本运算有效地进行,并得到确定的结果；对于相同的输入,无论谁执行算法,都能够得到相同的最终结果,有限性:算法必须由有限步组成,至少对某些输入,

7、算法应在有限多步内结束,并给出计算结果如果需要在无限步完成，就失去了实际意义。,信息输出:一个算法至少要有一个有效的信息输出,这就是问题求解的结果.,不唯一性:求解某一个题的解法不一定是唯一的, 对于一个问题可以有不同的算法.,数据输入:算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤.,3.描述算法的一般步骤： 输入数据.（若数据已知时，应用赋值；若数 据为任意未知时，应用输入） 数据处理. 输出结果.,1.下列关于算法的说法，正确的个数有（ ）。 求解某一类问题的算法是唯一的； 算法必须在有限步操作后之后停止； 算法的每一步操作必须是明确的，不能有歧义或模糊； 算法执行后一

8、定产生确定的结果。 A.1 B.2 C.3 D.4,C,2.下列对算法的理解不正确的是（ ）。 A.算法有一个共同特点就是对一类问题都有效（而不是个别问题） B.算法要求是一步步执行，每一步都能得到唯一的结果 C.算法一般是机械的，有时要进行大量重复的计算，它的优点是一种通法 D.任何问题都可以用算法来解决,D,4.算法的描述:,描述算法可以有不同的方式,常用的有自然语言、程序框图、程序设计语言、伪代码等.,(1)自然语言,(2)程序框图,(3)程序设计语言,1.1.2程序框图中讲解,1.2基本算法语句中讲解,自然语言就是人们日常使用的语言,可以是汉语、英语或数学语言等.用自然语言描述算法的优

9、点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和转向,并且操作步骤较多时,就不那么直观清晰了.,1.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,第一步:输入任意一个正实数r；,第二步:计算圆的面积: S=r2;,第三步:输出圆的面积S.,课堂练习,2.任意给定一个大于1 的正整数n,设计一个算法求出n的所有因数.,第一步：依次以2(n-1)为除数去除n,检查余数是否为0,若是,则是n的因数;若不是,则不是n的因数.,第二步：在n的因数中加入1和n.,第三步：输出n的所有因数.,课堂练习,【1】用自然语言描述求一元二次方程 ax2+bx+c=0 的根的算法.,第一步:计算=b2-4ac;,第二步:如果0,则原方程无实数解 ;否则(0)时，,第三步:输出x1, x2或无实数解的信息.,3.解方程(方程组)不等式的算法,题型探究,【2】写出一个能找出在a,b,c,d四个数中最大的数的算法.,