1.1.1 算法的概念.ppt

《1.1.1 算法的概念.ppt》由会员分享，可在线阅读，更多相关《1.1.1 算法的概念.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.1.1 1.1.1 算法的概念算法的概念学习目标：了解算法的含义，了解算法的思想.一、序言一、序言 算法不仅是数学及其应用的重要组成算法不仅是数学及其应用的重要组成部分，也是计算机科学的重要基础部分，也是计算机科学的重要基础.在现在现代社会里，计算机已经成为人们日常生活代社会里，计算机已经成为人们日常生活和工作不可缺少的工具和工作不可缺少的工具.听音乐、看电影、听音乐、看电影、玩游戏、打字、画卡通画、处理数据，计玩游戏、打字、画卡通画、处理数据，计算机几乎渗透到了人们生活的所有领域算机几乎渗透到了人们生活的所有领域.那么，计算机是怎样工作的呢？那么，计算机是怎样工作的呢？要想弄清楚这个问题

2、，算法的学习是要想弄清楚这个问题，算法的学习是一个开始一个开始.从数学发展的历史来看，算法的概念古已从数学发展的历史来看，算法的概念古已有之有之.比如，在西方数学中很早就有了欧几比如，在西方数学中很早就有了欧几里德算法，而中国古代数学中蕴含着更为里德算法，而中国古代数学中蕴含着更为丰富的算法内容和思想，割圆术、秦九韶丰富的算法内容和思想，割圆术、秦九韶算法等等都是很经典的算法算法等等都是很经典的算法.在这一章里，我们将学习算法的概念和程在这一章里，我们将学习算法的概念和程序框图序框图.理解算法的基本结构、基本算法语理解算法的基本结构、基本算法语句句.了解一些很有意思的重要算法，体会算了解一些很

3、有意思的重要算法，体会算法的基本思想法的基本思想.同时，算法有利于发展有条同时，算法有利于发展有条理的思考与表达的能力，提高逻辑思维能理的思考与表达的能力，提高逻辑思维能力力.（联系章头图联系章头图）中国古代数学中蕴含了丰）中国古代数学中蕴含了丰富的算法思想，算筹、算盘都是盛行一时富的算法思想，算筹、算盘都是盛行一时的计算工具的计算工具.其中其中算筹在春秋时期算筹在春秋时期已经已经很普遍；而很普遍；而算盘在明代开始盛行算盘在明代开始盛行，即使在，即使在计算机普及的今天，许多人仍然在使用计算机普及的今天，许多人仍然在使用.如今，算法已经成为计算机科学的重要基如今，算法已经成为计算机科学的重要基础

4、，同时计算机又是强大的实现各种算法础，同时计算机又是强大的实现各种算法的工具的工具.算法是解决问题的一种程序性方法算法是解决问题的一种程序性方法.算法思想是现代人应具备的一种数学素养算法思想是现代人应具备的一种数学素养.在以前的学习中，虽然没有出现算法这个在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了名词，但实际上在数学教学中已经渗透了大量的算法思想大量的算法思想.看下列实例：看下列实例：例例1 写出计算写出计算4(7-2)+6的算法步骤的算法步骤.解：算法步骤如下：解：算法步骤如下：第一步：计算第一步：计算7减去减去2，即，即7-2=5；第二步：第二步：4与与5相乘

5、，即相乘，即45=20；第三步：第三步：20与与6相加，即相加，即20+6=26.二、引例二、引例例例2 2：写出你在家里烧开水泡茶过程的一个算法：写出你在家里烧开水泡茶过程的一个算法.解：解：算法步骤如下：算法步骤如下：第一步：把水注入电水壶；第一步：把水注入电水壶；第二步：打开电源烧水；第二步：打开电源烧水；第三步：洗茶壶（杯、碗）；第三步：洗茶壶（杯、碗）；第四步：找到茶叶，并把茶叶放入茶杯；第四步：找到茶叶，并把茶叶放入茶杯；第五步：把烧开的水注入茶杯第五步：把烧开的水注入茶杯.（以上算法是解决某一问题的程序或步骤）（以上算法是解决某一问题的程序或步骤）例例3 写出求方程写出求方程x2

6、-2x-3=0的根的一个算法的根的一个算法.解：算法步骤如下：解：算法步骤如下：第一步：计算第一步：计算=b2-4ac=160;第二步：将第二步：将a=1,b=-2,c=-3代入求根公式代入求根公式第三步：得到方程的根第三步：得到方程的根x1=-1,x2=3.解法解法2：第一步：第一步 移项，得移项，得x22x3;第二步第二步 将第一步的结果两边加将第一步的结果两边加1配方，得配方，得(x1)24;第三步第三步 将第二步的结果两边开方将第二步的结果两边开方,得得 x-12,或或 x-1-2;第四步第四步 解得方程的根解得方程的根x3,或或 x1.三、算法三、算法(algorthm)的定义的定义

