111算法的概念1.ppt

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

1、计算机与算法计算机与算法:在现代社会里，计算机已经成为人在现代社会里，计算机已经成为人们日常生活和工作不可缺少的工具们日常生活和工作不可缺少的工具听音乐、看电影、玩游戏、画卡听音乐、看电影、玩游戏、画卡通画、处理数据通画、处理数据计算机几乎可以计算机几乎可以是一个全能的助手，你可以用它来是一个全能的助手，你可以用它来做你想做的任何事情那么，计算做你想做的任何事情那么，计算机是怎样工作呢？要想弄清楚这个机是怎样工作呢？要想弄清楚这个问题，就需要学习算法问题，就需要学习算法什么是算法？什么是算法？发电子邮件的方法很多，下面是其中的一种操作步骤：新课导入新课导入假如你的朋友不会发电子邮件，你怎么教会

2、他？假如你的朋友不会发电子邮件，你怎么教会他？假设家中生火泡茶有以下几个步骤：假设家中生火泡茶有以下几个步骤：a.a.生火生火 b.b.将水倒入锅中将水倒入锅中 c.c.找茶叶找茶叶 d.d.洗茶壶茶碗洗茶壶茶碗 e.e.用开水冲茶用开水冲茶请选出一个最优方案（请选出一个最优方案（）A.abcde B.bacde C.cadbe D.dcabe 背景背景广义的算法广义的算法是指完成某项工作的是指完成某项工作的方法方法和和步骤步骤，那，那么我们可以说洗衣机的使用说明书是操作洗衣机么我们可以说洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等的算法，菜谱是做菜的算法等等.我们做任何事情都是

3、在一定条件下按某种顺序执行的一系列操作。解决数学问题也是如此。例如用加减消元法解二元一次方程组时，就可以按照某一步骤进行操作。请你写出解下面二元一次方程组的详细过程请你写出解下面二元一次方程组的详细过程.第二步第二步,解解得得第三步第三步,-2得得 5y=3;第四步第四步,解解得得 第五步第五步,得到方程组的解为得到方程组的解为第一步第一步,+2得得 5x=1;解：你能你能写出解一般的二元一次方程组的步骤吗？写出解一般的二元一次方程组的步骤吗？第一步第一步,第二步第二步,解（解（3）得）得 第四步第四步,解（解（4）得）得 第三步第三步,第五步第五步,得到方程得到方程组组的解的解为为 在在数数

4、学学中中，算算法法通通常常是是指指按按照照一一定定规规则则解解决决某某一一类类问问题题的的明明确确和和有有限限的的步步骤骤.现现在在，算算法法通通常常可可以以编编成成计计算算机机程程序序，让让计计算算机机执执行并解决问题行并解决问题.2.2.算法的要求算法的要求(1)写出的算法写出的算法,必须能解决一类问题必须能解决一类问题(例如解例如解任意一个二元一次方程组任意一个二元一次方程组),并且能重复使用并且能重复使用;(2)算法过程要能一步一步执行算法过程要能一步一步执行,每一步执行每一步执行的操作的操作,必须确切必须确切,不能含混不清不能含混不清,而且在有限而且在有限步之内完成后能得出结果步之内

5、完成后能得出结果.1.1.算法的定义算法的定义探究新知探究新知3.3.算法的基本特征算法的基本特征:明明确确性性:算算法法对对每每一一个个步步骤骤都都有有确确切切的的、非非二二义义性性的的规规定定,即即每每一一步步对对于于利利用用算算法法解解决决问问题题的的人人或或计计算算机机来来说说都都是是可可读读的的、可可执执行行的的,而而不不需需要计算者临时动脑筋要计算者临时动脑筋.有有效效性性:算算法法的的每每一一个个步步骤骤都都能能够够通通过过基基本本运运算算有有效效地地进进行行,并并得得到到确确定定的的结结果果；对对于于相相同同的的输输入入,无无论论谁谁执执行行算算法法,都都能能够够得得到到相相同

