2022年高中数学典型例题解析第十三章算法初步 .pdf

《2022年高中数学典型例题解析第十三章算法初步 .pdf》由会员分享，可在线阅读，更多相关《2022年高中数学典型例题解析第十三章算法初步 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习必备欢迎下载第十三章算法初步13.1 流程图一、知识导学1.流程图：是由一些图框和带箭头的流线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，带箭头的流线表示操作的先后次序.2算法的三种基本的逻辑结构：顺序结构、条件结构、循环结构.3根据对条件的不同处理，循环结构又分为两种：直到型 (until 型)循环：在执行了一次循环体之后，对控制循环条件进行判断，当条件不满足时执行循环体.满足则停止 .如图 13-1-3， 先执行 A 框， 再判断给定的条件p是否为“假”，若p为“假”，则再执行A，如此反复，直到p为“真”为止 . 当型（ while 型）循环：在每次执行循环体

2、前对控制循环条件进行判断，当条件满足时执行循环体，不满足则停止.如图 13-1-4，当给定的条件p成立（“真” ）时，反复执行A 框操作，直到条件p为“假”时才停止循环.图 13-1-1 图 13-1-2二、疑难知识导析1.“算法“没有一个精确化的定义，教科书只对它作了描述性说明，算法具有如下特点：（1）有限性：一个算法的步骤是有限的，必须在有限操作之后停止，不能是无限的.（2）确定性：算法的每一步骤和次序应当是确定的.（3）有效性：算法的每一步骤都必须是有效的.2. 画流程图时必须注意以下几方面：（1）使用标准的图形符号.（2）流程图一般按从上到下、从左到右的方向画.（3）除判断框外，大多数

3、流程图符号只有一个进入点和一个退出点.判断框具有超过一个退出点的唯一符号.（4）判断框分两大类，一类判断框 “是” 与“否” 两分支的判断， 而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果.（5）在图形符号内描述的语言要非常简练清楚.3. 算法三种逻辑结构的几点说明：（1）顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的 .在流程图中的体现就是用流程线自上而下地连接起来，按顺序执行算法步骤. （ 2）一个条件结构可以有多个判断框.（3）循环结构要在某个条件下终止循环，这就需要条件结构来判断.在循环结构中都有一个计数变量和累加变量.计数变量用于记录循环次

4、数，累加变量用语输出结果，计数变量和累加变量一般是同步执行的，累加一次，计数一次.精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 17 页学习必备欢迎下载三、经典例题导讲 例 1已知三个单元存放了变量x，y，z的值， 试给出一个算法，顺次交换x，y，z的值（即y取x的值，z取y的值，x取z的值） ，并画出流程图.错解 ：第一步xy第二步yz第三步zx流程图为图 13-1-3 错因 ：未理解赋值的含义，由上面的算法使得y，z均取x的值 .举一形象的例子：有蓝和黑两个墨水瓶，但现在却把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将

5、其互换，请你设计算法解决这一问题.对于这种非数值性问题的算法设计问题，应当首先建立过程模型，根据过程设计步骤完成算法. 我们不可将两个墨水瓶中的墨水直接交换，因为两个墨水瓶都装有墨水，不可能进行直接交换. 正确的解法应为：S1 取一只空的墨水瓶，设其为白色；S2 将黑墨水瓶中的蓝墨水装入白瓶中； S3 将蓝墨水瓶中的黑墨水装入黑瓶中； S4 将白瓶中的蓝墨水装入蓝瓶中； S5 交换结束 .正解 ：第一步zp先将z的值赋给变量p，这时存放z的单元可作它用第二步yz再将y的值赋给z，这时存放y的单元可作它用第三步xy同样将x的值赋给y，这时存放x的单元可作它用第四步px最后将p的值赋给y，三个变量

6、x，y，z的值就完成了交换 流程图为图 13-1-4点评 ：在计算机中，每个变量都分配了一个存储单元，为了达到交换的目的，需要一个单元精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 17 页学习必备欢迎下载存放中间变量p. 例 2 已知三个数a，b，c. 试给出寻找这三个数中最大的一个算法，画出该算法的流程图.解：流程图为图 13-1-5点评 ：条件结构可含有多个判断框，判断框内的内容要简明、准确、清晰. 此题也可将第一个判断框中的两个条件分别用两个判断框表示，两两比较也很清晰. 若改为求100 个数中的最大数或最小数的问题则选择此法较

