算法题型与方法

《算法题型与方法》由会员分享，可在线阅读，更多相关《算法题型与方法（13页珍藏版）》请在装配图网上搜索。

1、算法题型与方法算法概念例1:下面对算法描述正确的一项是()A. 算法只能用自然语言來描述 E.算法只能用图形方式來表示C.同一问题可以有不同的算法 D.同一问题的算法不同，结果必然不同解：A, E显然错误，由算法的不唯一性知C正确，对于D,同一问题的算法不同，但 结果可以相同，D错，故选C例2：下列说法不牙硒的是()A.任何一个算法二定鸟有顺序结构E.任何一个算法都可能由顺序结构、条件结构、循环结构构成C.循环结构中一定包含条件结构D.条件结构中一定包含循环结构解：顺序结构、条件结构、循环结构按照顺序，后一种结构包含前一种结构，但反过来 不一定包含.所以条件结构中不一定包含循环结构，故选D例3

2、：下列叙述中，不正确的是( )A.解决一个问题的算法不是唯一的E.算法必须能够解决一类问题D.个算法可以分为11(11 EN)步,1】可以无限地取值C.在计算机上算法能够执行 解：算法由各步骤构成，但步骤是有限的.故选D读取算法功能例1：阅读如图所示的程序框图，若输入的k=10,则该算法的功能是( 计算数列211-1的前10项和计算数列2n-l的前10项和由程序框图可知：S = 0, i = l;A.C.解:E.计算数列2小的前9项和D.计算数列2n-l的前9项和S=1 +2x0 = 1 =2, i =2； S= 1 +2x1 =,观察得到对应数列的1 + 2 = 2 + 21, i = 3;

3、 S=1 +2x3 = 2+21 +22, i = 4;通项公式为an = 2n_1.k = 10时，i10时输出，说明是求前10项的和.例2：.如果执行如图所示的程序框图，输入正整数N(N2)和实数ai，a2,. ) . 的和aN,输出 A, B,贝lj（ A.A+B丿、）a】，a?, _ A+B “E.79 a!, a2,，呛的算术平均数C. A和B分别是ai，a2,D. A和E分别是心，a2,解：结合题中程序框图，由当xA时A= x可知A应为ai，呛中最大的数和最小的数 ，a”中最小的数和最大的数a2 . aN中最大的数；由当xB时B = x可知E应为a】，a?,aN中最小的数.故选C.

4、l/n）/输出S/TO/ 输入 a,b，k/开始计算算法结果例1: （2014新课标全国1卷）执行右面的程序框图，若输入 的a, b, k分别为1, 2, 3,则输出的M=（）207ATBI1615CTDT33解析 第一次循环：M =，a =2, b = J, n = 2;第二次循环：M = |, a=|, b = |, n = 3;第三次循环：M = y, a=|, b = y, n = 4,则输出M = y,选D.例2： （2014-杭州质量检测）某程序框图如图所示，若该程序运行后输出的结果不大于37,则输入的整数i的最大值为（）A. 3 B. 4 C. 5 D. 6解：经过第一次循环得到

5、S = 2, n = l；经过第二次循环得到S = 5, n = 2;经过第三次循环得到S=10, n = 3;经过第四次循环得到S=19, n = 4；经过第五次循环得到S = 36, n = 5；经过第六次循环得到S = 69, n = 6, V输出的结果不大于37,=的最大值为5,故选C.例3： （2013-全国课标1）执行如图的程序框图，如果输入的tE-l, 3,则输出的s的取值范围为（） A.3, 4B.-5, 2C.4, 3D.-2, 5，- ltl,解：由框图知s# 当-时，-3Ss3；L4t - t, lt3,当lt3时，3s4.综上，- 3Sj B. s C s D. s9解

6、析程序框图的执行过程如下：s = 1, k = 9; S = p, k= 8; s =k=7; s = x = , k = 6,循环结束.故可填入的条 7件为S花.故选C.开始例2： （2015-湖北七市（州）联考）某程序框图如图所示，判断框内为畑？ ”，n 为正整数，若输出的S=26,则判断框内的n=S=2S+k/输出s/解析 依题意，执行题中的程序框图，进行第一次循环时，k = l+l=2, S = 2x1 +2=4；进行第二次循环时，k=2 + l =3, S = 2x4 + 3 = 11；进行第三次 循环时，k = 3 + 1 =4, S = 2xll +4 = 26,因此当输出的S

7、= 26时，判断框内 的 n = 4.程序代码例1： .（2014陕西模拟）下面程序运行后,输出的值是（）i=0DOi=i+lLOOP UNTIL i*i = 2000i=i-lPRINT iENDA.42B.43C.44D.454522000, .I解：程序的功能是利用循环计算i22000（iG）的最大i值，V4422000, 输出的i为44.故选C.例2：若运行如图所示的弹序,则输出S的值是（）i = lS=0WHILE i=6B.i=7C.i=7 D.i = 7”故填B.与其他知识综合例1： （2014-南昌模拟）如果执行如图所示的程序框图，那么输 出的值为.解析 在数列an中，an=

8、cos y, ai = a2 = a3 = - 1, a4= -扌，a5 = a6 = 1,该数列是以6为周期的数列，且其前6项 和等于0.注意到2 014 = 6x335 +4,因此其前2 014项和等于335x01 始)1 113数列仏的前2 014项和，即等于-寸.例2： .（2013重庆）执行如图所示的程序框图，如果输出s=3,那 么判断框内应填入的条件是（）A.k6C.k8B.k7D.k 首先改写成如下形式：f (x) = (. (anX+an-i) x+an-2)x+.+ai)x+a。,再计 算最内层括号内一次多项式的值，即vi=a+an-i；然后由内向外逐层计算一多项式的值，即

