必修三算法的概念

1、2021/8/1411.1.1 算法的概念算法的概念2021/8/142章头图说明 章头图的后景是元代朱世杰所著的四元玉鉴，前景的前部是一台计算机，后部是盛行一时的计算工具算筹和算盘。 2021/8/143 中国古代数学在世界数学史上一度居于领先地们，它注重实际问题的解决，以算法为中心，寓理于算，其中蕴涵了丰富的算法思想，算筹是中国古代的计算工具，在春秋时期已经很普遍；算盘在明代开始盛行，即使在计算机普及的今天，许多人仍然在使用算盘。中国古代涌现了许多著名的数学家，如三国及两晋时期的赵爽、刘徽，南北朝的祖冲之、宋、元时期的秦九韶、杨辉、朱世杰，等。古时著名的数学专著如九章算术周髀算经数书九章四

2、元玉鉴等。所有这些成就，都使中国数学曾经处于世界巅峰。数学史简介2021/8/144 计算机的问世可谓是计算机的问世可谓是20 世纪最伟大的科学世纪最伟大的科学技术发明。它把人类社会带进了信息技术时代。技术发明。它把人类社会带进了信息技术时代。计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；2121世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：“计算机无处不在计算机无处不在”“数学无处不在数学无处不在”2121世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：-会会“用数学用数学”解决实际问题解决实际问题-会用计算机进行科学计算会用计

3、算机进行科学计算2021/8/145现代科学研究的三大支柱理论研究科学实验科学计算研究算法研究算法2021/8/146 而算法是计算机科学的重要基础。就像使用而算法是计算机科学的重要基础。就像使用算盘一样，人们需要给计算机编制算盘一样，人们需要给计算机编制“口决口决”算算法，才能让它工作，否则超级计算机只是一堆废法，才能让它工作，否则超级计算机只是一堆废铁而已。铁而已。2021/8/147问题的提出问题的提出 有一个农夫带一条狼狗、一只羊和有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小狼狗要吃羊，羊要吃白菜。

4、但是船很小，只够农夫带一样东西过河。问农夫该，只够农夫带一样东西过河。问农夫该如何解此难题？如何解此难题？ 2021/8/148问题的提出问题的提出 有一个农夫带一条狼狗、一只羊和有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该，只够农夫带一样东西过河。问农夫该如何解此难题？如何解此难题？ 方法和过程方法和过程：1、带羊到对岸，返回；带羊到对岸，返回；2、带菜到对岸，并把羊带回；带菜到对岸，并把羊带回；3、带狼狗到对岸，返回；带狼狗到对岸，返回

5、；4、带羊到对岸。带羊到对岸。2021/8/1492、回顾、回顾 二元一次方程组二元一次方程组 12 12yxyx的求解过程的求解过程.我们可以归纳它的步骤我们可以归纳它的步骤:第一步第一步: -2，得，得 5y=3 第三步第三步:5153xy，得代入将第二步第二步: 解得解得 y= 53第二步第二步: 解得解得 y= 53第四步：得到方程组的解为：第四步：得到方程组的解为：x=1/5, y=3/52021/8/14100 1221222111babacybxacybxa其中一般的二元一次方程组第二步：解，得第二步：解，得12211221babacacay第一步：第一步： - - ，得，得 1

6、a2a12211221)(cacaybaba第三步：将第三步：将 代入代入，得，得12211221babacacay12212112babacbcbx第四步：得到方程组的解第四步：得到方程组的解.2021/8/14111 1、算法的含义、算法的含义 算法 （algorithm)古代指的是用阿拉伯数字进行算术运算的过程。在数学中，通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。注意：解决某一类问题，明确而且有效，有限性，程序性，不唯一注意：解决某一类问题，明确而且有效，有限性，程序性，不唯一2021/8/1412【例】写出你在家中烧

7、开水的过程的一个算法。总结：“第1”其实大部分事情都是按照一定的程序执行， 因此要理清事情的每一步。 “第2”判断水是否烧开与是否继续烧火的过程是一个反馈与判断过程，因此有必要不断重复过程“3” 解: 1、往壶内注水； 2、点火加热； 3观察：如果水开，则停止烧火，否则继续烧火； 4、如果水未开，重复“3”直至水开。2021/8/1413请写出下面一个算法：写出已知直角三角形两边a,b，求斜边的一个算法 解：输入直角三角形两边a,b的值； 计算= 输出斜边长L的值。22ba2021/8/1414请试写出一个算法：请试写出一个算法：写出求一个数绝对值的一个算法 解：请输入要求绝对值的数a.若a=

8、0,则b=0(b为a的绝对值)。 若a0，则b=a； 若a0，则b=-a.输出a 的绝对值b。2021/8/1415新课讲解新课讲解算法的算法的基本基本特点特点1、有限性、有限性 一个算法应包括有限的操作步骤，一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。能在执行有穷的操作步骤之后结束。2、确定性、确定性 一个算法的计算规则及相应的计算一个算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。其词，也不能有二义性。3、有效性、有效性 算法中的每一个步骤都是可以算法中的每一个步骤都是可以在有限的时间内有效地完成的基本在有限

