算法设计
【例1】 已知平面直角坐标系中两点A(-1,0),B(3,2),写出求线段AB的垂直平分线方程的一个算法.
思路点拨:先由中点坐标公式求出线段AB的中点坐标,再由斜率公式求出直线AB的斜率,然后利用两直线垂直,斜率乘积等于-1,得到线段AB垂直平分线的斜率,最后由点斜式得到线段AB的垂直平分线方程.把这一解决问题的过程划分为若干明确的步骤并用简练的语言表述出来,就是一个算法.
[解] 算法如下:
S1 计算x0←=1,y0←=1,得AB的中点N(1,1);
S2 计算k1←=,得AB斜率;
S3 计算k←-=-2,得AB垂直平分线的斜率;
S4 由点斜式得直线AB的垂直平分线的方程,并输出.
1.算法设计与一般意义上的问题解决不同,它是对一类问题、一般解法的抽象与概括.算法设计既要借助一般问题的解决方法,又要包含这类问题的所有可能情形,它往往是把问题的解决划分为若干个可执行的步骤,有时甚至需要重复多次某些步骤,但最终都必须在有限个步骤之内完成.
2.对于给定的问题,设计其算法时应注意:
(1)与解决该问题的一般方法相联系,从中提炼并概括出算法步骤;
(2)将解决问题的过程划分为若干步骤;
(3)引入有关的参数或变量对算法步骤加以表述;
(4)用简练的语言将各个步骤表述出来.
1.已知圆的方程(x-2)2+(y+3)2=25和点P(-1,2),写出求过点P且与圆相切的直线AB的方程的一个算法.
思路点拨:把求圆的切线的解题过程划分为若干个明确的步骤表述出来即可.
[解] 算法步骤如下:
第一步 用点斜式写出直线AB的方程y-2=k(x+1);
第二步 将直线的方程化为一般方程kx-y+k+2=0;
第三步 计算点(2,-3)到直线AB的距离
d=;
第四步 解方程5=,得k=0或k=;
第五步 将k的值代入方程kx-y+k+2=0;
第六步 将第五步的运算结果化简,即得到直线AB的方程.
2.一位老爷爷带一只狼、一只羊和一筐青菜准备过河,但由于船小,过河时每次只能带一样东西,而老爷爷不在时,狼会把羊吃掉,羊也会把青菜吃掉.请写出解决老爷爷怎样过河才能把所带的东西全部运到对岸这一问题的算法.
思路点拨:在老爷爷运送东西过河的过程中,人离开岸边时必须保证岸边的每个东西相安无事,依据此原则可以确定安全的过河办法.
[解] 老爷爷过河的步骤如下:
S1 把羊带到对岸;
S2 回来接狼,把狼带到对岸后把羊带回来;
S3 把羊放在原地,把菜运到对岸;
S4 回来接羊.
流程图的应用
【例2】 (1)执行如图所示的流程图,若输入的t∈[-2,2],则输出的S属于________.
(2)执行如图所示的流程图,如果输入的a=4,b=6,那么输出的n的值为________.
(1)[-3,6] (2)4 [(1)当0≤t≤2时,S=t-3∈[-3,-1],当-2≤t<0时,2t2+1∈(1,9],t←2t2+1,即t∈(1,9],此时执行S=t-3,则S∈(-2,6],
综上,S∈[-3,6].
(2)运行流程图,第1次循环,a=2,b=4,a=6,s=6,n=1;第2次循环,a=-2,b=6,a=4,s=10,n=2;第3次循环,a=2,b=4,a=6,s=16,n=3;第4次循环,a=-2,b=6,a=4,s=20,n=4,结束循环,故输出的n=4.]
解答此类问题的关键是读懂流程图,理解流程图的功能.
流程图中的选择结构和循环结构一直是高考的热点,循环结构几乎是每年必考的内容,选择结构常用来设计分段函数求值;比较两个数的大小;对一组数进行排序筛选等问题.在解决此类问题时关键要弄清楚分类的条件.对于循环结构,应注意终止的条件,关键是看“是”与“否”后面对应的操作是什么.
提醒:循环结构中循环次数的控制非常关键,它直接影响着运算的结果,注意两个问题:一是运算次数;二是循环结构的形式,即是当型循环还是直到型循环.
3.执行如图所示的流程图,若输入n的值为3,则输出S的值为________.
1 [i=1,S=-1,1≥3不成立;
i=2,S=-1,2≥3不成立;
i=3,S=-1=1,此时3≥3成立,
结束循环,输出S的值为1.]
4.如图所示的流程图是为了求出满足3n-2n>1 000的最小偶数n,那么在和两个空白框中,可以分别填入________,________.
A≤1 000 n←n+2 [由流程图中A=3n-2n,故判断框中应填入A≤1 000,由于初始值n=0,要求满足A=3n-2n>1 000的最小偶数,故执行框中填入n←n+2.]
伪代码的应用
(1)如下所示的伪代码,当输入值x=4时,输出值y为________.
(2)根据下面的伪代码,可知输出的结果S是________.
(1)1 (2)13 [(1)因为输入值x=4,所以执行y←log2x-1,所以输出值y=log24-1=1.
(2)由伪代码知a=1,b=1,S=1+1=2,i初值为1,终值为4,步长为1,则有i=1时,a=1,b=2,S=1+2=3;i=2时,a=2,b=3,S=2+3=5;i=3时,a=3,b=5,S=3+5=8;i=4时,a=5,b=8,S=13,算法结束,输出S=13.]
由伪代码求值问题,通常先把伪代码算法转换成流程图算法直观易懂,步骤清晰.条件语句对应选择结构.循环语句对应循环结构.
循环结构的两种格式(当型循环结构和直到型循环结构中)判断框内的条件在解决同一问题时是不同的,它们恰好相反.在用循环语句编写程序时,常用到三种循环语句,一是For语句,二是While语句,三是Do语句.要特别注意计数变量的取值范围,避免出现多一次循环或少一次循环的错误.
5.某算法的伪代码如下,如果输出的y的值是4,那么输入的x的所有可能的值是________.
-,4 [本题的伪代码表示的算法是求分段函数y=的函数值.①当x<0时,由x-2=4,得x=-;②当x≥0时,由x2-3x=4,得x=4.]
6.根据下面的伪代码,可知输出的结果t是________.
24 [t=1×2×3×4=24.]
分类讨论思想
【例4】 批发部出售袜子,其批发数在100到500双之间,当批发数小于等于300双时,每双批发价为2.5元,当批发数超过300双时,每双批发价为2.2元.试画出流程图计算100~500双袜子的批发金额,并写出伪代码.
思路点拨:
[解] 流程图如图:
算法伪代码为:
1.在解答某些数学问题时,有时会有多种情况,需对各种情况加以分类,逐步求解,最后综合得出结论,这就是分类讨论思想.在具体问题的算法设计中,往往需要根据条件进行逻辑判断,并进行不同的处理,这实际上就运用了分类讨论的思想方法.
2.利用分类讨论思想,可以通过条件结构实现算法的选择.按条件进行分析、比较、判断,并根据不同的情况进行不同的处理.
3.当遇到实际问题时,首先建立数学模型将实际问题转化为数学问题,然后找出各个量及各个量之间的相互关系,选用合适的结构画出流程图,写出伪代码.
7.任给一个x值计算y=中的y值的算法的流程图如图所示,其中图框中的①②③分别为________、________、________.
x<0 x>0 y←3 [对照分段函数解析式完成填空.]
8.分析如下伪代码,并回答问题:
(1)伪代码解决的是什么问题?画出相应的流程图;
(2)根据伪代码回答:
①若输入的x值为1时,输出的y值为多少?
②若输出的y值为8时,输入的x值应为多少?
思路点拨:→→
[解] (1)本题伪代码解决的是求分段函数y=的函数值的问题.相应的流程图如图.
(2)①当x=1时,因为1<2,所以y=-2,即输出y的值为-2.
②当y=8时,x>2,由x2-2x=8,得x=4或x=-2(舍),所以输入x的值是4.
课件35张PPT。第1章 算法初步章末复习课算法设计 流程图的应用 伪代码的应用 分类讨论思想 Thank you for watching !章末综合测评(一) 算法初步
(满分:150分 时间:120分钟)
一、选择题(本大题共12小题,每小题5分,满分60分.在每小题给出的四个选项中,只有一项是符合题目要求的)
1.下列关于算法的描述中,正确的是( )
A.算法与求解一个问题的方法相同
B.算法只能解决一个问题,不能重复使用
C.算法要一步一步执行
D.有的算法在执行完以后,可能没有结果
C [算法与求解一个问题的方法既有区别又有联系,故A不对;算法能够重复使用,故B不对;每一个算法在执行完以后,必须有结果,故D不对.]
2.下列语句表达中,不是算法的是( )
A.从北京到巴黎可以直接乘飞机抵达
B.利用公式S=ah计算底为1、高为2的三角形的面积
C.x>2x+4
D.求过M(1,2),N(-3,-5)两点的直线的方程,可先求MN的斜率,再利用点斜式求得方程
C [根据算法的概念A、B、D都是算法.由于C仅是一个不等式,没有步骤和方法,故不是算法.]
3.语句①a←-a;②a>10;③输入a;④a+b←10;⑤a←a+b中可以用在处理框中的是( )
A.①② B.③④
C.②⑤ D.①⑤
D [处理框表示赋值或计算,x←y表示将y的值赋给x,y表示常量或与x同类的变量,故①⑤可以用在处理框中.]
4.下面的算法输出结果为( )
A.5 3 B.3 5
C.2 8 D.-2 8
B [执行第三步时,x=2;执行第四步时,y=5;执行第五步时,x=3.因此输出的结果为3,5.
提醒:在赋值语句中,变量的值始终等于最后一次赋给它的值,先前的值被替换.]
5.输入两个数, 输出其中较大的数,则能将语句补充完整的是( )
A.Print b B.a<b
C.a≤b D.Read b
A [输出a,b中较大的数,若a>b,则输出a,否则就输出b.]
6.如图是求函数y=x2-5x+3,当x∈{0,3,6,9,…,30}时的函数值的一个流程图,则填线处应填( )
A.x←3x B.x←x+1
C.x←x+2 D.x←x+3
D [由x∈{0,3,6,9,…,30}知每循环一次,x增加3,故填x←x+3.]
7.下面的伪代码给出了计算1×3×5×7×9×11×13的算法的一部分,则在横线上应该填入的语句是( )
A.S←S+i B.i←i+2
C.S←S×i D.i←S×i
C [这是一个求积的算法,当然用乘法,S←S×i.]
8.执行如图所示的流程图,若输入n=3,则输出的S的值为( )
A. B.
C. D.
B [当输入n=3时,输出
S=++
=
=×
=.]
9.执行下面的流程图,如果输入的x=0,y=1,n=1,则输出x,y的值分别为( )
A. 2 B. 2
C. 6 D. 6
C [执行流程图:当n=1时,x=0,y=1,
此时02+12≥36不成立;
当n=2时,x=,y=2,
此时2+22≥36不成立;
当n=3时,x=,y=6,
此时2+62≥36成立.
结束循环,输出x的值为,y的值为6.]
10.在对16和12求最大公约数时,整个操作如下:16-12=4,12-4=8,8-4=4.由此可以看出12和16的最大公约数是( )
A.4 B.12
C.16 D.8
A [根据更相减损术方法判断.]
11.执行如图所示的流程图,如果运行结果为5 040,那么判断框中应填入
( )
A.k<6 B.k<7
C.k>6 D.k>7
D [执行流程图,第一次循环,得S=2,k=3;
第二次循环,得S=6,k=4;
第三次循环,得S=24,k=5;
第四次循环,得S=120,k=6;
第五次循环,得S=720,k=7;
第六次循环,得S=5 040,k=8,
此时满足题意,退出循环,输出的S=5 040,
故判断框中应填入“k>7”.]
12.下列伪代码运行后输出的结果是( )
A.16 B.25
C.36 D.49
B [本题的算法功能是输出不小于20的最小完全平方数.]
二、填空题(本大题共4小题,每小题5分,共20分,把答案填在题中横线上)
13.下面伪代码运行后,输出的值是________.
44 [此伪代码为循环语句.
当i=45时,45×45=2 025>2 000.
所以输出i=45-1=44.]
14.执行如图所示的流程图,则输出x的值为________.
4 [执行流程图,x=1,k=1;
x=2,k=2;x=4,k=3;
x=16,k=4;x=4,k=5,
退出循环,此时x=4.]
15.下面是一个算法的伪代码.如果输出的y的值是20,则输入的x的值是________.
2或6 [本题的算法功能是求分段函数y=的值,根据y=20,分段计算即可求出相应的x的值.]
16.图中的流程图描述的算法称为欧几里得辗转相除法.若输入m=2 010,n=1 541,则输出m=________.
67 [当m=2 010,n=1 541时,m除以n的余数是469,此时m=1 541,n=469,m除以n的余数是134,此时m=469,n=134,m除以n的余数是67,此时m=134,n=67,m除以n的余数是0,此时m=67,n=0,退出程序,输出结果为67,故答案为67.]
三、解答题(本大题共6小题,共70分.解答应写出文字说明、证明过程或演算步骤)
17.(本小题满分10分)已知f(x)=x2-2x-3,求f(3),f(-5),f(5),并计算f(3)+f(-5)+f(5)的值,设计出解决该问题的一个算法,并画出流程图.
思路点拨:这是一个已知函数解析式求函数值的问题,用顺序结构即可,依次求值.
[解] 算法如下
S1 x←3;
S2 y1←x2-2x-3;
S3 x←-5;
S4 y2←x2-2x-3;
S5 x←5;
S6 y3←x2-2x-3;
S7 y←y1+y2+y3;
S8 输出y1,y2,y3,y的值.
该算法对应的流程图如图所示:
18.(本小题满分12分)根据如图所示的流程图,写出其算法的伪代码.
思路点拨:由所学知识可知,此流程图表示的是计算2+4+6+…+200的一个算法,由于在算法的流程图中出现了循环结构,故用伪代码表示该算法时需用循环语句.
[解] 伪代码为:
19.(本小题满分12分)已知伪代码如下:
分析该伪代码的算法功能,并画出其流程图.
思路点拨:读懂每一个算法语句,明确“Until”循环语句的算法功能,也可先画出流程图,再判断算法功能.
[解] 该伪代码的算法功能是找到并输出1至100(包括100)的正整数中的所有偶数.流程图如图所示.
20.(本小题满分12分)给出30个数:1,2,4,7,….其规律是:第1个数是1,第2个数比第1个数大1,第3个数比第2个数大2,第4个数比第3个数大3,以此类推.要计算这30个数的和,现已给出了该问题算法的流程图,如图所示.
(1)该算法使用了什么类型的循环结构?
(2)图中①处和②处应分别填上什么语句?
(3)根据流程图写出算法的伪代码.
思路点拨:该算法使用了当型循环结构,因为要求30个数的和,故循环体应执行30次,其中i是计数变量,因此判断框内的条件就是限制计数变量i的,故应为i≤30.算法中的变量p实质表示参与求和的各个数,由于它也是变化的,且满足第i个数比其前面一个数大i-1,第(i+1)个数比其前面一个数大i,故应用p=p+i.
[解] (1)当型循环结构.
(2)①处应填i≤30;②处应填p←p+i.
(3)程序伪代码如下:
21.(本小题满分12分)已知如图所示的流程图(未完成),设当箭头a指向①时,输出的结果为S=m,当箭头a指向②时,输出的结果为S=n,求m+n的值.
思路点拨:当箭头a指向①时,在每次循环中,累加变量S的值被赋为0,即上一次循环后S的值被0替换;当箭头a指向②时,累加变量S的值被不断累积.
[解] 当箭头a指出①时,输出S和i的结果如下:
S 0+1 0+2 0+3 0+4 0+5
i 2 3 4 5 6
∴S=m=5.
当箭头a指向②时,输出S和i的结果如下:
S 0+1 0+1+2 0+1+2+3 0+1+2+3+4
i 2 3 4 5
0+1+2+3+4+5
6
∴S=n=1+2+3+4+5=15.
于是m+n=20.
22.(本小题满分12分)某商场为迎接10周年店庆举办促销活动,活动规定,购物金额在100~300元的优惠货款的5%,超过300元的,超过部分优惠8%,原优惠条件仍然有效,画出顾客的购物金额与应付金额之间的流程图,要求输入购物金额能够输出应付货款,并写出伪代码.
思路点拨:实际付款金额y与购物金额x的函数关系式为y=根据此条件画流程图,写伪代码.
[解] 流程图:
伪代码如下: