《算法的概念》.ppt

1、第一章 算法初步 1.1.1 算法的概念,我们从小学就开始接触算法，熟悉许多问题的算法。如，做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体体现。广义地说，算法就是做某一件事的步骤或程序。菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。,在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。(古代的计算工具：算筹与算盘. 20世纪最伟大的发明：计算机，计算机是强大的实现各种算法的工具。),一、引入,一个农夫带着一只狼、一头山羊和一篮蔬菜要过河

2、，但只有一条小船。乘船时,农夫只能带一样东西。当农夫在场的时候,这三样东西相安无事，一旦农夫不在，狼会吃羊，或羊会吃菜。请设计一个方案，使农夫能安全地将这三样东西带过河。,S1:农夫带羊过河;,S2:农夫独自回来;,S3:农夫带狼过河;,S4:农夫带羊回来;,S5:农夫带蔬菜过河;,S6:农夫独自回来;,S7:农夫带羊过河。,S1：把九枚硬币平均分成三份，取其中两份放天平上称，若平衡则重的在剩下的一份里，若不平衡则在重的一份里；,S2：在重的一份里取两枚放天平的两边，若平衡则剩下的一枚就是所找的，若不平衡则重的那枚就是所要找的。,二、提出问题,1、现有九枚硬币，有一枚略重，你能用天平(不用砝码

3、)将其找出来吗？设计一种最有效的方法，解决这一问题。,2:用加减消元法解二元一次方程组 的具体步骤是什么？,+2，得 5x=1 . ,解，得 .,-2，得 5y3 . ,解，得 .,第一步，,第二步，,第三步，,第四步，,第五步，,得到方程组的解为 .,第一步， - ，得 . ,第二步，解 ，得 .,第三步， - ，得 . ,第四步，解 ，得 .,根据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进行，这五个步骤就构成了解二元一次方程组的一个“算法”.我们再根据这一算法编制计算机程序，就可以让计算机来解二元一次方程组.,阅读P2-3,算法通常指可以用来解决的某一类问题的步骤或程序，这

4、些步骤或程序必须是明确的和有效的，而且能够在有限步之内完成的。,三、概念,一般来说，“用算法解决问题” 可以利用计算机帮助完成。,四、算法的步骤设计,例1.写出交换两个大小相同的杯子中的液体(A水、 B酒) 的一个算法。,S1：找一个大小与A相同的空杯子C。,例1.写出交换两个大小相同的杯子中的液体(A水、 B酒) 的一个算法。,S1：找一个大小与A相同的空杯子C。,S2：将A中的水倒入C中。,四、算法的步骤设计,例1.写出交换两个大小相同的杯子中的液体(A水、 B酒) 的一个算法。,S1：找一个大小与A相同的空杯子C。,S2：将A中的水倒入C中。,S3：将B中的酒精倒入A中。,四、算法的步骤

5、设计,例1.写出交换两个大小相同的杯子中的液体(A水、 B酒) 的一个算法。,S1：找一个大小与A相同的空杯子C。,S4：将C中的水倒入B中，结束。,S2：将A中的水倒入C中。,S3：将B中的酒精倒入A中。,四、算法的步骤设计,2、如果要判断7是否为质数，如何设计算法步骤？,第一步，用2除7，得到余数1,所以2不能整除7.,第四步，用5除7，得到余数2,所以5不能整除7.,第五步，用6除7，得到余数1,所以6不能整除7.,第二步，用3除7，得到余数1,所以3不能整除7.,第三步，用4除7，得到余数3,所以4不能整除7.,第六步，所以7是质数.,3、如果要判断35是否为质数，如何设计算法步骤？,

