- 184.00 KB
- 2021-07-01 发布
- 1、本文档由用户上传,淘文库整理发布,可阅读全部内容。
- 2、本文档内容版权归属内容提供方,所产生的收益全部归内容提供方所有。如果您对本文有版权争议,请立即联系网站客服。
- 3、本文档由用户上传,本站不保证质量和数量令人满意,可能有诸多瑕疵,付费之前,请仔细阅读内容确认后进行付费下载。
- 网站客服QQ:403074932
一.学习目标
1.了解算法的含义,了解算法的思想;理解程序框图的三种基本逻辑结构:顺序结构、条件结构、循环结构.
2.理解几种基本算法语句——输入语句、输出语句、赋值语句、条件语句、循环语句的含义.
3.初步了解几个典型的算法案例.
二.知识要点
1.算法通常是指可以用计算机来解决某一类问题的程序或步骤,必须是明确和有序的,而且能够在有限步之内完成.
2.程序框图又称流程图,是一种用规定的图形
、指向线及文字说明来准确、直观地表示算法的图形.通常程序框图由程序框和流程线组成,一个或几个程序框的组合表示算法中的一个步骤,流程线带方向箭头,按照算法进行的顺序将程序框连接起来.
3.三种基本逻辑结构
(1)顺序结构是由若干个依次执行的处理步骤组成的,其结构形式为:
(2)条件结构是指算法的流程根据给定的条件是否成立而选择执行不同的流向的结构形式,即:
(3)循环结构是指从某处开始,按照一定的条件反复执行处理某一步骤的情况.反复执行的处理步骤称为循环体.循环结构又分为当型循环
和直到型循环
.结构形式为:
4.基本算法语句
(1)输入、输出语句和赋值语句:
输入语句格式:INPUT“提示内容”;变量 ;
输出语句格式:PRINT“提示内容”;表达式 ;
赋值语句格式:变量=表达式 .
(2)条件语句:
①框图:
②条件语句格式:
IF—THEN格式
IF—THEN—ELSE格式
5.循环语句
循环语句的格式
①UNTIL语句
②WHILE语句
③顺序结构是每个算法结构都含有的,而对于循环结构有重复性,条件结构具有选择性没有重复性,并且循环结构中必定包含一个条件结构,用于确定何时终止循环体.循环结构和条件结构都含有顺序结构.
④利用循环结构表示算法,第一要先确定是利用当型循环结构,还是直到型循环结构;第二要选择准确的表示累计的变量;第三要注意在哪一步开始循环,满足什么条件不再执行循环体.
6.算法案例
(1)辗转相除法与更相减损术
①辗转相除法:求两个正整数的最大公约数的方法,用较大的数m除以较小的数n得到余数r,反复操作,直到余数为0为止,即m=nt+r(0≤r<n).因此要用“后测试型”循环语句表示,其程序如下:
INPUT m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
(2)秦九韶算法
n次多项式
f(x)=anxn+an-1xn-1+…+a1x+a0
=(anxn-1+an-1xn-2+…+a1)x+a0
…
=(…((anx+an-1)x+an-2)x+…+a1)x+a0
得到递推公式
v0=an且v =v -1x+an- ,其中 =1,2,…,n
其算法可用循环语句来实现.
(3)进位制
①将十进制数化为二进制数的算法称为除2取余法;将十进制数化为 进制数的算法称为除 取余法.
②将 进制数化为十进制数的算法步骤为:
第一步:从左到右依次取 进制数anan-1…a1a0( )各位上的数字乘以 的幂, 的幂从n开始取值,每次递减1,递减到0,即an· n,an-1· n-1,…,a1· ,a0· 0;
第二步:把所有积加起来,就得到十进制数.
三.高考类型分析
例1. (1)执行下面的程序框图,如果输入的t∈[-1,3],则输出的s属于( )
A.[-3,4] B.[-5,2]
C.[-4,3] D.[-2,5]
(2)执行下面的程序框图,若输入的ε的值为0.25,则输出的n的值为____.
(3)阅读如下程序框图,如果输出i=5,那么在空白矩形框中应填入的语句为( )
A.S=2*i-2 B.S=2*i-1
C.S=2*i D.S=2*i+4
【分析】(1)条件结构、框图功能是求分段函数的值域.
(2)根据运行顺序计算出的值,当≤ε时输出n的值,结束程序.n为循环次数.
(3)根据程序框图表示的算法对i的取值进行验证.
【解析】(1)因为t∈[-1,3],当t∈[-1,1)时,s=3t∈[-3,3);当t∈[1,3]时,s=4t-t2=-(t2-4t)=-(t-2)2+4∈[3,4],所以s∈[-3,4].
(3)当i=2时,S=2×2+1=5<10;当i=3时,仍然循环,排除D;当i=4时,S=2×4+1=9<10;当i=5时,不满足S<10,即此时S≥10,输出i.此时A项求得S=2×5-2=8,B项求得S=2×5-1=9,C项求得S=2×5=10,故只有C项满足条件.
【评析】(1)循环结构中的条件判断
循环结构中的条件是高考常考的知识点,主要是控制循环的变量应该满足的条件是什么.满足条件则进入循环或者退出循环,此时要特别注意当型循环与直到型循环的区别.
(2)条件结构中的条件判断
条件结构中条件的判断关键是明确条件结构的功能,然后根据“是”的分支成立的条件进行判断.
(1)下面程序运行的结果为( )
n=10
S=100
DO
S=S-n
n=n-1
LOOP UNTIL S<=70
PRINT n
END
A.4 B.5 C.6 D.7
【解析】第一次循环后,S=90,n=9,90>70,不满足要求,继续运行;
第二次循环后,S=81,n=8,81>70,不满足要求,继续运行;
第三次循环后,S=73,n=7,73>70,不满足要求,继续运行;
第四次循环后,S=66,n=6,66<70,满足条件,结束循环.
【点评】1.在用WHILE语句和UNTIL语句编写程序解决问题时,一定要注意它们的格式及条件的表述方法.WHILE语句中是当条件满足时执行循环体,而UNTIL语句中是当条件不满足时执行循环体.
(2)下面程序运行后输出的结果为( )
a=0
j=1
WHILE j<=5
a=(a+j) MOD 5
j=j+1
END
a
A.0 B.1 C.2 D.4
【解析】当j=1时,余数a=1;
当j=2时,余数a=3;当j=3时,余数a=1;
当j=4时,余数a=0;当j=5时,余数a=0;
当j=6时,不满足条件,此时退出循环.
【点评】1.在解答本题时,易错选D而导致错误,错误原因是:对循环过程不理解,误认为j=1时,余数a=0,即j=1时,没有执行第一次循环.其错误过程如下:当j=1时,余数a=0;当j=2时,余数a=2;当j=3时,余数a=0;当j=4时,余数a=4;当j=5时,余数a=4.
2.解决算法语句的有关问题时,还有以下几点易造成失误,备考时要高度关注:
(1)对基本算法语句的功能及格式要求不熟悉.
(2)条件语句中的嵌套结构混乱,不能用分段函数
(1)用辗转相除法或更相减损术求375和85的最大公约数;
(2)用秦九韶算法计算f(x)=x5+2x4+3x3+4x2+5x+6在x=2时的值;
(3)将七进制数235(7)转化为八进制数.
【解析】(1)用辗转相除法:
375=85×4+35
85=35×2+15
35=15×2+5
15=3×5+0
∴375与85的最大公约数为5.
用更相减损术:
375-85=290
290-85=205
205-85=120
120-85=35
85-35=50
50-35=15
35-15=20
20-15=5
15-5=10
10-5=5.
∴375与85的最大公约数为5.
(3)先化成十进制,再化成八进制.
235(7)=2×72+3×7+5=124
∴124=174(8),即235(7)=174(8).
【点评】掌握三种特殊算法的求解思想和方法是顺利解决问题的前提和必要条件.
某算法的程序框图如图所示,其中输入的变量x在1,2,3,…,24这24个整数中等可能随机产生.
(1)分别求出按程序框图正确编程运行时输出y的值为i的概率Pi(i=1,2,3);
(2)甲、乙两同学依据自己对程序框图的理解,各自编写程序重复运行n次后,统计记录了输出y的值为i(i=1,2,3)的频数.以下是甲、乙所作频数统计表的部分数据.
甲的频数统计表(部分)
运行次数n
输出y的值为1的频数
输出y的值为2的频数
输出y的值为3的频数
30
14
6
10
…
…
…
…
2 100
1 027
376
697
乙的频数统计表(部分)
运行次数n
输出y的值为1的频数
输出y的值为2的频数
输出y的值为3的频数
30
12
11
7
…
…
…
…
2 100
1 051
696
353
当n=2 100时,根据表中的数据,分别写出甲、乙所编程序各自输出y的值为i(i=1,2,3)的频率(用分数表示),并判断两位同学中哪一位所编写程序符合算法要求的可能性较大;
(3)按程序框图正确编写的程序运行3次,求输出y的值为2的次数ξ的分布列及数学期望.
(2)当n=2 100时,甲、乙所编程序各自输出y的值为i(i=1,2,3)的频率如下:
输出y的值为1的频数
输出y的值为2的频数
输出y的值为3的频数
甲
乙
比较频率趋势与概率,可得乙同学所编程序符合算法要求的可能性较大.
(3)随机变量ξ可能的取值为0,1,2,3.
P(ξ=0)=C××=,
P(ξ=1)=C××=,
P(ξ=2)=C××=,
P(ξ=3)=C××=,
故ξ的分布列为
ξ
0
1
2
3
P
所以,Eξ=0×+1×+2×+3×=1.
即ξ的数学期望为1.
根据如图所示的程序框图,将输出的x,y的值依次分别记为x1,x2,x3,…,x …;y1,y2,y3,…,y ….
(1)分别求数列{x }和{y }的通项公式;
(2)令 =x y ,求数列{ }的前 项和T ,其中 ∈N*, ≤2 017.
(2)T =x1y1+x2y2+…+x y
=1×(3-1)+3×(32-1)+…+(2 -1)(3 -1)
=1×3+3×32+…+(2 -1)·3 -[1+3+…+(2 -1)].
令S =1×3+3×32+…+(2 -1)·3 ,①
则3S =1×32+3×33+…+(2 -1)·3 +1,②
①-②得
-2S =3+2·32+2·33+…+2·3 -(2 -1)·3 +1
=2(3+32+…+3 )-3-(2 -1)·3 +1
=2×-3-(2 -1)·3 +1
=3 +1-6-(2 -1)·3 +1
=2(1- )·3 +1-6,
∴S =( -1)·3 +1+3.
又∵1+3+…+(2 -1)== 2,
∴T =( -1)·3 +1+3- 2.
【点评】以程序框图或算法语句为题设条件常与统计问题、数列问题、函数问题综合,求解时关键是将程序框图或算法语句转化翻译.
四.方法总结
1.了解算法思想,理解算法含义的关键在于体现程序或步骤的明确性和有限性.
2.深刻理解算法的三种逻辑结构特征,需通过实际例子体会算法流程的全过程,认清所解决问题的实质.如解决分段函数的求值问题时,一般采用条件结构设计算法;如累加求和,累乘求积等问题,往往包含循环过程,非常适合计算机处理,这类问题很多程序框图都用循环结构进行设计,同时也要注意三种基本结构的共同特点.
3.特别提醒的是,程序框图主要包括三个部分:(1)弄清相应操作框的内容;(2)带箭头的流程线及判断框的条件;(3)框内外必要的文字说明和算法功能.读懂流程图要从这三方面研究,流程线反映了流程执行的先后顺序,主要看箭头方向,框内外文字说明了操作内容以及流向.
4.(1)辗转相除法与更相减损术是求两个正整数的最大公约数的两种方法,关键是掌握这两种算法的操作步骤,计算时应认真、细心,确保中间结果的准确性,因为下一次计算要用到上一次计算的结果.
(2)利用“除 取余法”将十进制数化为 进制数时,要把各步所得余数从下到上排,切莫把顺序弄错.
(3)利用秦九韶算法计算多项式的值的关键是正确地将多项式改写,然后由内向外逐次计算.由于本次计算用到上一次计算的结果,同样应认真、细致地计算每一步,确保每一步结果的准确性.