1.1.1《算法的概念》课件.ppt

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

2、一元二次函数图象解一元一次不等式、一元二次函数图象的画法，解线性方程组的算法，求两个的画法，解线性方程组的算法，求两个数的最大公因数的算法等。因此，数的最大公因数的算法等。因此，算法其实是重要的数学对象算法其实是重要的数学对象。一、算法的概念一、算法的概念 算法算法(algorithm)一词源于算术一词源于算术(algorism),即算术方法，是指一个即算术方法，是指一个由已知推求未知由已知推求未知的的运算过程。后来，人们把它推广到一般，运算过程。后来，人们把它推广到一般，把把进行某一工作的方法和步骤进行某一工作的方法和步骤称为算法。称为算法。广义地说，广义地说，算法就是做某一件事的步算法就是

3、做某一件事的步骤或程序骤或程序。菜谱是做菜肴的算法，洗衣。菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。歌谱是一首歌曲的算法。在数学中，在数学中，主要研究计算机能实现的主要研究计算机能实现的算法算法，即按照某种机械程序步骤一定可，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。比如解以得到结果的解决问题的程序。比如解方程的算法、函数求值的算法、作图的方程的算法、函数求值的算法、作图的算法，等等。算法，等等。例例1 “一群小兔一群鸡，两群合到一群里，一群小兔一群鸡，两群合到一群里，要数腿共要数腿共48，要数脑袋整，要数脑

4、袋整17，多少小兔，多少小兔多少鸡？多少鸡？”解：算术方法：如果没有小兔，那么小鸡解：算术方法：如果没有小兔，那么小鸡应为应为17只，总的腿数应为只，总的腿数应为217=34条，条，但现在有但现在有48条腿，造成腿的数目不够是由条腿，造成腿的数目不够是由于小兔的数目为于小兔的数目为0，每有一只小兔便会增，每有一只小兔便会增加两条腿，故应有加两条腿，故应有(48172)2=7只小只小兔。相应的，小鸡有兔。相应的，小鸡有10只。只。代数方法：设有代数方法：设有x只小鸡，只小鸡，y只小兔只小兔.则则172448xyxy将第一个方程的两边同乘以将第一个方程的两边同乘以2加到第二加到第二个方程中去，得到

5、个方程中去，得到17(42)48 17 2xyy解第二个方程得解第二个方程得y=7.把把y代入到第一个方程得代入到第一个方程得x=10.思考思考1 教材中例教材中例1是著名的是著名的“鸡兔同笼鸡兔同笼”问题，其中第一种解法是算术方法，教问题，其中第一种解法是算术方法，教材中对它的评价是材中对它的评价是“简单直观，却包含简单直观，却包含着深刻的算法思想着深刻的算法思想”，那么它是如何体，那么它是如何体现算法的思想呢？现算法的思想呢？S1 假设没有小兔，则小鸡应为假设没有小兔，则小鸡应为n只；只；S2 计算总腿数为计算总腿数为2n只；只；S3 计算实际总腿数与假设总腿数的差值计算实际总腿数与假设总

6、腿数的差值为为m2n；S4 计算小兔只数为计算小兔只数为 ;22mnS5 小鸡的只数为小鸡的只数为n .22mn思考思考2 教材中例教材中例1的第二种解法是列方程的第二种解法是列方程组的方法，它是否也是一种算法呢？组的方法，它是否也是一种算法呢？探究：是的，其算法步骤为：探究：是的，其算法步骤为：S1 设未知数；设未知数；S2 根据题意列方程组；根据题意列方程组；S3 解方程组；解方程组；S4 还原实际问题，得到实际问题的答案。还原实际问题，得到实际问题的答案。在实际中，很多问题可以归结为求解在实际中，很多问题可以归结为求解二元一次方程组，下面我们用消元法来二元一次方程组，下面我们用消元法来解

7、一般的二元一次方程组解一般的二元一次方程组11 1122121 12222 a xa xba xa xbS1 假定假定a110，a11a21得得 11 11221112221 12211 221 1 ()a xa xba aa axa ba bS2 如果如果a11a22a12a210，则执行下步；，则执行下步；否则执行否则执行S6S3 两边同除以两边同除以a11a22a12a210得得 11 1122111 221 12112221 12 a xa xba ba bxa aa aS4 代入代入.得得 22 11221112221 1211 221 12112221 12 a ba bxa aa