6、第一步，用2除35，得到余数1,所以2不能整除35.,第二步，用3除35，得到余数2,所以3不能整除35.,第三步，用4除35，得到余数3,所以4不能整除35.,第四步，用5除35，得到余数0,所以5能整除35.,第五步，所以35不是质数.,4、整数89是否为质数？如果让要判断89是否为质数，按照上述算法需要设计多少个步骤？,第一步，用2除89，得到余数1,所以2不能整除89.,第二步，用3除89，得到余数2,所以3不能整除89.,第三步，用4除89，得到余数1,所以4不能整除89., 第八十七步，用88除89，得到余数1,所以88不能 整除89.,第八十八步，所以89是质数.,这种写法不能算

7、是一个正规算法,思考:用288逐一去除89求余数，需要87个步骤，这些步骤基本是重复操作，我们可以按下面的思路改进这个算法，减少算法的步骤.,（1）用i表示288中的任意一个整数，并从2开始取数；,（2）用i除89，得到余数r. 若r=0，则89不是质数；若r0，将i用i+1替代，再执行同样的操作；,（3）这个操作一直进行到i取88为止.,你能按照这个思路，设计一个“判断89是否为质数”的算法步骤吗？,用i除89，得到余数r；,令i=2；,若r=0，则89不是质数，结束算法；若r0，将i用i+1替代；,判断“i88”是否成立？若是，则89是质数，结束算法；否则，返回第二步.,第一步，,第四步，

8、,第三步，,第二步，,算法设计:,一般地，判断一个大于2的整数是否为质数的算法步骤如何设计？,第一步，给定一个大于2的整数n；,第二步，令i=2；,第三步，用i除n，得到余数r；,第四步，判断“r=0”是否成立.若是，则n 不是质数，结束算法；否则，将i 的值增加1，仍用i表示；,第五步，判断“i(n-1)”是否成立，若是， 则n是质数，结束算法；否则，返回 第三步.,S1：令f(x)=x2-2，因为f(1)0,所以设a=1,b=2。,S2：令m= , 判断f(m)是否为0。若是0，则m为所求；若否，则继续判断f(a)f(m)大于0还是小于0 。,S3：若f(a)f(m) 0，则令a=m；否则

9、，令b=m 。,S4:判断 |a-b|0.005是否成立？若是，则a或b(或区间上任意值)为满足条件的近似根；若否，则返回S2。,实际上,上述步骤就是在求 的近似值。,算法设计:,5、用二分法设计一个求方程 的近似正根的算法，精确度0.005。,第一步，取函数f(x)，给定精确度d.,第二步，确定区间a，b，满足f(a)f(b)0.,第五步，判断a,b的长度是否小于d或f(m)是否等于0. 若是，则m是方程的近似解；否则，返回第三步.,第三步，取区间中点 .,第四步，若f(a)f(m)0,则含零点的区间 为a,m,否则，含零点的区间为m，b.,将新得到的含零点的区间仍记为a,b;,函数f(x)

10、的图象是一条连续不断的曲线，用“二分法”求方程 f(x)=0的近似解的常用算法设计：,练习： P5练习：1，2.,第一步，给定一个正实数r.,第三步，得到圆的面积S.,1、算法步骤：,第二步，计算以r为半径的圆的面积 .,2、算法步骤：,第一步，给定一个大于1的整数n；,第二步，令i=1；,第三步，用i除n，得到余数r；,第四步，判断“r=0”是否成立. 若是，则i是n的因数,输出i; 否则，不是n的因数，,第六步，判断“in”是否成立，若是， 结束算法；否则，返回第三步.,第五步，使i值增加1，仍用i表示，,四、小结作业,1.算法定义的理解：在数学中，现代意义上的 “算法”通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成.,2.算法的要求：,(1)写出的算法，必须能解决一类问题(例如解任意一个二元一次方程组)，并且能重复使用；,(2)算法过程要能一步一步执行，每一步执行的操作,必须确切，不能含混不清，而且在有限步之内完成后能得出结果。,3.算法的基本特征:,明确性：算法对每一个步骤都有确切的，能有效执行且得到确定结果的，不能模