当前位置:首页 >> 数学 >> (6)2017届高中数学一轮复习基础知识手册第六编 算法初步

(6)2017届高中数学一轮复习基础知识手册第六编 算法初步


第六编算法初步 1.算法的含义、程序框图 (1)了解算法的含义,了解算法的思想。 (2)理解程序框图的三种基本逻辑结构:顺序程序、条件结构、循环结构。 2.基本算法语句 了解几种基本算法语句——输入语句、输出语句、赋值语句、条件语句、循环语句的含义。 知识能力解读 知能解读(一)算法的概念 1.算法 算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。 2.算法的要求 (1)写出的算法必须能解决一类问题。 (2)要使算法尽量简单、步骤尽量少。 (3)要保证算法正确,且计算机能够执行。 知能解读(二)程序框图 1.定义 用一些通用图形个符号构成一张图来表示算法, 这种图称为程序框图 (简称框图或流程图) 。 2.常用的表示算法步骤的图形符号 图形符号 名称 功能 终端框(起止框) 表示一个算法的起始和结束 输入、输出框 处理框(执行框) 表示一个算法输入和输出的 信息 赋值、计算

判断框

判断某一条件是否成立, 成立 时在出口处标明“是”或“Y”; 不成立时标明“否”或“N” 连接程序框

流程线

连接点

连接程序框图的两部分

3.画程序框图的规则 (1)使用标准的框图符号。 (2)框图一般按从上到下、从左到右的方向画。 (3)除判断框外,大多数框图符号只有一个进入点和一个退出点,判断框是唯一具有超过 一个退出点的框图符号。 (4)在图形符号内描述的语言要非常精炼、清楚。 知能解读(三)算法的三种基本逻辑结构和框图表示 1.顺序结构 顺序结构是最简单的算法结构, 它由若干个依次执行的处理步骤组成, 它是任何一个算法都 离不开的一种算法结构, 可以用如图所示的流程图表示。 其中 A 和 B 两个框是依次执行的, 只有在执行完 A 框所指定的操作后,才能接着执行 B 框所指定的操作。

A

B

说明:顺序结构往往是从上到下的顺序,有时也有从左到右的。顺序结构常用于直接应用公 式的题型。 2.选择结构(条件结构) 在一个算法中,经常会遇到条件的判断。算法的流程根据条件是否成立有不同的流向,这种 根据条件作出判断,再决定执行哪一种操作的结构称为选择机构(条件结构) 。如图所示, 均为选择结构。图(1)为根据给定的条件 P 是否成立,而选择 A 框或 B 框,请注意无论条 件 P 是否成立,只能执行 A 框或 B 框之一,不可能执行 A 框又执行 B 框,也不可能 A,B 框都不执行。无论走哪一条路径,在执行完 A 框或 B 框之后,脱离本选择结构。图(2)为 当条件 P 成立时执行 A 框,当条件 P 不成立时不执行任何操作。

P 是 A B 否



P 否 A

(1)

(2)

说明: (1)选择结构与顺序结构的不同之处是它在执行下一语句时是有选择性的。 (2)在进行条件 P 的判断后可以不执行操作,而直接退出选择结构。 (3)选择结构在书写时要注意加上“是”或“否”,以便进行选择。 (4)在条件 P 的判断中只能存在“是”或“否”两种答案,而不能出现“不一定”这种现象。 3.循环结构 需要重复执行同一操作的结构称为循环结构, 即从某处开始, 按照一定的条件反复执行某一 处理步骤,反复执行的处理步骤称为循环体。图是一种常见的循环结构,它的功能是先执行 A,然后判断给定的条件 P 是否成立,如果条件 P 不成立,就继续执行 A,然后再对条件 P 进行判断,如果条件 P 仍然不成立,则仍然执行 A……如此反复执行 A,直到给定的条件 P 成立为止,此时不再执行 A,脱离本循环结构。另外,图所示的框图也是常见的一种循环结 构,它的功能是先判断条件 P 是否成立,如果条件 P 成立,则执行 A,然后再对条件 P 进 行判断, 如果条件 P 仍然成立, 则仍然执行 A……如此反复执行 A, 直到条件 P 不成立为止, 此时不再执行 A,脱离本循环结构。 说明: (1)理解两种常见的循环结构,即直到型(UNTIL 型)循环和当型(WHILE 型)循环以 及它们之间的相互转换。

A

A



P 是

P

是 否