7、繁琐，可采用假设第一数最大（最小） 将第一个数与后面的数依依比较，若后面的数较大（较小），则进行交换，最终第一个数即为最大（最小）值.点评 ：求和时根据过程的类同性可用循环结构来实现，而不用顺序结构. 例 3 画出求222222100994321的值的算法流程图.解：这是一个求和问题，可采用循环结构实现设计算法，但要注意奇数项为正号，偶数项为负号 .思路一：采用 -1 的奇偶次方（利用循环变量）来解决正负符号问题；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 17 页学习必备欢迎下载图 13-1-6 图 13-1-7思路二：采用选择结

8、构分奇偶项求和；图 13-1-8思路三：可先将222222100994321化简成1991173，转化为一个等差数列求和问题，易利用循环结构求出结果. 例 4设计一算法，求使20063212222n成立的最小正整数n的值 .精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 17 页学习必备欢迎下载解： 流程图为图 13-1-9点评 ：这道题仍然是考察求和的循环结构的运用问题，需要强调的是求和语句的表示方法 .若将题改为求使20063212222n成立的最大正整数n的值时， 则需注意的是输出的值 . 例 5 任意给定一个大于1 的整数 n，

9、试设计一个程序或步骤对n 是否为质数做出判断.解：算法为：S1 判断 n 是否等于2，若 n=2，则 n 是质数；若n2，则执行S2S2 依次从 2n-1 检验是不是的因数，即整除 n 的数，若有这样的数， 则 n 不是质数；若没有这样的数，则n 是质数 .点评 ：要验证是否为质数首先必须对质数的本质含义作深入分析：（1）质数是只能被1 和自身整除的大于1的整数 .（2）要判断一个大于1 的整数 n 是否为质数， 只要根据定义， 用比这个整数小的数去除 n. 如果它只能被1 和本身整除，而不能被其它整数整除，则这个数便是质数.图 13-1-10 精选学习资料 - - - - - - - - -

