111算法的概念 (2)

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

2、 计算机的问世可谓是计算机的问世可谓是20 世纪最伟大的科学世纪最伟大的科学技术发明。它把人类社会带进了信息技术时代。技术发明。它把人类社会带进了信息技术时代。计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；2121世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：“计算机无处不在计算机无处不在”“数学无处不在数学无处不在”2121世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：-会会“用数学用数学”解决实际问题解决实际问题-会用计算机进行科学计算会用计算机进行科学计算现代科学研究的三大支柱理论研究科学实验科学计算研究算法研究算法 而算

3、法是计算机科学的重要基础。就像使用而算法是计算机科学的重要基础。就像使用算盘一样，人们需要给计算机编制算盘一样，人们需要给计算机编制“口决口决”算算法，才能让它工作，否则超级计算机只是一堆废法，才能让它工作，否则超级计算机只是一堆废铁而已；铁而已；请看小品请看小品“钟点工钟点工”片段。片段。 要把大象装冰箱，分几步？要把大象装冰箱，分几步？问：问：答：分三步：答：分三步：第一步：打开冰箱门第一步：打开冰箱门第二步：把大象装冰箱第二步：把大象装冰箱第三步：关上冰箱门第三步：关上冰箱门2、回顾、回顾 二元一次方程组二元一次方程组 12 12yxyx的求解过程的求解过程.我们可以归纳它的步骤我们可以

4、归纳它的步骤:第一步第一步: -2，得，得 5y=3 第三步第三步:5153xy，得代入将第二步第二步: 解解得得 y= 53第二步第二步: 解解得得 y= 53思考？0 1221222111babacybxacybxa其中一般的二元一次方程组第二步：解第二步：解，得，得12211221babacacay第一步：第一步： - - ，得，得 1a2a12211221)(cacaybaba第三步：将第三步：将 代入代入，得，得12211221babacacay12212112babacbcbx1 1、算法的含义、算法的含义 算法 （algorithm)指的是用阿拉伯数字进行算术运算的过程。在数学中

5、，现代意义上的“算法”通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。2、算法的特点、算法的特点 有限性：一个算法应在执行有限个步骤后必须结束有限性：一个算法应在执行有限个步骤后必须结束.确定性：算法中每一个步骤和次序应当是确定的确定性：算法中每一个步骤和次序应当是确定的.3、算法的思想、算法的思想 ：程序化思想：程序化思想广播操图解是广播操的算法；广播操图解是广播操的算法； 菜谱是做菜的算法；菜谱是做菜的算法； 歌谱是一首歌曲的算法；歌谱是一首歌曲的算法； 空调说明书是空调使用的算法等空调说明书是空调使用的算法等例例1 1、（1

6、 1）设计一个算法，判断）设计一个算法，判断7 7是否为质数。是否为质数。 （2 2）设计一个算法，判断）设计一个算法，判断3535是否为质数。是否为质数。算法（算法（1 1） 第一步，用第一步，用2 2除除7 7，得到余数，得到余数1 1。因为余数。因为余数不为不为0 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。 第

7、四步，用第四步，用5 5除除7 7，得到余数，得到余数2 2。因为余数。因为余数不为不为0 0，所以，所以5 5不能整除不能整除7 7。 第五步，用第五步，用6 6除除7 7，得到余数，得到余数1 1。因为余数。因为余数不为不为0 0，所以，所以6 6不能整除不能整除7 7。因此，。因此，7 7是质数是质数例例1 1、（1 1）设计一个算法，判断）设计一个算法，判断7 7是否为质数。是否为质数。 （2 2）设计一个算法，判断）设计一个算法，判断3535是否为质数。是否为质数。算法（算法（2 2） 第一步，用第一步，用2 2除除3535，得到余数，得到余数1 1。因为余数。因为余数不为不为0 0

8、，所以，所以2 2不能整除不能整除3535。 第二步，用第二步，用3 3除除3535，得到余数，得到余数2 2。因为余数。因为余数不为不为0 0，所以，所以3 3不能整除不能整除3535。 第三步，用第三步，用4 4除除3535，得到余数，得到余数3 3。因为余数。因为余数不为不为0 0，所以，所以4 4不能整除不能整除3535。 第四步，用第四步，用5 5除除3535，得到余数，得到余数0 0。因为余数。因为余数为为0 0，所以，所以5 5能整除能整除3535。因此，。因此，3535不是质数不是质数你能写出你能写出“判断整数判断整数n(nn(n2)2)是否为质数是否为质数”的算法吗？的算法吗

9、？ 第一步，给定大于第一步，给定大于2 2的整数的整数n n。 第二步，令第二步，令i=2.i=2. 第三步，用第三步，用i i除除n n，得到余数，得到余数r r。判断余数。判断余数r r是否是否为为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是否为质数“的算法包含下面的

10、重复操作：用i除n，得到余数r，判断余数r是否为0，若是，则n不是质数；否则，将i的值增加1，再执行同样的操作这个操作一直要进行到i的值等于(n-1)为止。因此，”判断i是否为质数“的算法可以写成：例例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)“一分为二一分为

11、二”。得。得到到a,m和和m,b。根据。根据“f(a)f(m)0”是否成立，是否成立，取出零点所在的区间取出零点所在的区间a,m或或m,b，仍记为，仍记为a,b，对所得的区间对所得的区间a,b重复上述步骤，直到包含零点的区重复上述步骤，直到包含零点的区间间a,b“足够小足够小“，则，则a,b内的数可以作为方程的近内的数可以作为方程的近似解。似解。例例2用二分法设计一个求方程用二分法设计一个求方程 的近似正根的算法的近似正根的算法220 x 22.x第一步：令f x给定精确度d=0.052ab第三步：令m( )( )0,f af m第四步：若则含零点的区间为a,m;否则含零点的区间为m,b.将新得到的含零点的区间仍记为a,b.第五步：判断a,b的长度是否小于d或f(m)是否行于0.若是,则m是方程的近似解;否则,返回第三步解解( )( )0f af b第二步：确定区间a,b,满足课堂练习设计一个求一般的一元二次方程 的根的算法02c