山东省烟台市芝罘区高考数学知识点总结专题8算法初步新人教A版.doc

1、专题八之算法初步【知识概要】 一、算法的定义 对一类问题的机械的、统一的求解方法称为算法，算法是对特定问题求解步骤的一种描述. 现代意义的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤。 二、算法的五个特征 1. 确定性：算法的每一步必须是确切定义的，且无二义性，算法只有唯一的执行路径，对于相同的输入只能得出相同的输出。 2. 有限性：一个算法必须在执行有限次运算后结束. 在所规定的时间和空间内，若不能获得正确结果，其算法也是不能被采用的。 3. 可行性：算法中的每一个步骤必须能用实现算法的工具可执行指令精确表达，并在有限步骤内完成，否则这种算法也是不会被采纳的。 4. 算法一定要

2、根据输入的初始数据或给定的初值才能正确执行它的每一步骤。 5. 有输出: 算法一定能得到问题的解，有一个或多个结果输出，达到求解问题的目的，没有输出结果的算法是没有意义的。 三、算法的描述 描述算法可以有不同的方式，常用的有自然语言、框图、伪代码、程序设计语言等。 1. 自然语言：自然语言就是人们日常使用的语言，如汉语、英语或数学语言等，使用自然语言描述算法的优点是通俗易懂，当算法中的操作步骤都是顺序执行时比较容易理解。缺点是如果算法中包括判断和转向，并且操作步骤较多时，就不那么直观清晰了。 2. 框图（流程图）：（共有顺序结构、选择结构、循环结构三种结构） 程序框图又称流程图，是一种用规定的

3、图形、指向线及文字说明来准确、直观地表示算法的图形。画程序框图的规则： （1）使用标准的框图符号。 （2）框图一般按从上到下、从左到右的方向画。 （3）除判断框外，大多数框图符号只一个进入点和一个退出点。判断框是具有超过一个退出点的唯一符号。 （4）在图形符号内描述的语言要非常简练清楚。 （5）流程线必须画箭头，因为它是反映流程的执行的先后次序的。 顺序结构：顺序结构是由若干个依次执行的处理步骤组成的，这是任何一个算法结构都离不开的最简单、最基本的结构。其流程图如图1所示。 选择结构：先进行判断，判断的结果决定后面的步骤，这样的结构称为选择结构，或称为条件分支结构。其流程图如图2所示。 循环结

4、构：循环结构（重复结构）是指按照一定条件，反复执行某一操作的算法结构。在循环结构中，反复执行的处理步骤称为循环体。需要注意的是，循环结构中一定包含条件结构。其流程图如图3、图4所示。ABBAPYN 图1 图2PANYNAPY 图3 图4 图3、图4均为循环结构，只是图3表示直到型循环，图4表示当型循环。 当型循环（While型）和直到型（until型）循环的区别是：当型循环是先判断（条件）再执行，而直到型循环是先执行后判断；当型循环是条件满足时执行有关操作，直到型循环是满足了条件就不再执行的有关操作。对同一个问题，既可以用当型循环来处理，也可以用直到型循环来处理。 3. 伪代码：我们在研究算法

5、的时候，可以采用与程序设计语言类似的形式，我们称之为伪代码。它有5种语句：输入语句、输出语句、赋值语句、条件语句、循环语句。 （1）赋值语句：在表述一个算法时，经常要引入变量，并赋给变量一个值，用来表明赋给某一个变量一个具体的确定值的语句叫做赋值语句。 赋值语句用符号 “”或“”等表示。 （2）输入语句：用来实现算法的输入信息，本质是通过计算机的外设（如键盘等）把数据送到计算机内存。 输入语句用符号“Read a, b”等表示。 （3）输出语句：用来输出算法的结果，本质是从计算机向外部输出设备（如显示器、打印机、磁盘等）输出数据。 输出语句用符号“Print x”等表示。 （4）条件语句：一个

6、选择结构，执行此算法时，要根据条件选择流程线的方向. 我们用条件语句来实现这一过程. 其一般形式是图5：BCAYNIf A then BElse CEnd if 图5 （5）循环语句：一个循环结构，可以用循环语句来实现。 当循环次数已定，可用“”语句. “”语句的形式为： “初值”“终值”“步长”While P End whileYAPN 当循环次数不能确定时，可用“”语句来实现循环。“”语句的形式为图6： 图6 四、算法案例 1. 辗转相除法与更相减损术 （1）辗转相除法：欧几里德辗转相除法找到的最大公约数的步骤是：计算出的余数，若，则为的最大公约数；若，则把前面的除数作为新的被除数，把余数作为新的除数，继续运算，直到余数为零，此时的除数即为自然数的最大公约数。 （2）更相减损术：我们以求119和85这两个数的最大公约数加以说明：以两数中较大的数减去较小的数，即，以差数34和较小的数85构成新的一对数，对这一对数再用大数减去小数，即，再以差数51和较小的数34构成新的一对数，对这一对数，大数减去小数，这样的操作一直做下去，直到产生一对相等的数，这个数就是最大公约数。