专题八之算法初步知识点总结及分析

专题八之法初步知识总结及分析【知识概一、算的定义对一类问题的机械的统一的求解方法称为算法算法是对特定问题求解步骤的一种描述.现代意义的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤。二、算的五个特征●确定性：算法的每一步必须是确切定义的，且无二义性，算法只有唯一的执行路径，对于相同的输入只能得出相同的输出。●有限性：一个算法必须在执行有限次运算后结束.在所规定的时间和空间内，若不能获得正确结果，其算法也是不能被采用的。●可行性算法中的每一个步骤必须能用实现算法的工具——可执行指令精确表达，并在有限步骤内完成，否则这种算法也是不会被采纳的。●算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤。●有输出:算法一定能得到问题的解，有一个或多个结果输出，达到求解问题的目的，没有输出结果的算法是没有意义的。三、算的描述描述算法可以有不同的方式，常用的有自然语言、框图、伪代码、程序设计语言等。●自然语言：自然语言就是人们日常使用的语言，如汉语、英语或数学语言等使用自然语言描述算法的优点是通俗易懂当算法中的操作步骤都是顺序执行时比较容易理解点是如果算法中包括判断和转向且操作步骤较多时，就不那么直观清晰了。●框图（流程图顺序结构、选择结构、循环结构三种结构）程序框图又称流程图是一种用规定的图形指向线及文字说明来准确直观地表示算法的图形。画程序框图的规则：（1）使用标准的框图符号。（2）框图一般按从上到下、从左到右的方向画。（3）除判断框外，大多数框图符号只一个进入点和一个退出点。判断框是具有超过一个退出点的唯一符号。（4）在图形符号内描述的语言要非常简练清楚。壹

（5）流程线必须画箭头，因为它是反映流程的执行的先后次序的。顺序结构顺序结构是由若干个依次执行的处理步骤组成的这是任何一个算法结构都离不开的最简单、最基本的结构。其流程图如图所示。选择结构先进行判断判断的结果决定后面的步骤这样的结构称为选择结构，或称为条件分支结构。其流程图如图所示。循环结构：循环结构（重复结构）是指按照一定条件，反复执行某一操作的算法结构。在循环结构中，反复执行的处理步骤称为循环体。需要注意的是，循环结构中一定包含条件结构。其流程图如图、图所示。A

N

P

B图1

A

B图2AAN

P

P

N图3

图4图3、图4为循环结构，只是图3表示直到型循环，图表示当型循环。当型循环（型）和直到型（until型）循环的区别是：当型循环是先判断（条件）再执行，而直到型循环是先执行后判断；当型循环是条件满足时执行有关操作直到型循环是满足了条件就不再执行的有关操作对同一个问题既可以用当型循环来处理，也可以用直到型循环来处理。伪代码们在研究算法的时候以采用与程序设计语言类似的形式，我们称之为伪代码它有5种语句输入语句输出语句赋值语句条件语句、循环语句。（1）赋值语句：在表述一个算法时，经常要引入变量，并赋给变量一个值，用来表明赋给某一个变量一个具体的确定值的语句叫做赋值语句。赋值语句用符号“或xy”等表示。（2）输入语句：用来实现算法的输入信息，本质是通过计算机的外设（如键盘等）把数据送到计算机内存。输入语句用符号“Reada,b等表示。（3输出句用来输出算法的结果本质是从计算机向外部输出设如贰

显示器、打印机、磁盘等）输出数据。输出语句用符号“Printx”等表示。（4）条件语句：一个选择结构，执行此算法时，要根据条件选择流程线的方向.我们用条件语句来实现这一过程.其一般形式是图5：

NAIfthenBif图（5）循环语句：一个循环结构，可以用循环语句来实现。▲当循环次数已定，可用“For”语句.“For”语句的形式为：FIfro值“终值”“步长”Endfor▲当循环次数不能确定时，可用“While”语句来实现循环While”语句的形式为图6WhilePA

…P

Endwhile四、算案例

N

图6●辗转相除法与更相减损术（）辗转相除法：欧几里德辗转相除法找到ab最大公约数的步骤是：计算出a的余r，若r0，为a,b的最大公约数；若r0则把前面的除b作为新的被除数，把余r作为新的除数，继续运算，直到余数为零，此时的除数即为自然b的最大公约数。（2更相减损术：我们以11985这两个数的最大公约数加以说明：以两数中较大的数减去较小的数即

1934

以差数34和较小