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

专题八之算法初步【知识概要】 一、算法的定义 对一类问题的机械的、统一的求解方法称为算法，算法是对特定问题求解步骤的一种描述. 现代意义的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤。 二、算法的五个特征 1. 确定性：算法的每一步必须是确切定义的，且无二义性，算法只有唯一的执行路径，对于相同的输入只能得出相同的输出。 2. 有限性：一个算法必须在执行有限次运算后结束. 在所规定的时间和空间内，若不能获得正确结果，其算法也是不能被采用的。 3. 可行性：算法中的每一个步骤必须能用实现算法的工具可执行指令精确表达，并在有限步骤内完成，否则这种算法也是不会被采纳的。 4. 算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤。 5. 有输出: 算法一定能得到问题的解，有一个或多个结果输出，达到求解问题的目的，没有输出结果的算法是没有意义的。 三、算法的描述 描述算法可以有不同的方式，常用的有自然语言、框图、伪代码、程序设计语言等。 1. 自然语言：自然语言就是人们日常使用的语言，如汉语、英语或数学语言等，使用自然语言描述算法的优点是通俗易懂，当算法中的操作步骤都是顺序执行时比较容易理解。缺点是如果算法中包括判断和转向，并且操作步骤较多时，就不那么直观清晰了。 2. 框图（流程图）：（共有顺序结构、选择结构、循环结构三种结构） 程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形。画程序框图的规则： （1）使用标准的框图符号。 （2）框图一般按从上到下、从左到右的方向画。 （3）除判断框外，大多数框图符号只一个进入点和一个退出点。判断框是具有超过一个退出点的唯一符号。 （4）在图形符号内描述的语言要非常简练清楚。 （5）流程线必须画箭头，因为它是反映流程的执行的先后次序的。 顺序结构：顺序结构是由若干个依次执行的处理步骤组成的，这是任何一个算法结构都离不开的最简单、最基本的结构。其流程图如图1所示。 选择结构：先进行判断，判断的结果决定后面的步骤，这样的结构称为选择结构，或称为条件分支结构。其流程图如图2所示。 循环结构：循环结构（重复结构）是指按照一定条件，反复执行某一操作的算法结构。在循环结构中，反复执行的处理步骤称为循环体。需要注意的是，循环结构中一定包含条件结构。其流程图如图3、图4所示。abbapyn 图1 图2panynapy 图3 图4 图3、图4均为循环结构，只是图3表示直到型循环，图4表示当型循环。 当型循环（while型）和直到型（until型）循环的区别是：当型循环是先判断（条件）再执行，而直到型循环是先执行后判断；当型循环是条件满足时执行有关操作，直到型循环是满足了条件就不再执行的有关操作。对同一个问题，既可以用当型循环来处理，也可以用直到型循环来处理。 3. 伪代码：我们在研究算法的时候，可以采用与程序设计语言类似的形式，我们称之为伪代码。它有5种语句：输入语句、输出语句、赋值语句、条件语句、循环语句。 （1）赋值语句：在表述一个算法时，经常要引入变量，并赋给变量一个值，用来表明赋给某一个变量一个具体的确定值的语句叫做赋值语句。 赋值语句用符号 “”或“”等表示。 （2）输入语句：用来实现算法的输入信息，本质是通过计算机的外设（如键盘等）把数据送到计算机内存。 输入语句用符号“read a, b”等表示。 （3）输出语句：用来输出算法的结果，本质是从计算机向外部输出设备（如显示器、打印机、磁盘等）输出数据。 输出语句用符号“print x”等表示。 （4）条件语句：一个选择结构，执行此算法时，要根据条件选择流程线的方向. 我们用条件语句来实现这一过程. 其一般形式是图5：bcaynif a then belse cend if 图5 （5）循环语句：一个循环结构，可以用循环语句来实现。 当循环次数已定，可用“”语句. “”语句的形式为： “初值”“终值”“步长”while p end whileyapn 当循环次数不能确定时，可用“”语句来实现循环。“”语句的形式为图6： 图6 四、算法案例 1. 辗转相除法与更相减损术 （1）辗转相除法：欧几里德辗转相除法找到的最大公约数的步骤是：计算出的余数，若，则为的最大公约数；若，则把前面的除数作为新的被除数，把余数作为新的除数，继续运算，直到余数为零，此时的除数即为自然数的最大公约数。 （2）更相减损术：我们以求119和85这两个数的最大公约数加以说明：以两数中较大的数减去较小的数，即，以差数34