(2)在理解循环体内部循环的含义及作用时,要知道循环体的循环次数或循环条件以及什 么时候循环结束。 (3)在加条件 P 时,一定要注意经有限次循环后能使循环结束,否则,将出现死循环,即 一个错误的循环结构。 4.三种基本结构的共同特点 (1)只有一个入口。 (2)只有一个出口。请注意一个菱形判断框有两个出口,而一个选择结构只有一个出口。 不要将菱形判断框的出口和选择结构的出口混为一谈。 (3)结构内的每一部分都有机会被执行到,也就是说对每一个框来说都应当有一条从入口 到出口的路径通过它。 像图的处理框没有一条从入口到出口的路径通过它, 就是不符合要求 的流程图。
A

A
P 是 否

B

(4)结构内不存在死循环,即无终止的循环。像图就是一个死循环。在流程图中是不允许 有死循环出现的。 三种基本结构的这些共同特点, 也是检查一个流程图或算法是否正确、 合理的方法和试金石。 知能解读(四)基本算法语句 1.赋值语句 赋值语句就是将表达式所代表的值赋给变量的语句,其格式为“变量=表达式”(或“变量←表 达式”) ,用符号“=”(或“←”)表示,“x=y”(或“x←y”)表示将 y 的值赋给 x,其中 x 是一 个变量,y 是一个与 x 同类型的变量或表达式。 (注:不同版本的算法语句略有不同) 说明: (1)左边只能是变量,而不能是表达式,例如 3=m(或 3←m)是错误的。赋值语句右边 表达式可以是一个常量、变量或含变量的运算式。 (2)赋值号左右不能兑换,赋值语句是将赋值号右边的表达式的值赋给左边的变量,例如 y=x(或 y←x) ,表示用 x 的值替代变量 y 原先的取值,不能改写为 x=y(或 x←y) ,因为后 者表示用 y 的值替代变量 x 原先的取值。 (3) 不能用赋值语句进行代数式的演算 (如化简、 分解因式等) , 如 y ? x ?1 ? ( x ?1)( x ? 1) 是不能实现的。在一个赋值语句中只能给一个变量赋值,不能出现两个或多个“=”。 (4)赋值号与数学计算中的等号的意义不同。赋值号左边的变量如果原来没有值,则在执 行赋值语句后,获得一个值;如果原来已有值,则执行该语句后,以赋值号右边表达式的值 替代该变量的原值,即将原值“冲掉”。如 N=N+1 在数学计算中是不成立的,但在赋值语句 中,意思是将 N 的原值加 1 再赋给 N,即 N 的值加 1。 2.输入、输出语句 输入、输出语句是分别用来实现算法的输入信息、输出结果的功能的语句。 输入语句格式“INPUT a,b”(或“Read a,b”)表示输入的数据依次赋给 a,b。 输出语句格式“PRINT x”(或“Print x” )表示输出运算结果 x 。 “PRINT x , y” (或 “Print
2

x,y”)表示依次输出运算结果 x,y。 (1)输入语句还可以表示为“INPUT “提示内容”;变量”; (2)输入语句中的变量表示的只 能是具体的常数,不能是函数、变量或表达式; (3)输出语句 PRINT(或 Print)可以输出 常量、变量或表达式的值。 3.条件语句 在处理选择结构的算法中,运用条件语句来实现。 条件语句的一般格式如下:
IF 条件 THEN 语句体1 ELSE 语句体2 END IF

IF 条件 THEN 语句体 END IF

?

?

说明: (1)在执行?这种格式的条件语句时,若表达式(即条件)为真,则执行“THEN 分支”, 若表达式为假,则执行“ELSE 分支”,然后结束这一条件语句。其对应的程序框图如图。

满足条件? 是 THEN分支

否 ELSE分支

满足条件? 是 否 THEN分支

(2)在执行?这种格式的条件语句时,只对表达式的结果进行判断,若表达式为真,则执 行“THEN 分支”,否则跳过“THEN 分支”执行下一语句,其对应的程序框图如图。 (3) 在?这种格式的条件语句中, “THEN 分支”与“ELSE 分支”执行且只执行其中一个分支。 (4)“THEN 分支”与“ELSE 分支”语句一般在前面加空格以便阅读。 (5)条件语句主要用来实现算法中的条件结构,如判断一个数的正负、比较两数的大小、 对一组数据进行排序等就需要用到条件语句。 4.循环语句 用来实现循环结构的语句。 (1)WHILE 语句的一般格式
WHILE 表达式(条件) 循环体 WEND

(2)For 语句的一般格式(苏教版)
For 循环变量 From “初值”To “终值”Step “步长” 循环体 End For

(3)UNTIL 语句一般格式
DO 循环体 LOOP UNTIL 条件