9、V2=Vix+an-2，V3=V2x+an-3, . i=i-ix+a0.例2：下列各数85,9八210、1000、中最大的数是()A. 85(9)E 210(6) C. 1000,4) D. 111111 2)解：85 =lx43=64；111111=1x25+1x244-1x23+1x23+1x21+1x20=32+1 6+8+4+2+1=63 由上计算知最大的数是 210 ，故选B例3：用秦九韶算法计算多项式f (x) =3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时的值时， 至多需要做乘法和加法的次数分别是和解：Vf (x) =3x6+4x5+5x4+6x3+7x2+8

10、x+1= (3x+4) x+5x+6x+7x+8x+l需要做6次加法运算，6次乘法运算，把所给的多项式写成关于x的一次函数的形式，依次写出，得到最后结果，从里到外进 行运算，结果有6次乘法运算，有6次加法运算，本题也可以不分解，直接从最高次项的次 数直接得到结果.习题荟萃1、读程序甲：INPUT i = lS=0WHILE i 1000S = S + ii =i +1WENDPRINT SEND对甲乙两程序和输出结果判断正确的是(乙：INPUT i = 1000S=0DOS = S + ii =i 1LOOP UNTIL i 1PRINT SEND)BA.程序不同，结果不同B. 程序不同，结果

11、相同C. 程序相同，结果不同D. 程序相同，结果相同2、INPUT ni = lWHILE i 11IF n/i=int (n/i ) THENS=ii = i + lEND IFWENDPRINTSEND上述程序输出的是()DA. 1到n的和存吟的和C. 1n的所有质数D. I】的所有约数（注int （x）为不超过x的整数部分）3. （2014-东北三省四市联考）如图所示的程序框图，该算法的功能是（A.计算(1+2) + (2+21) + (3+2?) + .+(11 + 1+2“)的值E. 计算(1+21) + (2+22) + (3+23)+.+(11+211)的值C. 计算(1+2+3

12、 + .+11)4-(2+21+22 + .+211_1)的值D. 计算1+2+3 + .+(111) + (2+21+2? + .+2。的值解析 初始值k=l, S = 0,第1次进入循环体时，S=1 +2, k = 2;当第 2次进入循环体时，S=1 +2 + 2 + 21, k = 3,；给定正整数n,当k=n时，最后一次进入循环体,则有S= 1+2+2+21 + .+n + 2n_1, k = n + 1,终止循环体，输出 S= (1+2+3 + .+n) + (2+2】+2? + .+21),故选c.4、（2015-天津十二区县重点中学联考）执行如图所示的程序框图，若输 出的结果是4

13、,则判断框内m的取值范围是（）A. （2, 6B. （6, 12C（12, 20D. （2, 20）解析 要输出的结果是4,则该程序框图需要运行3次，即第2次的运行 结果S = 6满足判断框内的条件，所以6 10, +击.故选B（2013-山东）执行如图所示的程序框图，若输入的E的值为0.25, 则输出的I】的值为解：第 次循环得F=3, F（）=2, n = 2；第二次彳盾环得F=5, F = 此时 = | = 0.2N?是开始J7、输入 （0Fo=l. F=2.F产F+F】H=W+1/ 输附 /A. -12C.|D. 4开始输入x /若输出k=2,则输入x的取值范围k=0A. 19x200

14、E. x19|x=10x+I0|C- 19x200解析 根据程序框图，程序执行的步骤为S = 4,=19； S= -1, i =29; S = |, i = 39;3S = p i =49； S = 4, i=59； S= -1, i = 6 Q = 15, n = 3,此时P0Q不成立，输出n = 3,10、按如图所示的算法框图运算,/输入X如如）/10x+102 010,解得19xI?n= 1,5=0n=n+l结束715c 正严忆解析依题意得，数列的前2项和小于p、前 3项和不小于p.又数列务的前2、3项和分别等于扌+扌3111737兮、扌+扌+討缶因此P的取值范围是寸PS,选D.13、如

15、果执行如图的程序框图，那么输出的值是（）A. 2014 E 一1D2CiW* /输入成绩兀严庐2017M=0,N=0,i=lM二 M+lN二 7V+1i=i+/输如/1 1 1 1k = 02014S = - = -1, k=l2014S = -k = 2S = =2,1-21 U 1U丄1_2k = 3,故S的值依次循环取值-1, j, 2,周期为3,因为2014 = 671x3 + 1,故最后输出结果 为 S= -1.14、(2012-陕西文，5)下图是计算某年级500名学生期末考试(满分为100分)及格率q的程 序框图，则图中空白框内应填入()NMNMA. q=M E q= c.D解析本

16、题考查了循环结构的程序框图在实际问题中的应用.由框图知M为及格人M数，N为不及格人数，所以及格率q =乔.15、把5进制的数412d)化为7进制是.解：412(5)=2x5+1x51+4x52=2+5+4x25=107V107=2x74-1x71+2x72.把5进制的数412化为7进制是212(716、用秦九韶算法在计算f (x) =2x4+3x3 - 2x2+4x - 6时，要用到的乘法和加法的次数分别为 ( )A. 4, 3E. 6, 4C. 4, 4D 3, 4解：Vf (x) =2x4+3x3 - 2x2+4x - 6= (2x+3) x - 2) x+4) x - 6,用到的乘法的次数为4次，用到的加法的次数为4次17、用秦九韶算法求多项式f (x) =x+2x3+x2-3x-1,当x=2时的值，则v3=()A. 4B 9C. 15 D. 29解：由秦九韶算法的规则 f (x) =x4+2x3+x2 - 3x - 1=(x+2) x+1) x-3) x-1,/.V3= (x+2) x+1) x - 3乂 x=2,可得 V3= (2+2) 2+1) 2-3=15 故选 C.u/u