9、的时间内有效地完成的基本操作，并能得到确定的结果操作，并能得到确定的结果 。2021/8/1416广播操图解是广播操的算法；广播操图解是广播操的算法； 菜谱是做菜的算法；菜谱是做菜的算法； 歌谱是一首歌曲的算法；歌谱是一首歌曲的算法； 空调说明书是空调使用的算法等空调说明书是空调使用的算法等2021/8/1417例例1 1、（1 1）设计一个算法，判断）设计一个算法，判断7 7是否为质数。是否为质数。 （2 2）设计一个算法，判断）设计一个算法，判断3535是否为质数。是否为质数。算法（算法（1 1） 第一步，用第一步，用2 2除除7 7，得到余数，得到余数1 1。因为余数不为。因为余数不为0

10、 0，所以，所以2 2不能整除不能整除7 7。 第二步，用第二步，用3 3除除7 7，得到余数，得到余数1 1。因为余数不。因为余数不为为0 0，所以，所以3 3不能整除不能整除7 7。 第三步，用第三步，用4 4除除7 7，得到余数，得到余数3 3。因为余数。因为余数不为不为0 0，所以，所以4 4不能整除不能整除7 7。 第四步，用第四步，用5 5除除7 7，得到余数，得到余数2 2。因为余数。因为余数不为不为0 0，所以，所以5 5不能整除不能整除7 7。 第五步，用第五步，用6 6除除7 7，得到余数，得到余数1 1。因为余数。因为余数不为不为0 0，所以，所以6 6不能整除不能整除7

11、 7。因此，。因此，7 7是质数。是质数。2021/8/1418例例1 1、（1 1）设计一个算法，判断）设计一个算法，判断7 7是否为质数。是否为质数。 （2 2）设计一个算法，判断）设计一个算法，判断3535是否为质数。是否为质数。算法（算法（2 2） 第一步，用第一步，用2 2除除3535，得到余数，得到余数1 1。因为余数。因为余数不为不为0 0，所以，所以2 2不能整除不能整除3535。 第二步，用第二步，用3 3除除3535，得到余数，得到余数2 2。因为余数。因为余数不为不为0 0，所以，所以3 3不能整除不能整除3535。 第三步，用第三步，用4 4除除3535，得到余数，得到

12、余数3 3。因为余数。因为余数不为不为0 0，所以，所以4 4不能整除不能整除3535。 第四步，用第四步，用5 5除除3535，得到余数，得到余数0 0。因为余数。因为余数为为0 0，所以，所以5 5能整除能整除3535。因此，。因此，3535不是质数。不是质数。2021/8/1419你能写出你能写出“判断整数判断整数n(nn(n2)2)是否为质数是否为质数”的算法吗？的算法吗？ 第一步，给定大于第一步，给定大于2 2的整数的整数n n。 第二步，令第二步，令i=2.i=2. 第三步，用第三步，用i i除除n n，得到余数，得到余数r r。 第四步：判断余数第四步：判断余数r r是否为是否为

13、0 0，若是则，若是则n n不是质数不是质数，结束算法；否则，将，结束算法；否则，将i i的值增加的值增加1 1，仍用，仍用i i表示。表示。 第五步，判断第五步，判断i i是否大于是否大于(n-1)(n-1)，若是，则，若是，则n n是是质数，结束算法；否则，返回第三步。质数，结束算法；否则，返回第三步。 算法分析：对于任意的整数n(n2),若用i表示2（n-1)中的任意整数，则“判断n是否为质数“的算法包含下面的重复操作：用i除n，得到余数r，判断余数r是否为0，若是，则n不是质数；否则，将i的值增加1，再执行同样的操作这个操作一直要进行到i的值等于(n-1)为止。因此，”判断i是否为质数

14、“的算法可以写成：2021/8/1420例例2用二分法设计一个求方程用二分法设计一个求方程 的近似正根的算法，精确度的近似正根的算法，精确度0.05。220 x 算法分析：算法分析：令令f(x)=x2-2=0(x0)，则方程，则方程x2-2=0的解就是函数的解就是函数f(x)的零点。的零点。 “二分法二分法”的基本思想是：把函数的基本思想是：把函数f(x)的零点所的零点所在的区间在的区间a,b(满足满足f(a)f(b)0)“一分为二一分为二”。得。得到到a,m和和m,b。根据。根据“f(a)f(m)0”是否成立，是否成立，取出零点所在的区间取出零点所在的区间a,m或或m,b，仍记为，仍记为a,

15、b，对所得的区间对所得的区间a,b重复上述步骤，直到包含零点的区重复上述步骤，直到包含零点的区间间a,b“足够小足够小“，则，则a,b内的数可以作为方程的近内的数可以作为方程的近似解。似解。2021/8/1421例例2用二分法设计一个求方程用二分法设计一个求方程 的近似正根的算法的近似正根的算法220 x 22.x第一步：令f x给定精确度d=0.052ab第三步：令m( )( )0,f af m第四步：若则含零点的区间为a,m;否则含零点的区间为m,b.将新得到的含零点的区间仍记为a,b.解：解：( )( )0f af b第二步：确定区间a,b,满足第五步：判断a,b的长度是否小于d或f(m)是否行于0.若是,则m是方程的近似解;否则,