说明: (1)当程序执行时,遇到 WHILE 语句,先判断条件是否成立,若成立,则执行 WHILE 和 WEND 之间的循环体,然后再判断上述条件,再次执行循环体,这个过程反复执行,直到

某一次不符合条件为止,这时不再执行循环体,将跳到 WEND 语句后,执行 WEND 后面的 语句。 (2)当程序执行时,遇到 For 语句,首先把初值赋给循环变量,记下终值和步长,并比较 初值和终值,若初值没有超过终值,就开始执行 For 后面的语句,执行到 End For 语句时, 计算机让循环变量增加一个步长值, 然后用增值后的循环变量值与终值比较, 如果超过终值, 就执行 End For 后面的语句,否则执行 For 后面的语句。 (3)循环变量是用于控制算法中循环次数的变量,起计数作用。初值和终值,是循环开始 和结束时循环变量的值,步长是指循环变量每次增加的值。步长为 1 时可以省略不写,但为 其他值时,必须写,不能省略。 (4)当计算机遇到 UNTIL 语句时,先执行一次 DO 和 UNTIL 之间的循环体,再对 UNTIL 后的条件进行判断。如果条件不符合,继续执行循环体,然后再检查上述条件,如果条件仍 不符合,再次执行循环体,直到条件符合时为止。这时,计算机将不再执行循环体,执行 UNTIL 语句之后的语句。 (5)循环语句主要用来处理算法中的循环结构,在处理一些有规律的计算问题,如果加求 和、累乘求积等问题时,常常用循环语句编写程序。 (6)用 For 循环编写程序时要注意设定好循环变量的初值、步长和终值,避免出现多一次 循环或少一次循环的情况;用 WHILE 循环编写程序时,一定要注意表达式的写法,当表达 式为真时执行循环体, 表达式为假时结束循环; UNTIL 语句是先执行循环体, 再判断条件, 因此在任何一个 UNTIL 语句中, 循环体至少要执行一次。 简单地讲, “WHILE”符合就循环, “UNTIL”符合就停止。 知能解读(五)辗转相除法与更相减损术 辗转相除法与更相减损术都是求两数最大公约数的方法。 说明: (1)用辗转相除法求 a,b 的最大公约数的步骤: ?用较大的数 a 除以较小的数 b 得到一个商 S0 和一个余数 r0 。 ?若 r0 ? 0 ,则 b 为 a,b 的最大公约数;若 r0 ≠0 ,则用除数 b 除以余数 r0 得到一个商 S1 和 一个余数 r1 。 ?若 r1 ? 0 ,则 r0 为 a,b 的最大公约数; r1≠0 ,则用 r0 除以余数 r1 得到一个商 S2 和一个 余数 r2 。 如此下去,直至余数 ri ? 0 ,则 ri ?1 为 a,b 的最大公约数。 (2)用更相减损术求两个数的最大公约数的步骤: 所谓更相减损术就是用两个数中较大的数减去较小的数,用差和较小的数构成新的一对数。 对于这一对数,再用大数减去小数。用同样的方法一直做下去,直到得到两个相等的数,这 个数就是最大公约数。在《九章算术》中记载了用更相减损术求最大公约数的步骤:可半者 半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之。 翻译为:?任意给定两个正数,判断它们是否都是偶数。若是,用 2 约简;若不是,执行第 ?步。?用较大的数减去较小的数,接着把较小的数与所得的差比较,并用大数减小数。继 续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所 求的最大公约数。 (3)辗转相除法与更相减损术之间的关系。 ?辗转相除法与更相减损术都是求最大公约数的方法。在计算上,辗转相除法以除法为主, 更相减损术以减法为主;在计算次数上,辗转相除法计算次数相对较少,特别是当两个数字 大小差别较大时计算次数的区别较明显; 从结果体现形式来看, 辗转相除法是以相除余数为 0 而得到结果的,而更相减损术则是以减数与差相等而得到结果的。 ?辗转相除法的理论依据是:由 a ? nb ? r→r=a-nb 得 a,b 与 b,r 有相同的公约数;更 相减损术的理论依据是:由 a ? b ? r→a ? b ? r 得 a,b 与 b,r 有相同的公约数。 知能解读(六)秦九韶算法和进位制 1.应用秦九韶算法完成一般多项式 f ( x) ? an x ? an?1x
n n?1

? …? a1x ? a0 的求值问题。