7、(含义含义)：1.定义定义：在数学中，“算法”通常指按照一定规则解决某一类问题某一类问题的明确和有限的步骤.现在,算法通常可以编成计算机程序,让计算机执行并解决问题.2.算法的思想：算法的思想：在解决某一类问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，达到探求解决这一类问题的一般性方法，并将解决问题的步骤用具体化、程序化的语言加以表述，这就是算法的思想.算法思想的一种重要的数学思想，始终贯穿在高中数学的学习过程中，例如，计算一个函数值；求解一个方程；证明一个结论等，我们都需要有一个清晰的思路，一步一步地去完成.算法思想可以更好地培养我们的逻辑推理能力.算法作为一个名

8、词，在中学教科书中并没有出现算法作为一个名词，在中学教科书中并没有出现过，我们在基础教育阶段还没有接触算法概念过，我们在基础教育阶段还没有接触算法概念.但是我们却从小学就开始接触算法，熟悉许多问但是我们却从小学就开始接触算法，熟悉许多问题的算法题的算法.比如：比如：做四则运算要先乘除后加减，从里往外脱括弧；做四则运算要先乘除后加减，从里往外脱括弧；竖式笔算是算法；至于乘法口诀；珠算口诀等，竖式笔算是算法；至于乘法口诀；珠算口诀等，更是算法的具体体现更是算法的具体体现.我们还知道：解一元二次方程的步骤；求解一元我们还知道：解一元二次方程的步骤；求解一元一次不等式、一元二次不等式的步骤；解线性方一

9、次不等式、一元二次不等式的步骤；解线性方程组的步骤；求两个数的最大公因数的步骤；多程组的步骤；求两个数的最大公因数的步骤；多项式乘法公式等等，这些都是算法的具体体现项式乘法公式等等，这些都是算法的具体体现.四、算法的特征（特点）四、算法的特征（特点）程序性程序性(顺序性、步骤性、逻辑性、指向性、条理性顺序性、步骤性、逻辑性、指向性、条理性)：算法从初始步骤开始，分成若干个明确的步骤，前一步是后一步的前提，只有完成前一步，才能进行下一步，而且每一步都是正确无误的.确定性确定性(有效性、精确性有效性、精确性)：算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的.即应当能有效地执行，并得到

10、确定的结果.有穷性有穷性(有限性有限性)：一个算法应包含有限的操作步骤，而不能是无限的.即必须在执行有穷次运算后结束.不唯一性不唯一性：求解某一个问题的算法不一定只有惟一的一个，可以有不同的算法，这些算法有繁简、优劣之分.普遍性普遍性：很多具体问题，都可以设计合理的算法去解决.说明：算法必须能在计算机上执行说明：算法必须能在计算机上执行,若没有输出的算法若没有输出的算法,则则计算机在运行后就没有最后的结果计算机在运行后就没有最后的结果,这样的算法是没有意这样的算法是没有意义的义的.算法(algorithm)一词源于算术(algorism)，即算术方法，是指一个由已知推求未知的运算过程.后来，人

11、们把它推广到一般，把进行某一工作的方法和步骤称为算法.广义地说，算法就是做某一件事的步骤或程序.菜谱是做菜肴的算法；洗衣机的使用说明书是操作洗衣机的算法；歌谱是一首歌曲的算法.解方程的算法、函数求值的算法、作图的算法，等等.算法是机械，有时要进行大量重复计算，只要按部就班地去做，总能算出结果，通常把算法过程称为“数学机械化”，其最大的优点是可以让计算机来完成.例例1：给出求：给出求1+2+3+4+5的一个算法的一个算法例例1 1给给出出求求的的一一个个算算法法；解：算法步骤，按照逐一相加的程序进行解：算法步骤，按照逐一相加的程序进行.第一步第一步 计算计算1+2,1+2,得到得到3;3;第二步

12、第二步 将第一步中的运算结果将第一步中的运算结果3 3与与3 3相加相加,得到得到6 6；第三步第三步 将第二步中的运算结果将第二步中的运算结果6 6与与4 4相加相加,得到得到1010；第四步第四步 将第三步中的运算结果将第三步中的运算结果1010与与5 5相加相加,得到得到1515；五、例题讲解五、例题讲解解解:我们用消元法求解这个方程组我们用消元法求解这个方程组,步骤是步骤是:例例2 2 给出求解方程组给出求解方程组 的一个算法；的一个算法；第二步第二步:解解得得y=-1第一步第一步:-2得得3y=-3 第三步第三步:将将y=-1代入代入，解得，解得也可用代入消元法求解也可用代入消元法求

13、解.给出求解下列方程组的一个算法给出求解下列方程组的一个算法.第一步第一步：(1)B2-(2)B1,得得(A1B2-A2B1)x=B2C1-B1C2.（3）第三步：第三步：(2)A1-(1)A2,得得(A1B2-A2B1)y=A1C2-A2C1.（4）第五步：第五步：得到方程组的解为得到方程组的解为例例3(P3)(1)设计一个算法，判断设计一个算法，判断7是否为质数是否为质数.(2)设计一个算法，判断设计一个算法，判断7是否为质数是否为质数.算法分析：依次用算法分析：依次用26除除7，如果它们中有一个能整除，如果它们中有一个能整除7，则则7不是质数，否则不是质数，否则7是质数是质数.(1)解：

