天津第一中学数学算法初步资料理pdf

高三数学(理) 第二学期 新课预习 第九周 天津市立思辰网络教育有限公司 版权所有 1 /12 第二学期 第九周第二学期 第九周 课程内容 算法初步 2014-2015 学年 高三数学(理) 第二学期 新课预习 第九周 天津市立思辰网络教育有限公司 版权所有 2 /12 本周复习算法初步的内容本周复习算法初步的内容 一般地讲，算法是人们解决问题的固定步骤和方法在本模块中，我们应重点掌握的是 在数值计算方面的算法 高考新课程标准数学考试大纲对算法初步的要求是： （1）算法的含义、流程图：了解算法的含义，了解算法的思想；理解流程图的 三种基本逻辑结构：顺序结构、选择结构、循环结构 （2）基本算法语句：理解几种基本算法语句输入语句、输出语句、赋值语句、 选择语句、循环语句的含义 注意的是，考纲对算法的含义和算法的思想的要求是“了解”，而对流程图和基本算法 语句的要求是“理解”由此可见，复习中应把重点放在流程图和基本算法语句上，要对这 两方面的内容重点掌握、多加练习 表达算法的方法有自然语言、流程图和基本算法语句三种自然语言描述算法只是学 习算法的一个过渡，流程图和基本算法语句才是学习的重点，同时也是难点，尤其是选择 结构和循环结构，在复习中是重中之重 1算法的特征1算法的特征 （1）确定性：算法的确定性是指一个算法中每一步操作都是明确的，不能模糊或有 歧义，算法执行后一定产生明确的结果； （2）有穷性：算法的有穷性是指一个算法必须能够在有限个步骤之内把问题解决， 不能无限的执行下去； 高三数学(理) 第二学期 新课预习 第九周 天津市立思辰网络教育有限公司 版权所有 3 /12 （3）可行性：算法的可行性是指一个算法对于某一类问题的解决都必须是有效的， 切实可行的，并且能够重复使用 2、程序框图2、程序框图 基本的程序框有起始框，输入、输出框，处理框，判断框其中起始框是任何流程都 不可缺少的，而输入、输出框可以用在算法中任何需要输入、输出的位置程序框图中的 图框表示各种操作，图框内的文字和符号表示操作的内容，带箭头的流线表示操作的先后 次序 （1）顺序结构 顺序结构描述的是最自然的结构，它也是最基本的结构， 其特点是：语句与语句之间，框与框之间是按从上到下的顺 序进行，不能跳跃，不能回头，如图 1 表示的是顺序结构的 示意图，它的功能是：A 和B 两个框是依次执行的，只有在 执行完 A 框后，才能接着执行B 框 （2）选择结构 选择结构是依据指定条件选择不同的指令的控制结构选择结构和实际问题中的分类 处理与数学思想中的分类讨论思想是完全对应的 两种常见的选择结构如图 2 和图 3 所示 图 2 的功能是先判断 P 是否成立，若成立，再执行A 后脱离选择结构 图 3 的功能是根据给定的条件 P是否成立而选择 A 框或B 框，特别注意，无论条件 P 是否成立，只能执行A 框或B 框之一，不可能既执行 A 框又执行 B框，也不可能 A 框、B 框都不执行，无论执行哪条路径，在执行完 A 框或 B框之后，脱离本选择结构 （3）循环结构 循环结构就是根据指定条件决定是否重复执行一条或多条指令的控制结构它的特点 是：从某处开始，按照一定的条件反复执行某一处理步骤，其中反复执行的处理步骤称为 循环体 两种常见的循环结构如图 4 和图 5 所示 高三数学(理) 第二学期 新课预习 第九周 天津市立思辰网络教育有限公司 版权所有 4 /12 图 4 的功能是先执行 A框，然后判断给定的条件 P 是否成立，如果P 条件不成立，再 执行 A，然后再对 P条件作判断，如果 P 条件仍然不成立，又执行 A，如此反复执行 A，直到给定的 P 条件成立为止，此时不再执行 A，脱离本循环结构（又称直到型循 环） 图 5 的功能是先判断条件 P 是否成立，若成立，则执行 A 框，再判断条件 P是否成 立，若成立，又执行A 框，直到不符合条件时终止循环（又称当型循环），执行本循 环结构后的下一步程序 3、基本算法语句3、基本算法语句 算法是计算机科学的基础，本部分要学习的算法语句，是为了将算法转换为计算机能 够理解的程序语言和能在计算机上实现的程序所需要的语句，其作用就是实现算法与计算 机的转换 （1）赋值语句（1）赋值语句 赋值语句是用来表明赋给某一个变量一个具体的确定值的语句赋值语句的一般格式 为：变量名=表达式 赋值语句还应注意以下几点：赋值号左边只能是变量名字，而不是表达式；赋值 号左右不能对换；不能利用赋值语句进行代数式（或符号）的演算（如化简、因式分解 等）；赋值号与数学中的等号的意义不同 （2）输入语句（2）输入语句 输入语句主要用来给变量输入初始数据输入语句的一般格式是：变量=INPUT（“提 示内容”）输入语句要求输入的值只能是具体的常数，不能是函数、变量或表达式。 （3）输出语句3）输出语句 任何求解问题的算法，都要把求解的结果“输出”，这就需要有“输出语句”来控制输 出输出语句主要有 PRINT 语句，利用 PEINT 语句可以使结果在屏幕上显示出来 （4）条件语句4）条件语句 条件语句就是处理条件分支逻辑结构的算法语句计算机通常是按照程序中语句出现 的先后顺序依次往下执行的但有时需要根据某个给定条件是否满足而决定所要执行的语 句，这是就需要条件语句Basic 语言中的条件语句主要为 if 语句，if 语句的一般格式 是： IF 表达式 语句序列 1； ELSE 语句序列 2； END IF 高三数学(理) 第二学期 新课预习 第九周 天津市立思辰网络教育有限公司 版权所有 5 /12 该语句的功能为，如果表达式结果为真，则执行表达式后面的语句序列 1；如果表达式结 果为假，则执行 else 后面的语句序列 2 if 语句的最简单的格式是： 该语句的功能为，如果表达式结果为真，则执行表达式后面的语句序列 1，否则跳过语句 序列 1 （5）循环语句（5）循环语句 循环语句是用来处理算法中的循环结构的程序语言当遇到有规律的重复运算，或者 在程序中需要对某些语句进行重复的执行时，需要用循环语句进行控制Basic 程序语言 中常用的有两种循环语句：WHILE 循环和 UNTIL 循环 WHILE 循环的格式为： UNTIL 循环的格式为： WHILE 循环结构，首先要求对条件进行判断，如果条件为真，则执行循环体部分，每次 开始执行循环体前，都要判断条件是否为真这样重复执行，一直到条件为假时，就跳过 循环体部分，结束循环 UNTIL 循环结构，首选执行循环体，再检查条件，当条件不成立时，继续执行循环 体，当条件成立时，就跳过循环体部分，结束循环 （6）辗转相除法：（6）辗转相除法： 求最大公约数的方法就是辗转相除法也叫欧几里德算法，它是由欧几里德在公元前 300 年左右首先提出的利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数m除以较小的数n得到一个商 0 q 和一个余数 0 r ； 第二步：若 0 0 r = ，则n为 , m n的最大公约数；若 0 0 r ，则用除数n除以余数 0 r 得 到一个商 1 q 和一个余数 1 r ； IF 表达式 语句序列 1； END IF WHILE 条件 循环体 WEND DO 循环体 LOOP UNTIL 条件 高三数学(理) 第二学期 新课预习 第九周 天津市立思辰网络教育有限公司 版权所有 6 /12 第三步：若 1 0 r = ，则 1 r 为 , m n的最大公约数；若 1 0 r ，则用除数 0 r 除以余数 1 r 得 到一个商 2 q 和一个余数 2 r ； 依次计算直至 0 n r = ，此时所得到的 1 n r 即为所求的最大公约数 （7）更相减损术（7）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术 更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母之数，以少 减多，更相减损，求其等也，以等数约之 翻译出来为： 第一步：任意给出两个正数；判断它们是否都是偶数若是，用 2 约简；若不是，执 行第二步 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小 数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数 （8）秦九韶算法（8）秦九韶算法 应用秦九韶算法完成一般的多项式 f(x)=anx n +an-1x n-1 +.+a1x+a0 求值问题 f(x)=anx n +an-1x n-1 +.+a1x+a0 =( anx n-1 +an-1x n-2 +.+a1)x+a0 =( anx n-2 +an-1x n-3 +.+a2)x+a1)x+a0 =.=(.( anx+an-1)x+an-2)x+.+a1)x+a0 求多项式的值时，首先计算最内层括号内依次多项式的值，即 v1=anx+an-1 然后由内向外逐层计算一次多项式的值，即 v2=v1x+an-2 v3=v2x+an-3 . vn=vn-1x+a0 这样，把 n 次多项式的求值问题转化成求 n 个一次多项式的值的问题 观察秦九韶算法的数学模型，计算 vk 时要用到 vk-1 的值，若令 v0=an，我们可以得到下面 的递推公式： v0=an vk=vk-1+an-k(k=1,2,n) 这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。 （9）进位制 进位制 （9）进位制 进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号 的个数称为基数，基数为 n，即可称 n 进位制，简称 n 进制。现在最常用的是十进制，通 常使用 10 个阿拉伯数字 0-9 进行记数。对于任何一个数，我们可以用不同的进位制来表 示。比如：十进数 57，可以用二进制表示为 111001，也可以用八进制表示为 71、用十 六进制表示为 39，它们所代表的数值都是一样的。 一般地，若 k 是一个大于一的整数，那么以 k 为基数的 k 进制可以表示为： 110( )110 .(0,0,.,) nnknn a aa aakaa ak Ccb Dbc 解解：由流程图可知第一个选择框作用是比较 x 与 b的大小， 故第二个选择框的作用应该是比较 x 与 c的大小，故应选； 点评：点评：本题考查条件结构的程序框图，求解时，对字母比较难 理解，可以取一些特殊的数值，代进去，方便理解。从以上三题来 看，因为算法是新课程中的新增加的内容，因此它也必然是新高考 中的一个热点，应高度重视。 例 6例 6、右边是根据所输入的x值计算 y 值的一个算法程序, 若 x依次取数列 1 100 n ( ) nN + 中的前 200 项，则所得 y 值中的 最小值为 . （注：程序中的赋值符号“=”也可以写成“”或“:=”） 解解：1n200，所以， 100 99 100 n 1 1， 当 x0，即 0x1 时，由 y1x，得 1y2， 当 x0，即 100 99 x0 时，由 y1x，得 1y1 100 99 ， 所以，y 值中的最小值为 1。 点评点评：本题考查条件语句，与数列和不等式结合，属中等难度的试题。 例 7例 7、已知伪代码如下，则输出结果 S= . （注：程序中的赋值符号“=”也可以写成“”或“:=”） I0 S0 While I6 II+2 SS+I 2 End while Print S 解解：第一步：I2，S4，第二步：I4，S416，第三步：I6，S416 3656，所以，输出 56。 点评点评：这是一个当型循环语句，求解时，写出前面几步中循环体的结果即可。 例 8例 8、某电信部门规定：拨打市内电话时，如果通话时间不超过 3 分钟，则收取通话 费 0.2 元，如果通话时间超过 3 分钟，则超过部分以每分钟 0.1 元收取通话费（通话不足 1 分钟时按 1 分钟计），试设计一个计算通话费用的算法.要求写出算法，画出程序框图， 编写程序. 开始 输入abc ， ， xa = bx xb = xc = 输出x 结束 是 是 否 否 Read x If x 0 Then 1 yx + Else 1 yx End If 高三数学(理) 第二学期 新课预习 第九周 天津市立思辰网络教育有限公司 版权所有 10 /12 INPUT t IF t + 2010？ 输出S 结束 否 开始 1、阅读下列程序框图，该程序输出的结果是 2、如下图，给出了一个程序框图,其作用是输入x的值,输出相应的 y 的值,若要使输入的x 的值与输出的 y 的值相等,则这样的x的值的集合为 . 开始 y 输出 结束 2 x ？ x 输入 2 yx = 5 x ？ 23 yx = 1 y x = 1 图 是 否 是 否 3、右图是一程序框图，则其输出结果为 4、一个算法的程序框图如下图所示，若该程序输出的结果为 5 6 ，则判断框中应填入的条 件是（ ） A. 4 i B. 5 i C. 5 i D. 6 i B. 20 i = D. 20 i y = 7 输出 y 结束 开始 输出a(b +1) 输出a(b 1) 结束 开始 输入两个数a和b b a 是 否 图 4 高三数学(理) 第二学期 巩固练习 第九周 天津市立思辰网络教育有限公司 版权所有 6 /11 1、某店一个月的收入和支出总共记录了 N 个 数据 1 a ， 2 a ， N a ，其中收入记为正数，支出 记为负数。该店用下边的程序框图计算月总收 入 S 和月净盈利 V，那么在图中空白的判断框 和处理框中，应分别填入下列四个选项中的 AA0,V=S-T BA0, V=S+T w.w DAa? S=S+ 1 k(k+1) k=k+1 输出 S 结束 是 否 （第 8 题图） 高三数学(理) 第二学期 巩固练习 第九周 天津市立思辰网络教育有限公司 版权所有 9 /11 9、如图所示,程序框图(算法流程图)的输出结果是 A 1 6 B 25 24 C 3 4 D 11 12 10、执行右面的程序框图,如果输入的 10 N = ,那么输出的S = A 111 1+ 2310 + B 111 1+ 2310 + ！ ！ ！ C 111 1+ 2311