f ( x) ? an xn ? an?1xn?1 ? …? a1x ? a0 ? (an xn?1 ? an ?1xn?2 ? …? a1) x ? a0 ? ((an xn?2 ? an?1xn?3 ? …? a2) x ? a1) x ? a0 ? … ? (…((an x ? an?1 ) x) ? an?2 ) x ? …? a1 ) x ? a0
求多项式的值时,首先计算最内层括号内一次多项式的值,即 u1 ? an x ? an?1 ,然后由内向 外逐层计算一次多项式的值,即 u2 ? u1 x ? an?2 , u3 ? u2 x ? an?3 ,…, un ? un?1 x ? a0 ,这 样,把 n 次多项式的求值问题转化成求 n 个一次多项式值的问题。 2.进位制是一种计数方式,用有限的数字在不同的位置表示不同的数值,可使用数学符号的 个数称为基数,基数为 n,即可称 n 进位制,简称 n 进制,现在最常用的是十进制,通常使 用 10 个阿拉伯数字 0~9 进行记数,对于任何一个数,我们可以用不同的进位制来表示,比 如:十进制数 57,可以用二进制表示为 111001,也可以用八进制表示为 71,它们所代表的 数值都是一样的。 一般地,若 k 是一个大于 1 的整数,那么以 k 为基数的 k 进制数可以表示为: an an?1…a1a0( k ) (an , an?1 ,…, a1a0 ? N ,0 ? an ? k ,0≤an?1, an?2 ,…, a0 ? k ) 。而表示各种进位 制数一般在数字右下方加注来表示,如 111001(2)表示二进制数,34(5)表示五进制数。 R 进制转化成十进制的方法:数码乘以相应权之和。 如:

5 4 3 2 0 ( 111011 ) ?136?8 =1? 82 +3?8+6 ?80 =94 。 2 =1? 2 +1? 2 +1? 2 +0 ? 2 +1? 2+1? 2 =59 ,

十进制数转化成 r 进制数的方法:连续除以基,直至商为 0,从低到高记录余数。如:把十 进制数 159 转换成八进制数。
8 159 8 19 8 2 0 余7 余3 余2 2 3 7

(159)10=(237)8

知能解读(六)秦九韶算法和进位制 思想方法(一)转化思想 程序框图与程序是描述算法的两种重要语言, 熟练地进行二者的互化, 是灵活描述某一算法 的基础。 思想方法(二)递归法 递归法是数学中非常重要的方法,比如数列中的累加、累乘、递推公式等都是常见的递归。 在算法中,我们可通过赋值语句和循环语句来实现递归。 规律技巧(二)画流程图,写伪代码(苏教版) 1.利用顺序结构绘制算法流程图,利用赋值、输入、输出语句书写伪代码 当所需解决的问题较为简单, 只要依次进行多个处理就能完成时, 通过顺序结构来绘制算法 流程图,用赋值、输入、输出语句来书写伪代码。 2.利用选择结构绘制算法流程图,利用条件语句书写伪代码 解决问题的过程中,必须先根据条件作出判断,再决定执行哪一种操作,画流程图时必须通 过选择结构实现,写伪代码时也必须用条件语句描述。 3.利用循环结构绘制算法流程图,利用循环语句书写伪代码 当需要解决的问题需要多次重复相同的步骤时, 要实现算法必须通过循环结构来实现, 伪代 码的书写也必须用循环语句来描述。 高考命题研究 程序框图是高考必考知识点,以选择题、填空题的形式出现,主要考查循环结构程序框图。 其中读出程序框图的功能,求出输出结果,根据题目条件补充判断框内的条件是高考热点。

有时还会与分段函数求值、数列求和或求积、统计与概率等知识综合考查,难度不大。 高考热点(一)基本算法语句 计算机程序设计语言包含以下五个基本算法语句:输入语句、输出语句、赋值语句、条件语 句、循环语句,它们与算法的三种基本结构式相互对应的。其中条件语句、循环语句是重点 考查的内容,常以选择题、填空题的形式考查,重在考查对算法语句的理解和应用。 高考热点(二)程序框图 程序框图是高考新课程标准的新增内容,主要以客观题出现,考查最多的是循环结构。算法 和程序框图常见的题型有两种:一种是阅读程序框图,写出执行结果;另一种是填写程序框 图的空白部分。 高考热点(三)算法与其他知识结合 在知识交汇处命题是高考命题的一个原则, 算法作为新增内容, 它与其他知识的结合也是高 考热点,它常与函数、数列、统计、概率等结合在一起考查。 附录常用公式定理 常用符号 图形符号 名称 终端框(起止框) 输入、输出框 处理框(执行框) 判断框

流程线

连接点


赞助商链接
更多相关文档:
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com