1.1.1 算法的概念

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.1.1,算法的概念,学习目标：了解算法的含义，了解算法的思想,.,一、序言,算法不仅是数学及其应用的重要组成部分，也是计算机科学的重要基础,.,在现代社会里，计算机已经成为人们日常生活和工作不可缺少的工具,.,听音乐、看电影、玩游戏、打字、画卡通画、处理数据，计算机几乎渗透到了人们生活的所有领域,.,那么，计算机是怎样工作的呢？,要想弄清楚这个问题，算法的学习是一个开始,.,从数学发展的历史来看，算法的概念古已有之,.,比如，在西方数学中很早就有了欧几里德算法，而中国古代数学中蕴含着更为丰富的算法内容和思想，割圆术、秦九韶算法等等都是很经典的算法,.,在这一章里，我们将学习算法的概念和程序框图,.,理解算法的基本结构、基本算法语句,.,了解一些很有意思的重要算法，体会算法的基本思想,.,同时，算法有利于发展有条理的思考与表达的能力，提高逻辑思维能力,.,（,联系章头图,）中国古代数学中蕴含了丰富的算法思想，算筹、算盘都是盛行一时的计算工具,.,其中,算筹在春秋时期,已经很普遍；而,算盘在明代开始盛行,，即使在计算机普及的今天，许多人仍然在使用,.,如今，算法已经成为计算机科学的重要基础，同时计算机又是强大的实现各种算法的工具,.,算法是解决问题的一种程序性方法,.,算法思想是现代人应具备的一种数学素养,.,在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想,.,看下列实例：,例,1,写出计算,4,(7-2)+6,的算法步骤,.,解：算法步骤如下：,第一步：计算,7,减去,2,，即,7-2=5,；,第二步：,4,与,5,相乘，即,45=20,；,第三步：,20,与,6,相加，即,20+6=26.,二、引例,例,2,：写出你在家里烧开水泡茶过程的一个算法,.,解：,算法步骤如下：,第一步：把水注入电水壶；,第二步：打开电源烧水；,第三步：洗茶壶（杯、碗）；,第四步：找到茶叶，并把茶叶放入茶杯；,第五步：把烧开的水注入茶杯,.,（以上算法是解决某一问题的程序或步骤）,例,3,写出求方程,x,2,-2x-3=0,的根的一个算法,.,解：算法步骤如下：,第一步：计算,=b,2,-4ac=160;,第二步：将,a=1,b=-2,c=-3,代入求根公式,第三步：得到方程的根,x,1,=-1,x,2,=3.,解法,2,：第一步 移项，得,x,2,2,x,3;,第二步 将第一步的结果两边加,1,配方，得,(,x,1),2,4;,第三步 将第二步的结果两边开方,得,x-,1,2,或,x-,1,-,2,;,第四步 解得方程的根,x,3,或,x,1.,三、算法,(algorthm),的定义,(,含义,),：,1.,定义,：,在数学中，“算法”通常指按照一定规则解决,某一类问题,的,明确和有限的步骤,.,现在,算法通常可以编成计算机程序,让计算机执行并解决问题,.,2.,算法的思想：,在解决某一类问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，达到探求解决这一类问题的一般性方法，并将解决问题的步骤用具体化、程序化的语言加以表述，这就是算法的思想,.,算法思想的一种重要的数学思想，始终贯穿在高中数学的学习过程中，例如，计算一个函数值；求解一个方程；证明一个结论等，我们都需要有一个清晰的思路，一步一步地去完成,.,算法思想可以更好地培养我们的逻辑推理能力,.,算法作为一个名词，在中学教科书中并没有出现过，我们在基础教育阶段还没有接触算法概念,.,但是我们却从小学就开始接触算法，熟悉许多问题的算法,.,比如：,做四则运算要先乘除后加减，从里往外脱括弧；,竖式笔算是算法；至于乘法口诀；珠算口诀等，更是算法的具体体现,.,我们还知道：解一元二次方程的步骤；求解一元一次不等式、一元二次不等式的步骤；解线性方程组的步骤；求两个数的最大公因数的步骤；多项式乘法公式等等，这些都是算法的具体体现,.,四、算法的特征（特点）,程序性,(,顺序性、步骤性、逻辑性、指向性、条理性,),：,算法从初始步骤开始，分成若干个明确的步骤，前一步是后一步的前提，只有完成前一步，才能进行下一步，而且每一步都是正确无误的,.,确定性,(,有效性、精确性,),：,算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的,.,即应当能有效地执行，并得到确定的结果,.,有穷性,(,有限性,),：,一个算法应包含有限的操作步骤，而不能是无限的,.,即必须在执行有穷次运算后结束,.,不唯一性,：,求解某一个问题的算法不一定只有惟一的一个，可以有不同的算法，这些算法有繁简、优劣之分,.,普遍性,：,很多具体问题，都可以设计合理的算法去解决,.,说明：算法必须能在计算机上执行,若没有输出的算法,则计算机在运行后就没有最后的结果,这样的算法是没有意义的,.,算法,(algorithm),一词源于算术,(algorism),，即算术方法，是指一个由已知推求未知的运算过程,.,后来，人们把它推广到一般，把进行某一工作的方法和步骤称为算法,.,广义地说，算法就是做某一件事的步骤或程序,.,菜谱是做菜肴的算法；洗衣机的使用说明书是操作洗衣机的算法；歌谱是一首歌曲的算法,.,解方程的算法、函数求值的算法、作图的算法，等等,.,算法是机械，有时要进行大量重复计算，只要按部就班地去做，总能算出结果，通常把算法过程称为,“数学机械化”，,其最大的优点是可以让计算机来完成,.,例,1,：给出求,1+2+3+4+5,的一个算法,例,1,给出求 的一个算法；,解：算法步骤，按照逐一相加的程序进行,.,第一步,计算,1+2,得到,3;,第二步,将第一步中的运算结果,3,与,3,相加,得到,6,；,第三步,将第二步中的运算结果,6,与,4,相加,得到,10,；,第四步,将第三步中的运算结果,10,与,5,相加,得到,15,；,五、例题讲解,解,:,我们用消元法求解这个方程组,步骤是,:,例,2,给出求解方程组 的一个算法；,第二步,:,解得,y=-1,第一步,:,-2,得,3y=-3,第三步,:,将,y=-1,代入，解得,也可用代入消元法求解,.,给出求解下列方程组的一个算法,.,第一步,：,(1)B,2,-(2)B,1,得,(A,1,B,2,-A,2,B,1,)x=B,2,C,1,-B,1,C,2,.,（,3,）,第三步：,(2)A,1,-(1)A,2,得,(A,1,B,2,-A,2,B,1,)y=A,1,C,2,-A,2,C,1,.,（,4,）,第五步：,得到方程组的解为,例,3,(P3),(,1),设计一个算法，判断,7,是否为质数,.(2),设计一个算法，判断,7,是否为质数,.,算法分析：依次用,2,6,除,7,，如果它们中有一个能整除,7,，则,7,不是质数，否则,7,是质数,.,(1),解：算法步骤如下：,S1:,用,2,除,7,，得到余数,1.,因为余数不为零，所以,2,不能整除,7.,S2:,用,3,除,7,，得到余数,1.,因为余数不为零，所以,3,不能整除,7.,S3:,用,4,除,7,，得到余数,3.,因为余数不为零，所以,4,不能整除,7.,S4:,用,5,除,7,，得到余数,2.,因为余数不为零，所以,5,不能整除,7.,S5:,用,6,除,7,，得到余数,1.,因为余数不为零，所以,6,不能整除,7.,S6:,用,2,除,7,，得到余数,1.,因为余数不为零，所以,2,不能整除,7.,因此，,7,是质数,.,（,2,）类似地，可写出“判断,35,是否为质数”的算法,.,(1),解：算法步骤如下：,S1:,用,2,除,35,，得到余数,1.,因为余数不为,0,，所以,2,不能整除,35.,S2:,用,3,除,35,，得到余数,2.,因为余数不为,0,，所以,3,不能整除,35.,S3:,用,4,除,35,，得到余数,3.,因为余数不为,0,，所以,4,不能整除,35.,S4:,用,5,除,35,，得到余数,0.,因为余数为,0,，所以,5,能整除,35.,因此，,35,不是质数,.,例,3(P3)(1),设计一个算法，判断,7,是否为质数,.(2),设计一个算法，判断,7,是否为质数,.,探究：你能写出,“,判断整数,n(n2),是否为质数,”,的算法吗？,.,算法分析：根据质数的定义,(,只能被,1,和自身整除的大于,1,的整数叫质数,),，很容易设计出下面的步骤：,第一步：,依次从,2,（,n-1,）检验是不是,n,的因数，即整除,n,的数，若有这样的数，则,n,不是质数；若没有这样的数，则,n,是质数,这是判断一个大于,1,的整数,n,是否为质数的最基本算法,.,解法二：见课本,P4.,例,4,两个大人和两个小孩一起渡河，渡口只有一条小船，每次只能渡,1,个大人或两个小孩，他们四人都会划船，但都不会游泳,.,试问他们怎样渡过河去？请写出一个渡河方案,.,第一步,:,两个小孩同船过河去；,第二步：一个小孩划船回来；,第三步：一个大人划船过河去；,第四步：对岸的小孩划船回来；,第五步：两个小孩同船渡过河,去；,第六步：一个小孩划船回来；,第七步：余下的一个大人独自划船渡过河去；对岸的小孩划船回来；,第八步：两个小孩再同时划船渡过河去,.,渡河方案,:,P5.,练习：,1.,任意给定一个正实数，设计一个算法求以这个数为半径的圆的面积,.,解,:,算法步骤为,第一步：输入任意一个正实数,r;,第二步：计算以,r,为半径的圆的面积,S=,r,2,;,第三步：输出圆的面积,S.,2.,任意给定一个大于,1,的正整数,n,，试设计一个算法求出,n,的所有因数,.,解：算法步骤为,第一步：,依次以,2,(n-1),为除数去除,n,，检查余数是否为,0.,若是，则是,n,的因数；若不是，则不是,n,的因数；,第二步：,在,n,的因数中加入,1,和,n,；,第三步：,输出,n,的所有因数,.,六、小结与作业：,本节课主要讲了算法的含义，,算法,通常指按照一定规则解决,某一类问题,的,明确和有限的步骤,.,广义地说，算法就是做某一件事的步骤或程序,.,平时不论我们做什么事都离不开算法，算法的描述可以用自然语言，也可以用数学语言,.,在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序,.,算法具有以下特性：,(1),有穷性；,(2),确定性；,(3),程序性；,(4),不惟一性；,(5),普遍性,.,作业：,1,.,写出求,12345,的算法,.,2.,写出求过两点,M(-3,-1),、,N(2,5),的直线与坐标轴围成面积的一个算法,.,1.,写出求,12345,的算法,.,步骤,1,：,先求,12,，得到结果,2,；,步骤,2,：,将步骤,1,得到的结果,2,再乘以,3,，,得到,6,；,步骤,3,：,将步骤,2,得到的结果,6,再乘以,4,，,得到结果,24,；,步骤,4,：,将步骤,3,得到的结果,24,再乘以,5,，,得到,120.,2.,写出求过两点,M(-3,-1),、,N(2,5),的直线与坐标轴围成面积的一个算法,.,第一步,：取,x,1,=-,3,，,y,1,=-,1,，,x,2,=2,，,y,2,=5,；,第五步,：,计算,；,第六步,：,输出运算结果,S.,第二步,：,计算,第三步,：,在第二步结果中令,x=0,得到,y,的值,m,，得直线与,y,轴交点,(0,m),；,第四步,：,在第二步结果中令,y=0,得到,x,的值,n,，,得直线与,x,轴交点,(n,0),；,