算法的设计尽量简单.ppt

1.1.11.1.1算法的概念算法的概念 随着科学技术的日新月异,算法学也得到了前所未有的发展,现在已经发展到了各个领域.有遗传算法,排序算法,加密算法,蚁群算法等,与生物学,计算机科学等有着很广泛的联系,尤其是在现在的航空航天中,更是有着更广泛的应用.很多复杂的运算都是借助计算机和算法来完成的,在高端科学技术中有着很重要的地位.1-1、把冰箱门打开 2、把大象装进去 3、把冰箱门关上 2000春晚小品春晚小品钟钟点工点工 2-问题问题1:请请写出解二元一次方程写出解二元一次方程组组的的详细详细求解求解步步骤.第一步第一步:2得得:5x=1 第二步第二步:解解得得:第第三三步步:-2得得:5y3 第第四四步步:解解得得:第第五五步步:得得到方程到方程组的解的解为 你能写出与教材解法不同的求解步你能写出与教材解法不同的求解步骤吗？3-你能你能写出写出求求一般二元一次方程一般二元一次方程组组的的步步骤吗？第三步第三步:第四步第四步:解（4）得 第五步第五步:得到方程得到方程组组的解的解为为 推推 广广第一步第一步:第二步第二步:解（3）得 4-一一般般地地,按按照照一一定定规则解解决决某某一一类问题的的明确明确和和有限有限的步的步骤称称为算法算法。从从广广义义的的角角度度来来看看,并并不不是是只只有有“计计算算”的的问问题题才才有有算算法法,日日常常生生活活中中处处处处都都有有.如如乐乐谱谱是是乐乐队队演演奏奏的的算算法法,菜菜谱谱是是做做菜肴的算法菜肴的算法,棋棋谱是是下棋下棋的算法的算法.它是解决它是解决某一某一类类问题问题的程序或步的程序或步骤骤；这这些程序或步些程序或步骤骤必必须须是明确有效的是明确有效的，而且而且能能够够在有限步之内完成在有限步之内完成；算法的；算法的设计尽量尽量简单简单、步、步骤骤尽量少尽量少。一一.算法的算法的概念概念5-二二.算法的基本特征算法的基本特征:明明确确性性:算算法法中中的的每每一一步步都都应应该该是是确确定定的的,并且能有效地并且能有效地执执行且得到确定的行且得到确定的结结果果.有限性有限性:一个算法的步一个算法的步骤骤是有限的是有限的，它它应应在在有限步操作之后停止，而不能是无限的有限步操作之后停止，而不能是无限的程程序序性性:算算法法从从初初始始步步骤骤开开始始，分分为为若若干干明明确确的的步步骤骤，每每一一个个步步骤骤只只能能有有一一个个确确定定的的后后续步步骤骤，只只有有执执行行完完前前一一步步才才能能进进行行下一步，并且每一步都下一步，并且每一步都要要准确无准确无误误.6-1下列关于算法的下列关于算法的说法正确的是（法正确的是（）（A）某算法可以无止境地运算下去）某算法可以无止境地运算下去 （B）一个）一个问题的算法步的算法步骤可以是可逆的可以是可逆的 （C）完成一件事情的算法有且只有一种）完成一件事情的算法有且只有一种 （D）设计算法要本着算法要本着简单、方便、可操、方便、可操作的原作的原则 D概念辨析概念辨析7-2下列运算中不属于我下列运算中不属于我们所所讨论算法范算法范畴的是（畴的是（）.A.已知已知圆的半径求的半径求圆的面的面积 B.从一副扑克牌随意抽取从一副扑克牌随意抽取3张扑克牌抽到扑克牌抽到 24点的可能性点的可能性C.已知坐已知坐标平面内的两点求直平面内的两点求直线的方程的方程 D.加减乘除运算法加减乘除运算法则B概念辨析概念辨析8-三三.算法的算法的表示方式：表示方式：自然语言就是人们日常使用的语言,可以是汉语、英语或数学语言等.用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和循环,并且操作步骤较多时,就不那么直观清晰了.(1)(1)自然自然语语言言（算法（算法语言）言）(2)(2)程序框程序框图(3)(3)程序程序设计语言言1.1.21.1.2程序框程序框图中中讲解解1.21.2基本算法基本算法语句句中中讲解解9-第一步第一步：用：用2 2除除7 7，得到余数，得到余数1,1,所以所以2 2不能整除不能整除7.7.第二步第二步：用：用3 3除除7 7，得到余数，得到余数1,1,所以所以3 3不能整除不能整除7.7.例例1:1:（1 1）设计设计一个算法，判断一个算法，判断7 7是否是否为质为质数？数？第三步第三步：用：用4 4除除7 7，得到余数，得到余数3,3,所以所以4 4不能整除不能整除7.7.第四步第四步：用：用5 5除除7 7，得到余数，得到余数2,2,所以所以5 5不能整除不能整除7.7.第五步第五步：用：用6 6除除7 7，得到余数，得到余数1,1,所以所以6 6不能整除不能整除7.7.因此，因此，7 7是是质数数.10-例例1 1:（2 2）设计设计一个算法，判断一个算法，判断3535是否是否为质为质数？数？第一步第一步：用：用2 2除除3535，得到余数，得到余数1,1,所以所以2 2不能整除不能整除35.35.第二步第二步：用：用3 3除除3535，得到余数，得到余数2,2所以所以3 3不能整除不能整除35.35.第三步第三步：用：用4 4除除3535，得到余数，得到余数3,3,所以所以4 4不能整除不能整除35.35.第四步第四步：用：用5 5除除3535，得到余数，得到余数0,0,所以所以5 5能整除能整除35.35.因此，因此，3535不是不是质数数.11-第一步：第一步：给定一个大于定一个大于2 2的整数的整数n；第二步：第二步：令令i=2=2；第三步：第三步：用用i除除n，得到余数，得到余数r r；第五步：第五步：判断判断“i(n-1)-1)”是否成立是否成立.若是，若是，则则n n是是质质数数,结束算法；束算法；否否则则，返回第三步，返回第三步.第四步：第四步：判断判断“r=0”r=0”是否是否成成立立.若是，若是，则则n 不是不是质质数数,结束算法；束算法；否否则则，将将i i的的值值增加增加1 1，仍用，仍用i i表示表示.你能你能写出写出“判断整数判断整数n(n2)n(n2)是否是否为质为质数数”的算法的算法吗？P4:探究探究12-假假如如你你参参加加一一个个猜猜商商品品价价格格的的活活动,只只要要在在规规定定时时间间内内大大体体猜猜出出某某商商品品的的价价格格,就就可可获获得得该该件件商商品品（每每猜猜一一次次，主主持持人人会会提提醒醒你你报价价是是高高了了还是是低低了了）.现现有有一一商商品品,价价格格在在0 014140000元元之之间间,采采取取怎怎样样的的策策略略才才能能在在较较短短时间时间内内说说出大体答案呢出大体答案呢?第一步第一步:报报“700”；第第二二步步:若若主主持持人人说说高高了了(说说明明答答案案在在0700之之 间间),就就 报报“350”,否否 则则(答答 数数 在在350700之之间间)报报“525”；第三步第三步:重复第二步的重复第二步的报报数方法取中数方法取中间间数数,直至得到直至得到大体答案大体答案.解决解决实际问题需要程序和步需要程序和步骤，解决数学，解决数学问题同同样需要程序和需要程序和步步骤13-例例2 2.用用二分法二分法设计设计一个求方程一个求方程 x2-2=0（x0）的近似根的算法的近似根的算法.(.(精确度精确度为为0.005)0.005)第一步：第一步：第二步：第二步：第三步：第三步：第四步：第四步：第五步：第五步：令令 ，给定精确度定精确度d.确定区确定区间 a，b，满足足f(a)f(b)0.0.取区取区间中点中点若若f(a)f(m)0,0,则含零点的区含零点的区间为否否则，含零点的区，含零点的区间为将新得到的含零点的区将新得到的含零点的区间仍仍记为 a,b;判断判断|a-b|d是否成立是否成立或或f(m)是否等于是否等于0.0.若是，若是，则m是方程的近似解；是方程的近似解；否否则，返回，返回 a,m,m，b.第三步第三步.14-分析分析分析分析问题问题 对对于区于区间间a,b 上上连续连续不断、不断、且且f(a)f(b)0的函数的函数y=f(x),通通过过不断地把函不断地把函数数f(x)的零点所在的区的零点所在的区间间一分二，使区一分二，使区间间的两个端点逐步逼近零点，的两个端点逐步逼近零点，进进而得到零点而得到零点近似近似值值的方法叫做的方法叫做二分法二分法.二分法二分法:ab|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 50.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=0.005.d=0.005.此步此步骤也是求的近似也是求的近似值的一个算法的一个算法.16-小小结：算法的特征是什么？算法的特征是什么？n明确性明确性n程序程序性性n有限性有限性算法的概念：算法的概念：算法通常指可以用来解决的某算法通常指可以用来解决的某一一类问题的步的步骤或程序，或程序，这些步些步骤或程序必或程序必须是明是明确的和有效的，而且能确的和有效的，而且能够在有限步之内完成的。在有限步之内完成的。17-3.有人有人对对歌德巴赫猜想歌德巴赫猜想“任何大于任何大于4的偶数都能的偶数都能写成两个奇写成两个奇质质数之和数之和”设计设计了如下操作步了如下操作步骤骤：第一步：第一步：检验6=3+36=3+3第二步：第二步：检验8=3+58=3+5第三步：第三步：检验10=5+510=5+5。利用利用计计算算机不断地机不断地进进行下去！行下去！请问请问：利用利用这这种程序能种程序能够证够证明猜想的正确性明猜想的正确性吗吗？这是一种算法是一种算法吗？概念辨析概念辨析18-