6、同的的最最终终结果结果有限性有限性:算法应由有限步组成算法应由有限步组成,至少对某些输入至少对某些输入,算法应在有限多步内结束算法应在有限多步内结束,并给出计算结果并给出计算结果信信息息输输出出:一一个个算算法法至至少少要要有有一一个个有有效效的的信信息输出息输出,这就是问题求解的结果这就是问题求解的结果.不不唯唯一一性性:求求解解某某一一个个题题的的解解法法不不一一定定是是唯唯一的一的,对于一个问题可以有不同的算法对于一个问题可以有不同的算法.数数据据输输入入:算算法法一一定定要要根根据据输输入入的的初初始始数数据据或或给定的初值才能正确执行它的每一步骤给定的初值才能正确执行它的每一步骤.1

7、下面的四种叙述不能称为算法的是（下面的四种叙述不能称为算法的是（）（A）广播的广播操图解）广播的广播操图解 （B）歌曲的歌谱）歌曲的歌谱 （C）做饭用米）做饭用米 （D）做米饭需要刷锅、淘米、添水、加）做米饭需要刷锅、淘米、添水、加热这些步骤热这些步骤练习题练习题C2下列关于算法的说法正确的是（下列关于算法的说法正确的是（）（A）某算法可以无止境地运算下去）某算法可以无止境地运算下去 （B）一个问题的算法步骤可以是可逆的）一个问题的算法步骤可以是可逆的 （C）完成一件事情的算法有且只有一种）完成一件事情的算法有且只有一种 （D）设计算法要本着简单、方便、可操）设计算法要本着简单、方便、可操作的

8、原则作的原则 D3下列关于算法的说法中，正确的是（下列关于算法的说法中，正确的是（）.A.算法就是某个问题的解题过程算法就是某个问题的解题过程 B.算法执行后可以不产生确定的结果算法执行后可以不产生确定的结果C.解决某类问题的算法不是惟一的解决某类问题的算法不是惟一的 D.算法可以无限地操作下去不停止算法可以无限地操作下去不停止C4下列运算中不属于我们所讨论算法范下列运算中不属于我们所讨论算法范畴的是（畴的是（）.A.已知圆的半径求圆的面积已知圆的半径求圆的面积 B.从一副扑克牌随意抽取从一副扑克牌随意抽取3张扑克牌抽到张扑克牌抽到24点的可能性点的可能性C.已知坐标平面内的两点求直线的方程已

9、知坐标平面内的两点求直线的方程 D.加减乘除运算法则加减乘除运算法则B5下列语句表达中是算法的有（下列语句表达中是算法的有（）.从济南到巴黎可以先乘火车到北京再坐从济南到巴黎可以先乘火车到北京再坐飞机抵达；飞机抵达；利用公式利用公式 S=ah2 计算底为计算底为1高为高为2的三的三角形的面积；角形的面积；x2x+4；求求M(1，2)与与N(3，5)两点连线的方程可两点连线的方程可先求先求MN的斜率再利用点斜式方程求得的斜率再利用点斜式方程求得A.1 个个 B.2 个个 C.3 个个 D.4 个个C我有2条腿一个脑袋我有4条腿一个脑袋问题问题1：“一群小兔一群小鸡，两群一群小兔一群小鸡，两群合合

10、 到一群中，腿一共有到一群中，腿一共有48条，脑条，脑 袋共有袋共有17个，问一共有多少小个，问一共有多少小 鸡？多少小兔？鸡？多少小兔？解决步骤解决步骤：1.设未知数：设未知数：设有设有x只小鸡，只小鸡，y只小兔只小兔 X+Y=172.列方程组；列方程组；2X+4Y=483.解方程组；解方程组；X=10 y=74.得到实际问题的答案。得到实际问题的答案。小鸡小鸡10只，小兔只，小兔7只只 例题例题例例 2:2:(1)(1)设计一个算法，判断设计一个算法，判断7 7是否为质是否为质数。数。第一步，用第一步，用2除除7，得余数，得余数1，因为余数不是，因为余数不是0，所以，所以2不能除不能除7.

11、第二步，用第二步，用3除除7，得余数，得余数1，因为余数不是，因为余数不是0，所以，所以3不能除不能除7.第三步，用第三步，用4除除7，得余数，得余数3，因为余数不是，因为余数不是0，所以，所以4不能除不能除7.第四步，用第四步，用5除除7，得余数，得余数2，因为余数不是，因为余数不是0，所以，所以5不能除不能除7.第五步，用第五步，用6除除7，得余数，得余数1，因为余数不是，因为余数不是0，所以，所以6不能除不能除7.变式：设计一个算法，判断变式：设计一个算法，判断3535是否为质数。是否为质数。第一步，用第一步，用2除除35，得余数，得余数1，因为余数不是，因为余数不是0，所以，所以2不能

12、除不能除35.第二步，用第二步，用3除除35，得余数，得余数2，因为余数不是，因为余数不是0，所以，所以3不能除不能除35.第三步，用第三步，用4除除35，得余数，得余数3，因为余数不是，因为余数不是0，所以，所以4不能除不能除35.第四步，用第四步，用5除除35，得余数，得余数0，因为余数是，因为余数是0，所以，所以5能除能除35.因此，因此，35不是质数不是质数.变式变式:任意给定一个大于任意给定一个大于2 2的整数的整数n,n,试试设计一个程序或步骤对设计一个程序或步骤对n n是否为质数做是否为质数做出判断。出判断。例题例题第一步：第一步：给定大于给定大于2的整数的整数n.第二步：第二步

13、：令令i=2第三步：第三步：用用i除除n，得到余数，得到余数r.第四步：第四步：判断判断”r=0”是否成立，若是，是否成立，若是，则则n不是质数，结束算法；否则，将不是质数，结束算法；否则，将i的的值增加值增加1，仍用，仍用i表示表示,即：即：i=i+1.第五步：第五步：判断判断”i(n-1)”是否成立，若是否成立，若是，则是，则n是质数，结束算法；否则，将返是质数，结束算法；否则，将返回第回第3步步.1.任意给定一个正实数任意给定一个正实数a，试设计一个算，试设计一个算法求以法求以a为直径的圆的面积为直径的圆的面积.第一步：输入第一步：输入a的值的值.第二步：第二步：_.第三步：第三步：_.

14、第四步：输出圆的面积的值第四步：输出圆的面积的值.解：解：练习练习计算计算 计算计算 例2：用二分法设计一个求方程 的近似根的算法 对于区间a,b 上连续不断、且f(a)f(b)0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点，进而得到零点或其近似值的方法叫做二分法。二分法的基本思想：二分法的基本思想：分析：分析：第四步第四步,若若f(a)f(m)0,则含零点的区间为则含零点的区间为a,m；否则，含零点的区间为；否则，含零点的区间为m,b.第二步第二步,给定区间给定区间a,b,满足满足f(a)f(b)0第三步第三步,取中间点取中间点第五步第五

15、步,判断判断f(m)是否等于或者是否等于或者a,b的长的长度是否小于度是否小于d，若是，则，若是，则m是方程的近似解是方程的近似解;否否则，返回第三步则，返回第三步将新得到的含零点的仍然记为将新得到的含零点的仍然记为a,b.第一步第一步,令令 ,给定精确度给定精确度d.算法步骤：算法步骤：a ab b|a-b|a-b|1 12 21 11 11.51.50.50.51.251.251.51.50.250.251.3751.3751.51.50.1250.1251.3751.3751.437 51.437 50.062 50.062 51.406 251.406 251.437 51.437 5

16、0.031 250.031 251.406 251.406 251.421 8751.421 8750.015 6250.015 6251.414 6251.414 6251.421 8751.421 8750.007 812 50.007 812 51.414 062 51.414 062 51.417 968 751.417 968 750.003 906 250.003 906 25当当d d=0.005=0.005时，按照以上算法，可得下面表和图时，按照以上算法，可得下面表和图.y=x2-2121.51.3751.25 于是，开区间于是，开区间（1.4140625,1.41796875）中）中的实数都是当精确度为的实数都是当精确度为0.005时的原方程的近时的原方程的近似解似解.