111算法的概念

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

2、,数学史简介,计算机的问世可谓是20 世纪最伟大的科学技术发明。它把人类社会带进了信息技术时代。,计算机是对人脑的模拟，它强化了人的思维智能；,21世纪信息社会的两个主要特征： “计算机无处不在” “数学无处不在”,21世纪信息社会对科技人才的要求： -会“用数学”解决实际问题 -会用计算机进行科学计算,算法的研究和应用正是本课程的主题 ！,现代科学研究的三大支柱,研究算法,而算法是计算机科学的重要基础。就像使用算盘一样，人们需要给计算机编制“口决”算法，才能让它工作，否则超级计算机只是一堆废铁而已；,要想了解计算机的工作原理，算法的学习是一个开始,请看小品“钟点工”片段。,一、问题情境,要把

3、大象装冰箱，分几步？,问：,答：分三步：,第一步：打开冰箱门,第二步：把大象装冰箱,第三步：关上冰箱门,思考？,3.,二、建构数学,1、算法的含义,算法 （algorithm)指的是用阿拉伯数字进行算术运算的过程。在数学中，现代意义上的“算法”通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。,2、算法的特点,有限性： 一个算法应在执行有限个步骤后必须结束.,明确性： 算法中每一个步骤和次序应当是确定的.,二、建构数学,3、算法的思想 ：程序化思想,程序性: 算法是一个程序化的过程.,广播操图解是广播操的算法； 菜谱是做菜的算法；

4、歌谱是一首歌曲的算法； 空调说明书是空调使用的算法等,生活中的算法：,例1、（1）设计一个算法，判断7是否为质数。 （2）设计一个算法，判断35是否为质数。,算法（1）,第一步，用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、（1）设计一个算法，判断7是否为质数。 （2）设计一个算法，判断3

5、5是否为质数。,算法（2）,第一步，用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不是质数,你能写出“判断整数n(n2)是否为质数”的算法吗？,第一步，给定大于2的整数n。,四、数学探究,第二步，令i=2.,第三步，用i除n，得到余数r。判断余数r是否为0，若是则n不是质数，结束算法；否则，将i的值增加1，仍用i表示。,第四步，判断i是否大于(n-1)，

6、若是，则n是质数；否则，返回第三步,算法分析：对于任意的整数n(n2),若用i表示2-（n-1)中的任意整数，则“判断n是否为质数“的算法包含下面的重复操作： 用i除n，得到余数r，判断余数r是否为0，若是，则n不是质数；否则，将i的值增加1，再执行同样的操作 这个操作一直要进行到i的值等于(n-1)为止。因此，”判断i是否为质数“的算法可以写成：,例2,用二分法设计一个求方程 的近似正根的算法，精确度0.05。,算法分析：令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,b，对所得的区间a,b重复上述步骤，直到包含零点的区间a,b“足够小“，则a,b内的数可以作为方程的近似解。,例2,用二分法设计一个求方程 的近似正根的算法,解,课堂练习,设计一个求一般的一元二次方程 的根的算法,四、回顾反思,1、算