8、 aa ba bxa aa aS5 输出结果输出结果x1，x2，S6 若若a11b2a21b10.则执行下一步；否则执行下一步；否则执行则执行S8S7 输出输出“方程组无解方程组无解”.S8 输出输出“方程组有无穷多个解方程组有无穷多个解”以上解二元一次方程组的方法，叫做以上解二元一次方程组的方法，叫做高斯消去法高斯消去法二、算法的特点二、算法的特点 不论在哪一种算法中，它们都是经有限不论在哪一种算法中，它们都是经有限次步骤完成的，因而它们体现了次步骤完成的，因而它们体现了算法的有算法的有穷性穷性。在算法中，每一步都能明确地执行，在算法中，每一步都能明确地执行，且有确定的结果，因此具有且有确定

9、的结果，因此具有确定性确定性。在所有算法中，每一步操作都是可以在所有算法中，每一步操作都是可以执行的，也就是具有执行的，也就是具有可行性可行性。为了便于计算机运算，它们必须先输入为了便于计算机运算，它们必须先输入已知数据，而计算的目的分别是解方程组已知数据，而计算的目的分别是解方程组和求最大值等，因此必须输出结果，也就和求最大值等，因此必须输出结果，也就是必须有输入和输出。是必须有输入和输出。算法解决的都是一类问题（分别是解决算法解决的都是一类问题（分别是解决求方程组的解和确定一个有理整数序列中求方程组的解和确定一个有理整数序列中的最大值问题），因此具有的最大值问题），因此具有普适性普适性。体

10、验体验：写出解方程：写出解方程x22x3=0的一个算法的一个算法.配方法：配方法：S1 移项，得移项，得x22x=3 S2 式两边同加式两边同加1并配方得并配方得(x1)2=4 S3 式两边开方，得式两边开方，得x1=2 S4 解解式得式得x=3或或x=1因式分解法：因式分解法：S1 将方程左边因式分解得将方程左边因式分解得(x3)(x+1)=0 S2 由由得得x3=0或或x+1=0 S3 解解得得x=3或或x1公式法：公式法：S1 计算方程的判别式，判断其符号计算方程的判别式，判断其符号 =(2)24(3)0；S2 将将a=1，b=2，c=3代入求根公式，代入求根公式，得得x=3或或x=1例

11、例2 写出一个求有限整数列中的最大值写出一个求有限整数列中的最大值的算法。的算法。解：算法如下：解：算法如下：S1 先假定序列中的第一个整数为先假定序列中的第一个整数为“最大值最大值”;S2 将序列中的下一个整数值与将序列中的下一个整数值与“最大值最大值”比比较，如果它大于此较，如果它大于此“最大值最大值”，这时你就假定，这时你就假定“最大值最大值”是这个整数；是这个整数；S3 如果序列中还有其他整数，重复如果序列中还有其他整数，重复S2;S4 在序列中一直到没有可比的数为止，这时在序列中一直到没有可比的数为止，这时假定的假定的“最大值最大值”就是这个序列中的最大值。就是这个序列中的最大值。如

12、果让你去找，你可能不会这样做，可如果让你去找，你可能不会这样做，可能认为，这样太机械、太枯燥。不要忘了，能认为，这样太机械、太枯燥。不要忘了，我们写的是算法。算法要求我们写的是算法。算法要求按部就班按部就班地做，地做，每一步都有每一步都有唯一的结果唯一的结果，又要求写出的算，又要求写出的算法对法对任意整数序列都适用任意整数序列都适用，总能得到结果。，总能得到结果。所以上面写的，符合算法的要求。所以上面写的，符合算法的要求。下面我们用数学语言，写出对任意下面我们用数学语言，写出对任意3个个整数整数a，b，c求出最大值的算法。求出最大值的算法。S1 max=aS2 如果如果bmax,则则max=b

13、.S3 如果如果cmax,则则max=c.S4 max就是就是a,b,c中的最大值。中的最大值。例例3 写出求写出求1+2+3+4+5+6的一个算法。的一个算法。解：算法解：算法1：S1 计算计算1+2得到得到3；S2 将第一步中的运算结果将第一步中的运算结果3与与3相加得到相加得到6S3 将第二步中的运算结果将第二步中的运算结果6与与4相加得到相加得到10S4 将第三步中的运算结果将第三步中的运算结果10与与5相加得到相加得到15S5 将第四步中的运算结果将第四步中的运算结果15与与6相加得到相加得到21算法算法2：S1：取：取n=6；S2：计算：计算S3：输出运算结果。：输出运算结果。2)

