算法初步知识点及习题.docx

算法

算法是高中数学课程中的新增内容，是中国数学课程内容的一个新特色．“算法〞过程是指机械式地根据某种确定的步骤行事，通过一系列小的简洁计算操作完成困难计算的过程．算法的学习内容大致可分为三个步骤：用自然语言描绘算法；精确刻画算法(程序框图)；计算机实现执行算法(程序语言的描绘过程)．算法思想贯穿高中数学课程的相关部分．

【学问要点】

1．算法：算法可以理解为由根本运算及规定的运算依次所构成的完好的解题步骤，或者看成根据要求设计好的有限的精确的计算序列，并且这样的步骤或序列可以解决一类问题．现代意义上的“算法〞通常是指可以用计算机来解决的某一类问题的程序或步骤．

2．程序框图

程序框图：用一些通用的符号构成一张图来表示算法，这种图称为程序框图(程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形)．

用框图表示算法步骤的一些常用的图形符号：

程序框

名称

功能

终端框(起止框)

表示一个算法的起始与完毕

输入、输出框

表示一个算法输入与输出的信息

处理框(执行框)

赋值、计算

推断框

推断某一条件是否成立，成立时在出口处标明“是〞，不成立时标明“否〞

↓→

流程线(指向线)

指引流程图的方向

连接点

连接另一页或另一部分的框图

程序框图的三种根本逻辑构造：

依次构造：描绘的是最简洁的算法构造，语句与语句之间、框与框之间按从上到下的依次进展(如图9－1)．

图9－1

条件分支构造：根据指定条件选择执行不同指令的限制构造(如图9－2)．

图9－2

循环构造：根据指定条件确定是否重复执行一条或多条指令的限制构造(如图9－3)．

图9－3

3．几种根本算法语句

任何一个程序设计语言中，都包含五种根本的算法语句，即输入语句、输出语句、赋值语句、条件语句、循环语句．

输入语句与输出语句分别用来实现算法的输入信息、输出结果的功能；赋值语句是用来说明赋给某一个变量一个详细的确定值的语句；条件语句是处理条件分支逻辑构造的算法语句；循环语句是用来处理算法中的循环构造的语句．

4．中国古代算法案例：

更相减损之术、辗转相除法：求两个正数的最大公因数的方法．

辗转相除法算法步骤：第一步：用两数中较大数除以较小数，求商与余数．第二步：用除数除以余数．第三步：重复第二步，直到余数为0．第四步，得出两数的最大公约数，即余数0之前的余数．

更相减损术算法步骤：第一步：用较大数减去较小数，得到差．第二步：比较减数与差的大小，再用较大数减去较小数．第三步：重复第二步，直到差与减数相等为止．第四步：相等数即为最大公约数．

割圆术：用正多边形的面积渐渐靠近圆面积的算法求圆周率?．

秦九韶算法：求一元多项式的值的一种方法，递推关系为

【复习要求】

1．理解算法的含义，理解算法的思想．

2．理解程序框图的三种根本逻辑构造：依次构造、条件分支构造、循环构造．

3．理解几种根本算法语句——输入语句、输出语句、赋值语句、条件语句、循环语句的含义．

【例题分析】

例1如图(图9－4)所示，将一系列指令用框图的形式表示，箭头指向下一步的操作．请根据框图答复以下问题：

图9－4

(1)这个框图表示了怎样的算法

(2)输出的数是多少

【分析】由框图中的文字及图形符号表示的操作内容可知：此算法是“求1到50的与〞，由此可以算出输出的数．

解：(1)此框图表示的算法为：求1＋2＋3＋…＋50的与；

(2)易知所求与为1275．

【评析】程序框图主要包括三部分：表示相应操作的框，带箭头的流程线与框外必要的说明．读框图时要从这三个方面探讨，流程线反映了嘱咐执行的先后依次，主要看箭头方向，框及内外的文字说明说明了操作内容．常用这种方式考察对算法的理解与应用．

例2(1)如图9－5所示的是一个算法的程序框图，a1＝3，输出的结果为7，则a2的值为______．

图9－5

(2)如图9－6所示的是某个函数求值的程序框图，则满意该程序的函数解析式为_____．

图9－6

(3)如图9－7所示的是求某个数列与的程序框图，此程序输出的结果为_____．

图9－7

【分析】这三个小题的重点在于读懂框图．(1)只含有依次构造，(2)含有条件分支构造，说明函数的定义域为R，当x＜0时，遵从解析式f(x)＝3x－1，否则(即当x≥0时)，遵从解析式f(x)＝2－5x；(3)中有两个循环变量S、I，S是累加变量，I是计数变量；另外还要推断I的奇偶性，以此确定是加还是减．

解：(1)；(2)；

(3)S＝12－22＋32－42＋…＋992－1002＝－5050．

【评析】题(1)，只含有依次构造，所表示的算法比较简洁，只需根据框图箭头方向依次读出即可．题(2)含有条件分支构造，这是一个与分段函数有关的算法，框图中含有推断框．读包含有推断框的框图时，要特殊重视推断框内的条件与框外的文