10、 名师归纳总结 - - - - - - -第 5 页，共 17 页学习必备欢迎下载 例 6 设计一个求无理数2的近似值的算法.分析 ：无理数2的近似值可看作是方程022x的正的近似根，因此该算法的实质是设计一个求方程022x的近似根的算法.其基本方法即运用二分法求解方程的近似解.解：设所求近似根与精确解的差的绝对值不超过0.005, 算法 :S1 令2)(2xxf. 因为0)2(,0)1(ff, 所以设2, 121xxS2 令2)(21xxm,判 断)(mf是 否 为0,若 是 ,则m为 所 求 ;若 否 ,则 继 续 判 断)()(1mfxf大于 0 还是小于0.S3 若)()(1mfxf0

11、,则mx1;否则 ,令mx2.S4 判断005.021xx是否成立，若是，则21,xx之间的任意值均为满足条件的近似根；若否，则返回第二步.点评 ：二分法求方程近似解的算法是一个重要的算法案例，将在第三节中详细阐述.四、典型习题导练1已知两个单元分别存放了变量A和B的值， 则可以实现变量BA,交换的算法是 （）.AS1 ABBS1 ACCS1 ACDS1 ACS2 BAS2 CBS2 BAS2 BDS3 BCS3 CB下面流程图中的错误是（）图 13-1-11Ai没有赋值B循环结构有错CS 的计算不对D判断条件不成立3.将“打电话”的过程描述成一个算法，这个算法可表示为，由此说明算法具有下列特

12、性. 4. 在表示求直线0cbyax（a，b为常数，且a，b不同时为0）的斜率的算法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 17 页学习必备欢迎下载的流程图中，判断框中应填入的内容是5. 3 个正实数，设计一个算法，判断分别以这3 个数为三边边长的三角形是否存在，画出这个算法的流程图. 6. 一队士兵来到一条有鳄鱼的深河的左岸.只有一条小船和两个小孩，这条船只能承载两个小孩或一个士兵.试设计一个算法，将这队士兵渡到对岸，并将这个算法用流程图表示.13.2 基本算法语句一、知识导学1 赋值语句用符号“”表示，“yx”表示将y的值赋

13、给x，其中x是一个变量，y是一个与x同类型的变量或表达式. 2 条件语句主要有两种形式：“行 If 语句”和“块If 语句” . “行 If 语句”的一般形式为：If A Then B Else C . 一个行 If 语句必须在一行中写完，其中方括号中的Else 部分可以缺省. “块 If 语句”的一般格式为: If A Then B Else C End if Then 部分和Else 部分是可选的，但块If 语句的出口“ End if ”不能省 . 3 循环语句主要有两种类型：For 语句和 While 语句 . 当循环的次数已经确定，可用“For”语句表示 .“For”语句的一般形式为：

14、For I from “初值”to step“步长”End for 上面“ For”和“ End for”之间缩进的步骤称为循环体. 当循环次数不能确定是，可用“While”语句来实现循环.“While ”语句的一般形式为：While A End while 其中 A 表示判断执行循环的条件. 上面“ While ”和“ End While ”之间缩进的步骤称为循环体. 二、疑难知识导析1.有的条件语句可以不带“Else”分支，即满足条件时执行B，否则不执行任何操作.条件语句也可以进行嵌套，在进行条件语句的嵌套时，书写要有层次.例如：If A Then B Else if C Then D E

15、lse E End if 2.“For”语句是在执行过程中先操作，后判断.而“ While ”语句的特点是“前测试”，即先判断，后执行 .若初始条件不成立，则一次也不执行循环体中的内容.任何一种需要重复处理的问题都可以用这种前测试循环来实现. 三、经典例题导讲精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 17 页学习必备欢迎下载例 1 下列程序的运行结果是. 9X8YIf X5 Then 7YYIf X4 Then 6YYIf X3 Then 6YYPrint Y错解 ：8+7=15 错因 ： 误认为在一个程序中只执行一个条件语句，与

16、在一个条件语句中只选择其中一个分支相混淆 .If A Then B Else C 若满足条件A 则执行 B，否则是执行C，B 和 C 是这个条件语句的分支，而这个程序省略了Else 部分 . 正解 ：这里是有三个条件语句，各个条件语句是独立的，三个条件均成立，所以按顺序依次执行，结果为8+7+6+6=27. 例 2 下面的伪代码的效果是0iWhile i10 2iiEnd While End 错解 ：执行 10 次循环错因 ：将 For 语句和 While 语句混淆 . For 语句中有步长使循环变量不断变化，而While 语句则无 . 正解： 无限循环下去，这是因为这里i始终为 0，总能满足

17、条件“10i”，故是一个“死循环” . 点评 ：“死循环”是设计循环结构的大忌，此题可改变i的初始值或每一次循环i都增加一个值 . 例 3下面的程序运行时输出的结果是（）1IWhile 5I0S1IIIISSEnd while Print S End 错解 ： 第一次循环时， I 被赋予 2， S被赋予 4； 第二次循环时， I 被赋予 3， S被赋予 4+23=13；第三次循环时，I 被赋予4，S 被赋予13+24=29；第四次循环时，I 被赋予5，S 被赋予545292. 由于此时5I，故循环终止，输出S为 54. 正解： 由于0S在循环内，每经过一次循环后S 都被赋值0，因此，只要求满足

18、条件的最后一次循环S 的值，即当4I时，16440S.精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 17 页学习必备欢迎下载例 4用语句描述求使10007531n成立的最大正整数n的算法过程 .解：1n1TWhile 1000T2nnnTTEnd while Print 2n点评 ： 此题易错的是输出值，根据 While 循环语句的特征当1000T时跳出循环体， 此时n的值是1000T时的最小的整数，则使1000T的最大整数应为n的前一个奇数即2n. 例 5 已知当100100 x时，1xy，当100 x时，4y，当100 x时，4x

19、y，设计一算法求y的值 . 解： Read x If 100100 x then 1xyElse if 100 x Then 4xyElse 4yEnd if End 点评 ：嵌套 If语句可用如上的紧凑形式书写，要注意的是如不是采取紧凑形式，则需注意一个块 If 语句对应一个End If ，不可省略或缺少. 例 6 设计一个算法，使得输入一个正整数n，输出 1！+2！+3！+n！的值 . 写出伪代码. 解：思路一：利用单循环，循环体中必须包括一个求各项阶乘的语句以及一个求和语句. Read n 01ST For I from 1 to n TSSITT End For Print S 思路二

20、：运用内外双重循环，但尤其注意的是每一次外循环T 的值都要从1 开始 . Read n 0S精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 17 页学习必备欢迎下载For I from 1 to n 1T For J from 1 to I JTTEnd For TSS End For Print S 四 、典型习题导练1 下列的循环语句循环的次数为（）For I from 1 to 7 For J from 1 to 9 Pint I+J End for End for End A.7 次 B.9次 C.63次 D.16次2运行下面的

21、程序后输出的结果是，若将程序中的A语句与 B语句的位置互换，再次执行程序后输出的结果为 . 1x0yWhile 3xxyyA 语句1xxB 语句End While Print x,y End 3. 伪代码描述的求T的代数式是 ,求S的代数式是 . Read n 1T0SFor I from 1 to n ITTISSEnd for Print T,S 4. 运行下面程序后输出的结果为For I from 10 to 1 step -2 Print I End for End 5. 将 100 名学生的一门功课的成绩依次输入并计算输出平均成绩. 13 3 算法案例精选学习资料 - - - - -

22、 - - - - 名师归纳总结 - - - - - - -第 10 页，共 17 页学习必备欢迎下载一、知识导学1算法设计思想：（1） “韩信点兵孙子问题”对正整数m 从 2 开始逐一检验条件，若三个条件中有任何一个不满足，则m 递增 1，一直到m 同时满足三个条件为止(循环过程用Goto 语句实现 ) （2）用辗转相除法找出ba.的最大公约数的步骤是：计算出ba的余数r，若0r，则b为ba,的最大公约数；若0r，则把前面的除数b作为新的被除数，继续运算，直到余数为 0，此时的除数即为正整数ba,的最大公约数 . 2. 更相减损术的步骤： （1）任意给出两个正数，判断它们是否都是偶数. 若是，

23、用2 约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数 . 继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数 . （3）二分法求方程0)(xf在区间ba,内的一个近似解*x的解题步骤可表示为S1 取ba, 的中点bax210，将区间一分为二；S2 若00 xf，则0 x就是方程的根；否则判别根x在0 x的左侧还是右侧：若00 xfaf，bxx,*0，以0 x代替a；若00 xfaf，则0,*xax，以0 x代替b；S3 若cba，计算终止，此时0 xx，否则转S1. 二、疑难知识导析1)int( x表示不超过x的整数部

24、分，如0)32.0int(,5)86.5int(，但当x是负数时极易出错，如1)14.1int(就是错误的，应为-2. 2),mod(ba表示a除以b所得的余数，也可用amod b表示 .3辗转相除法与更相减损术求最大公约数的联系与区别：（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显 . （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0 则得到， 而更相减损术则以减数与差相等而得到. 4用二分法求方程近似解，必须先判断方程在给定区间ba, 上是否有解 , 即xf连

25、续且满足0bfaf. 并在二分搜索过程中需对中点处函数值的符号进行多次循环判定，故需要选择结构、循环结构，即可用Goto 语句和条件语句实现算法. 三、经典例题导讲精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 17 页学习必备欢迎下载例 1)5int(，)05.0int(，)9,67mod(，45 mod7= . A16，-1， 4，3 B.15，0，4，3 C.15,-1,3,4 D.15,-1,4,3 错解 ：根据)int( x表示不超过x的整数部分 , ),mod(ba表示a除以b所得的余数 ,选择 B.错因 : 对)int(

26、 x表示的含义理解不透彻,将不超过 -0.05 的整数错认为是0, 将负数的大小比较与正数的大小比较相混淆. 正解 ：不超过 -0.05的整数是 -1, 所以答案为D. 例 2 所谓同构数是指此数的平方数的最后几位与该数相等.请设计一算法判断一个大于0且小于 1000 的整数是否为同构数.错解 ： 算法思想：求出输入数的平方，考虑其个位或最后两位或最后三位与输入数是否相等，若相等，则为同构数. Read x xxy If )10(yx or )100(yx or )1000(yx Then Print x End if End 错因：在表示个位或最后两位或最后三位出现错误，“/ ”仅表示除，

27、y/10,y/100,y/1000都仅仅表示商 . 正解 ：可用)1000,mod(),100,mod(),10,mod(yyy来表示个位，最后两位以及最后三位. Read x xxy If )10,mod(yx or )100,mod(yx or )1000,mod(yx Then Print x End if End 例 3孙子算经中的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”可以用下面的算法解决：先在纸上写上2，每次加3，加成 5 除余 3 的时候停下来，再在这个数上每次加15，到得出7 除 2 的时候，就是答数.试用流程图和伪代码表示这一

28、算法. 解：流程图为：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 17 页学习必备欢迎下载伪代码为：10 2m20 3mm30 If 35 ,mod m Then Goto 20 40 If 2)7,mod(m Then Print m Goto 80 50 End if60 15mm70 Goto 40 80 End 点评 ：这是孙子思想的体现，主要是依次满足三个整除条件. 例 4 分别用辗转相除法、更相减损法求192 与 81 的最大公约数.解：辗转相除法：S1 30281192S2 2123081S3 912130S4 32

29、921S5 0339故 3 是 192 与 81 的最大公约数 . 更相减损法：S1 11181192S2 3081111S3 513081S4 213051S5 92130S6 12921S7 3912S8 639精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 17 页学习必备欢迎下载S9 336故 3 是 192 与 81 的最大公约数. 点评 ：辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少 . 辗转相除法是当大数被小数整除时停止除法运算，此时的小数就是两者的最大公约数，更相减损术是当大数减去小

30、数的差等于小数时减法停止，较小的数就是最大公约数. 例 5 为了设计用区间二分法求方程0123xx在0 ，1 上的一个近似解（误差不超过 0.001 ）的算法 , 流程图的各个框图如下所示, 请重新排列各框图, 并用带箭头的流线和判断符号“ Y”、“ N”组成正确的算法流程图, 并写出其伪代码.( 其中ba,分别表示区间的左右端点 )图 13-3-2 流程图为图 13-3-3 伪代码为精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 17 页学习必备欢迎下载10 Read ba,20 2)(0bax30 1)(23aaaf40 1)(2

31、0300 xxxf50 If 0)(0 xf Then Goto 120 60 If 0)()(0 xfaf Then 70 0 xb100 End if 80 Else 90 0 xa100 End if 110 If 001.0ba Then Goto 20 120 Print 0 x130 End 点评 ： 二分法的基本思想在必修一中已渗透，这里运用算法将二分法求方程近似解的步骤更清晰的表述出来. 例 6 用秦九韶算法计算多项式654323567983512)(xxxxxxxf在4x时的值时，3v的值为.解： 根据秦九韶算法，此多项式可变形为1235879653xxxxxxxf按照从内到

32、外的顺序，依次计算一次多项式当4x时的值：40v75)4(31v346)7()4(2v577934)4(3v故当4x时多项式的值为57. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 17 页学习必备欢迎下载点评 ：秦九韶算法的关键是n 次多项式的变形. 把一个n次多项式0111)(axaxaxaxfnnnn改写成0121)()(axaxaxaxaxfnnn，求多项式的值，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值，这样把求n次多项式的值问题转化为求n个一次多项式的值的问题，这种方法成为秦九韶算法.这种算

33、法中有反复执行的步骤，因此，可考虑用循环结构实现.四、典型习题导练1以下短文摘自古代孙子算经 一书， 其引申出的 “大衍求一术” 称为 “中国剩余原理” ：“今有物不知其数， 三三数之剩二， 五五数之剩三， 七七数之剩二， 问物几何？” 答曰 （） . A二十一 B.二十二 C.二十三 D.二十四2用辗转相除法求52 与 39 的最大公约数的循环次数为（）. A1 次 B.2次 C.3次 D.5次3下面程序功能是统计随机产生的十个两位正整数中偶数和奇数的个数，并求出偶数与奇数各自的总和 . For I from 1 to 10 10)90int(Rndx Print x; If Then xs

34、snn22122 Else xss11 End If End for Print Print “奇数个数=”；1n，“偶数个数=”；2n4 若一个数的各因子之和正好等于该数本身，则该数成为完数. 请补充完整下列找出1100之间的所有完数的伪代码. For a from 2 to 100 1cFor b from 2 to If mod(a,b)=0 Then End if End For If Then Print a End if End For 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 17 页学习必备欢迎下载End 5设计求被9 除余 4，被 11 除余 3 的最小正整数的算法，画出流程图，写出伪代码.6利用辗转相除法或更相减损术求324,243,135 的最大公约数. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 17 页