14、1(nn算法算法3：S1 将原式变形为将原式变形为(1+6)+(2+5)+(3+4)=37；S2 计算计算37；S3 输出运算结果。输出运算结果。例例4.求求1357911的值，写出其的值，写出其算法。算法。算法算法1；第一步，先求第一步，先求13，得到结果，得到结果3；第二步，将第一步所得结果第二步，将第一步所得结果3再乘以再乘以5，得，得到结果到结果15；第三步，再将第三步，再将15乘以乘以7，得到结果，得到结果105；第四步，再将第四步，再将105乘以乘以9，得到，得到945；第五步，再将第五步，再将945乘以乘以11，得到，得到10395，即，即是最后结果。是最后结果。算法算法2：用：

15、用P表示被乘数，表示被乘数，i表示乘数。表示乘数。S1 使使P=1;S2 使使i=3;S3 使使P=Pi；S4 使使i=i+2；S5 若若i11，则返回到，则返回到S3继续执行；否则继续执行；否则算法结束。算法结束。由于计算机动是高速计算的自动机器，由于计算机动是高速计算的自动机器，实现实现循环循环的语句可以在很短的时间内完成。的语句可以在很短的时间内完成。对于对于循环结构循环结构的详细情况，我们将在以后的详细情况，我们将在以后的学习中介绍。的学习中介绍。例例6.利用二分法求函数利用二分法求函数y=f(x)(x在定义区在定义区间间D)上的一个变号零点上的一个变号零点x0的近似值的近似值x，使，

16、使它与零点的误差不超过正数它与零点的误差不超过正数，即使，即使|xx0|，写出它的一个算法，写出它的一个算法.S1 在在D内取一个闭区间内取一个闭区间a，b，使，使f(a)与与f(b)异号，即异号，即f(a)f(b)0；S2 令令x0=，计算，计算f(x0)；2abS3 若若f(x0)=0，则，则x0就是就是y=f(x)的零点；的零点；若若f(x0)与与f(a)异号，则异号，则a=a，b=x0，否则，否则a=x0，b=b；S4 判断判断|ab|是否成立，若成立，则是否成立，若成立，则区间区间a，b内任意实数都是内任意实数都是x0的近似值；的近似值；否则，返回否则，返回S2，直到不等式，直到不等

17、式|ab|2x+4；求求M(1，2)与与N(3，5)两点连线的方程可两点连线的方程可先求先求MN的斜率再利用点斜式方程求得的斜率再利用点斜式方程求得A.1 个个 B.2 个个 C.3 个个 D.4 个个21C6写出求写出求123100的一个算法的一个算法.可以运用公式可以运用公式123n直接计算直接计算.第一步第一步；第二步第二步；第三步输出运算结果第三步输出运算结果.(1)2n n取取n100 计算计算(1)2n n7已知一个学生的语文成绩为已知一个学生的语文成绩为89，数学，数学成绩为成绩为96，外语成绩为，外语成绩为99，求他的总分和，求他的总分和平均成绩的一个算法为：平均成绩的一个算法

18、为：第一步取第一步取A89，B96，C99;第二步第二步；第三步第三步；第四步输出第四步输出D，E.计算总分计算总分DA+B+C 计算平均成绩计算平均成绩E 3D小结作业小结作业 算法是建立在解法基础上的操作过程，算法算法是建立在解法基础上的操作过程，算法不一定要有运算结果，问题答案可以由计算机解不一定要有运算结果，问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是决设计一个解决某类问题的算法的核心内容是设计算法的步骤，它没有一个固定的模式，但有设计算法的步骤，它没有一个固定的模式，但有以下几个基本要求：以下几个基本要求：(1)(1)符合运算规则，计算机能操作；符合运算规则，计算机能操作；(2)(2)每个步骤都有一个明确的计算任务每个步骤都有一个明确的计算任务；(4)(4)步骤个数尽可能少步骤个数尽可能少；(5)(5)每个步骤的语言描述要准确、简明每个步骤的语言描述要准确、简明.(3)(3)对对重复操作重复操作步骤作返回处理步骤作返回处理；