14、算法步骤如下：解：算法步骤如下：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.因为余

15、数不为零，所以因为余数不为零，所以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，所

16、以，所以5能整除能整除35.因此，因此，35不是质数不是质数.例例3(P3)(1)设计一个算法，判断设计一个算法，判断7是否为质数是否为质数.(2)设计一个算法，判断设计一个算法，判断7是否为质数是否为质数.探究：你能写出探究：你能写出“判断整数判断整数n(n2)n(n2)是否为质数是否为质数”的算法吗的算法吗？.算法分析：根据质数的定义算法分析：根据质数的定义(只能被只能被1和自身和自身整除的大于整除的大于1的整数叫质数的整数叫质数)，很容易设计出，很容易设计出下面的步骤：下面的步骤：第一步：第一步：依次从依次从2（n-1）检验是不是）检验是不是n的的因数，即整除因数，即整除n的数，若有这样

17、的数，则的数，若有这样的数，则n不是质数；不是质数；若没有这样的数，则若没有这样的数，则n是质数是质数这是判断一个大于这是判断一个大于1的整数的整数n是否为质数的最是否为质数的最基本算法基本算法.解法二：见课本解法二：见课本P4.P4.例例4 两个大人和两个小孩一起渡河，两个大人和两个小孩一起渡河，渡口只有一条小船，每次只能渡渡口只有一条小船，每次只能渡1 个大个大人或两个小孩，他们四人都会划船，但人或两个小孩，他们四人都会划船，但都不会游泳都不会游泳.试问他们怎样渡过河去？试问他们怎样渡过河去？请写出一个渡河方案请写出一个渡河方案.第一步第一步:两个小孩同船过河去；两个小孩同船过河去；第二步

18、：一个小孩划船回来；第二步：一个小孩划船回来；第三步：一个大人划船过河去；第三步：一个大人划船过河去；第四步：对岸的小孩划船回来；第四步：对岸的小孩划船回来；第五步：两个小孩同船渡过河第五步：两个小孩同船渡过河去；去；第六步：一个小孩划船回来；第六步：一个小孩划船回来；第七步：余下的一个大人独自划船第七步：余下的一个大人独自划船渡过河去；对岸的小孩划船回来；渡过河去；对岸的小孩划船回来；第八步：两个小孩再同时划船渡过河去第八步：两个小孩再同时划船渡过河去.渡河方案渡河方案:P5.练习：1.任意给定一个正实数，设计一个算法求以任意给定一个正实数，设计一个算法求以这个数为半径的圆的面积这个数为半径

19、的圆的面积.解解:算法步骤为算法步骤为第一步：输入任意一个正实数第一步：输入任意一个正实数r;第二步：计算以第二步：计算以r为半径的圆的面积为半径的圆的面积S=r2;第三步：第三步：输出出圆的面的面积S.2.2.任意给定一个大于任意给定一个大于1 1的正整数的正整数n n，试设计，试设计一个算法求出一个算法求出n n的所有因数的所有因数.解：算法步骤为解：算法步骤为第一步：第一步：依次以依次以2(n-1)为除数去除为除数去除n，检，检查余数是否为查余数是否为0.若是，则是若是，则是n的因数；的因数；若不是，则不是若不是，则不是n的因数；的因数；第二步：第二步：在在n的因数中加入的因数中加入1和

20、和n；第三步：第三步：输出输出n的所有因数的所有因数.六、小结与作业：本节课主要讲了算法的含义，本节课主要讲了算法的含义，算法算法通常指按照一定规则解决某一类问题某一类问题的明确和有限的步骤明确和有限的步骤.广义地说，算法就是做某一件事的步骤或程序广义地说，算法就是做某一件事的步骤或程序.平时不论我们做什么事都离不开算法，算法的描平时不论我们做什么事都离不开算法，算法的描述可以用自然语言，也可以用数学语言述可以用自然语言，也可以用数学语言.在数学中，主要研究计算机能实现的算法，即按在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问照某种机械程序步骤一定可以得到

21、结果的解决问题的程序题的程序.算法具有以下特性：算法具有以下特性：(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，得到结果得到结果2

22、4；步骤步骤4：将步骤将步骤3得到的结果得到的结果24再乘以再乘以5，得到得到120.2.写出求过两点写出求过两点M(-3,-1)、N(2,5)的的直线与坐标轴围成面积的一个算法直线与坐标轴围成面积的一个算法.第一步第一步：取：取x1=-3，y1=-1，x2=2，y2=5；第五步第五步：计计算算；第六步第六步：输输出运算出运算结结果果S.S.第二步第二步：计算计算第三步第三步：在第二步在第二步结结果中令果中令x=0得到得到y的的值值m，得直得直线线与与y轴轴交点交点(0,m)；第四步第四步：在第二步在第二步结结果中令果中令y=0y=0得到得到x x的的值值n n，得直得直线线与与x x轴轴交点交点(n,0)(n,0)；