《2022年高中数学必修3-算法初步精讲 .pdf》由会员分享，可在线阅读，更多相关《2022年高中数学必修3-算法初步精讲 .pdf（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、高中数学必修 3- 算法初步精讲 13.1 流程图一、 知识导学1. 流程图：是由一些图框和带箭头的流线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，带箭头的流线表示操作的先后次序. 2算法的三种基本的逻辑结构：顺序结构、条件结构、循环结构. 3根据对条件的不同处理，循环结构又分为两种：直到型 (until 型)循环： 在执行了一次循环体之后， 对控制循环条件进行判断，当条件不满足时执行循环体.满足则停止 .如图 13-1-3 ，先执行 A 框，再判断给定的条件 p 是否为“假” ， 假设 p 为 “假” ，则再执行 A， 如此反复，直到 p 为“真”为止. 当型whi
2、le 型循环：在每次执行循环体前对控制循环条件进行判断，当条件满足时执行循环体， 不满足则停止 .如图 13-1-4 ， 当给定的条件 p 成立 “真” 时，反复执行 A 框操作，直到条件p 为“假”时才停止循环 . 图 13-1-1 图 13-1-2 二、疑难知识1.“算法“没有一个精确化的定义，教科书只对它作了描述性说明，算法具有如下特点：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 26 页1有限性：一个算法的步骤是有限的，必须在有限操作之后停止，不能是无限的. 2确定性：算法的每一步骤和次序应当是确定的. 3有效性：算法的每一
3、步骤都必须是有效的. 2. 画流程图时必须注意以下几方面：1使用标准的图形符号 . 2流程图一般按从上到下、从左到右的方向画. 3除判断框外，大多数流程图符号只有一个进入点和一个退出点.判断框具有超过一个退出点的唯一符号. 4判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果. 5在图形符号内描述的语言要非常简练清楚. 3. 算法三种逻辑结构的几点说明：1顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的 .在流程图中的表达就是用流程线自上而下地连接起来，按顺序执行算法步骤 .2一个条件结构可以有多个判断
4、框. 3循环结构要在某个条件下终止循环，这就需要条件结构来判断.在循环结构中都有一个计数变量和累加变量.计数变量用于记录循环次数，累加变量用语输出结果，计数变量和累加变量一般是同步执行的，累加一次，计数一次. 三、经典例题例 1 已知三个单元存放了变量x， y ，z的值，试给出一个算法，顺次交换x，y ，z的值即 y 取x的值，z取 y 的值，x取z的值 ，并画出流程精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 26 页图. 错解：第一步xy第二步yz第三步zx流程图为图 13-1-3 错因：未理解赋值的含义，由上面的算法使得y ，z
5、均取x的值. 举一形象的例子： 有蓝和黑两个墨水瓶， 但现在却把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题.对于这种非数值性问题的算法设计问题，应当首先建立过程模型， 根据过程设计步骤完成算法 . 我们不可将两个墨水瓶中的墨水直接交换，因为两个墨水瓶都装有墨水，不可能进行直接交换.正确的解法应为：S1 取一只空的墨水瓶，设其为白色；S2 将黑墨水瓶中的蓝墨水装入白瓶中；S3 将蓝墨水瓶中的黑墨水装入黑瓶中；S4 将白瓶中的蓝墨水装入蓝瓶中；S5 交换结束 . 正解：第一步zp先将z的值赋给变量 p ，这时存放z的单元可作它用 精选学习资料 - -
6、- - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 26 页第二步yz再将 y 的值赋给z，这时存放 y 的单元可作它用 第三步xy同样将x的值赋给 y ，这时存放x的单元可作它用 第四步px最后将 p 的值赋给 y ，三个变量x， y ，z的值就完成了交换 流程图为图 13-1-4 点评：在电脑中，每个变量都分配了一个存储单元，为了到达交换的目的，需要一个单元存放中间变量p . 例 2 已知三个数a，b ，c.试给出寻找这三个数中最大的一个算法，画出该算法的流程图 . 解：流程图为精选学习资料 - - - - - - - - - 名师归纳总结 - - - -
7、- - -第 4 页，共 26 页图 13-1-5 点评：条件结构可含有多个判断框，判断框内的内容要简明、准确、清晰.此题也可将第一个判断框中的两个条件分别用两个判断框表示，两两比较也很清晰.假设改为求 100 个数中的最大数或最小数的问题则选择此法较繁琐，可采用假设第一数最大最小将第一个数与后面的数依依比较，假设后面的数较大较小 ，则进行交换，最终第一个数即为最大最小值. 点评：求和时根据过程的类同性可用循环结构来实现，而不用顺序结构. 例 3 画出求222222100994321的值的算法流程图 . 解：这是一个求和问题，可采用循环结构实现设计算法，但要注意奇数项为正号，偶数项为负号 .
8、思路一：采用 -1 的奇偶次方利用循环变量来解决正负符号问题；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 26 页图 13-1-6 图 13-1-7 思路二：采用选择结构分奇偶项求和；图 13-1-8 思路三：可先将222222100994321化简成精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 26 页1991173， 转化为一个等差数列求和问题， 易利用循环结构求出结果 . 例 4 设计一算法， 求使20063212222n成立的最小正整数n的值. 解： 流程图为图 1
9、3-1-9 点评：这道题仍然是考察求和的循环结构的运用问题，需要强调的是求和语句的表示方法 .假设将题改为求使20063212222n成立的最大正整数n的值时，则需注意的是输出的值. 例 5 任意给定一个大于1 的整数 n，试设计一个程序或步骤对n 是否为质数做出判断 . 解：算法为：S1 判断 n 是否等于 2，假设 n=2 ，则 n 是质数；假设 n2，则执行 S2 S2 依次从 2n-1 检验是不是的因数，即整除n 的数，假设有这样的数，则 n 不是质数；假设没有这样的数，则n 是质数 . 点评：要验证是否为质数首先必须对质数的本质含义作深入分析：1质数是只能被 1 和自身整除的大于1
10、的整数 . 2要判断一个大于1 的整数 n 是否为质数，只要根据定义，用比这个精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 26 页整数小的数去除n.如果它只能被1 和本身整除，而不能被其它整数整除，则这个数便是质数 . 图 13-1-10 例 6 设计一个求无理数2的近似值的算法 . 分析：无理数2的近似值可看作是方程022x的正的近似根， 因此该算法的实质是设计一个求方程022x的近似根的算法 .其基本方法即运用二分法求解方程的近似解 . 解：设所求近似根与精确解的差的绝对值不超过0.005, 算法: S1 令2)(2xxf.因为
11、0)2(,0)1 (ff,所以设2, 121xxS2 令2)(21xxm,判断)(mf是否为 0,假设是 ,则 m 为所求 ;假设否 ,则继续判断)()(1mfxf大于 0 还是小于 0.S3 假设)()(1mfxf0, 则mx1;否则,令mx2. S4 判断005.021xx是否成立，假设是，则21,xx之间的任意值均为满足条件的近似根；假设否，则返回第二步. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 26 页点评：二分法求方程近似解的算法是一个重要的算法案例，将在第三节中详细阐述. 四、典型习题1已知两个单元分别存放了变量A和
12、B的值，则可以实现变量BA,交换的算法是. AS1 ABBS1 ACCS1 ACDS1 ACS2 BAS2 CBS2 BAS2 BDS3 BCS3 CB1 下面流程图中的错误是图 13-1-11 Ai 没有赋值B循环结构有错CS 的计算不对D判断条件不成立精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 26 页3. 将 “ 打” 的 过 程 描 述 成 一 个 算 法 ， 这 个 算 法 可 表 示为， 由 此 说 明 算 法 具 有 以 下 特性 . 4. 在表示求直线0cbyaxa， b 为常数，且a， b 不同时为 0的斜率的算法
13、的流程图中，判断框中应填入的内容是5. 3 个正实数，设计一个算法， 判断分别以这 3 个数为三边边长的三角形是否存在，画出这个算法的流程图 . 6.一队士兵来到一条有鳄鱼的深河的左岸.只有一条小船和两个小孩， 这条船只能承载两个小孩或一个士兵.试设计一个算法，将这队士兵渡到对岸，并将这个算法用流程图表示 . 13.2 基本算法语句一、知识导学1 赋值语句用符号“”表示， “yx”表示将 y 的值赋给x，其中x是一个变量， y 是一个与x同类型的变量或表达式 . 2 条件语句主要有两种形式： “行 If 语句”和“块 If 语句” . “行 If 语句”的一般形式为：If A Then B E
14、lse C . 一个行 If 语句必须在一行中写完，其中方括号中的Else 部分可以缺省 . “块 If 语句”的一般格式为 : If A Then 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 26 页B Else C End if Then 部分和 Else 部分是可选的，但块If 语句的出口“ End if ”不能省 . 3 循环语句主要有两种类型：For 语句和 While 语句. 当循环的次数已经确定，可用“For”语句表示 .“For”语句的一般形式为：For I from “初值” to step “步长” End f
15、or 上面“ For”和“ End for ”之间缩进的步骤称为循环体. 当循环次数不能确定是，可用“While ”语句来实现循环 .“While ”语句的一般形式为：While A End while 其中 A 表示判断执行循环的条件. 上面“ While ”和“ End While ”之间缩进的步骤称为循环体. 二、疑难知识1. 有的条件语句可以不带“Else”分支，即满足条件时执行B，否则不执行任何操作 .条件语句也可以进行嵌套， 在进行条件语句的嵌套时， 书写要有层次 .例如：If A Then B 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -
16、 -第 11 页，共 26 页Else if C Then D Else E End if 2.“For”语句是在执行过程中先操作，后判断.而“While ”语句的特点是“前测试” ，即先判断，后执行 .假设初始条件不成立，则一次也不执行循环体中的内容.任何一种需要重复处理的问题都可以用这种前测试循环来实现. 三、经典例题例 1 以下程序的运行结果是 . 9X8YIf X 5 Then 7YYIf X 4 Then 6YYIf X 3 Then 6YYPrint Y错解：8+7=15 错因：误认为在一个程序中只执行一个条件语句，与在一个条件语句中只选择其中一个分支相混淆 .If A Then
17、B Else C 假设满足条件 A 则执行 B，否则是执行C，B 和 C 是这个条件语句的分支，而这个程序省略了Else 部分. 正解：这里是有三个条件语句，各个条件语句是独立的，三个条件均成立，所以按顺序依次执行，结果为8+7+6+6=27. 例 2 下面的伪代码的效果是精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 26 页0iWhile i10 2iiEnd While End 错解：执行 10 次循环错因：将 For 语句和 While 语句混淆 . For 语句中有步长使循环变量不断变化，而 While 语句则无 . 正解：
18、无限循环下去，这是因为这里i 始终为 0，总能满足条件“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. 精选学习资料
19、 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 26 页正解：由于0S在循环内，每经过一次循环后S 都被赋值 0，因此，只要求满足条件的最后一次循环S 的值，即当4I时，16440S. 例 4 用语句描述求使10007531n成立的最大正整数n的算法过程 . 解：1n1TWhile 1000T2nnnTTEnd while Print 2n点评： 此题易错的是输出值， 根据 While 循环语句的特征当1000T时跳出循环体，此时n的值是1000T时的最小的整数，则使1000T的最大整数应为n的前一个奇数即2n. 例 5 已知当100100 x时
20、，1xy，当100 x时，4y，当100 x时，4xy，设计一算法求 y 的值. 解： Read x If 100100 xthen 1xyElse if 100 xThen 4xyElse 4yEnd if End 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 26 页点评：嵌套 If 语句可用如上的紧凑形式书写，要注意的是如不是采取紧凑形式，则需注意一个块 If 语句对应一个 End If ，不可省略或缺少 . 例 6设计一个算法，使得输入一个正整数n，输出 1！+2 ！+3 ！+ +n！的值.写出伪代码 . 解：思路一：利用单
21、循环， 循环体中必须包括一个求各项阶乘的语句以及一个求和语句 . Read n 01STFor I from 1 to n TSSITTEnd For Print S 思路二：运用内外双重循环，但尤其注意的是每一次外循环T 的值都要从 1 开始. Read n 0SFor I from 1 to n 1TFor J from 1 to I JTTEnd For TSSEnd For 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 26 页Print S 四 、典型习题1 以下的循环语句循环的次数为For I from 1 to 7 F
22、or J from 1 to 9 Pint I+J End for End for End A.7 次B.9 次C.63 次D.16 次2运行下面的程序后输出的结果是，假设将程序中的A 语句与 B 语句的位置互换，再次执行程序后输出的结果为 . 1x0yWhile 3xxyyA语句1xxB语句End While Print x,y End 3.伪代码描述的求T 的代数式是,求 S的代数式是 . Read n 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 26 页1T0SFor I from 1 to n ITTISSEnd for
23、Print T,S 4.运行下面程序后输出的结果为For I from 10 to 1 step -2 Print I End for End 5. 将 100 名学生的一门功课的成绩依次输入并计算输出平均成绩. 13 3 算法案例一、知识导学1算法设计思想：1 “韩信点兵孙子问题”对正整数m 从 2 开始逐一检验条件，假设三个条件中有任何一个不满足， 则 m 递增 1，一直到 m 同时满足三个条件为止 (循环过程用 Goto 语句实现 ) 2用辗转相除法找出ba. 的最大公约数的步骤是： 计算出ba的余数r，假设0r， 则 b 为ba,的最大公约数； 假设0r， 则把前面的除数 b作为新的被
24、除数，继续运算，直到余数为0，此时的除数即为正整数ba,的最大公约数 . 2.更相减损术的步骤：1任意给出两个正数，判断它们是否都是偶数.假设是，用 2 约简；假设不是，执行第二步.2以较大的数减去较小的数，接着把较小精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 26 页的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数等数就是所求的最大公约数. 3 二分法求方程0)(xf在区间ba,内的一个近似解*x的解题步骤可表示为S1 取ba,的中点bax210，将区间一分为二；S2 假设00 xf，则0 x就是
25、方程的根；否则判别根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的整数部分， 如0)32.0int(,5)86.5int(，但当x是负数时极易出错，如1)14.1int(就是错误的，应为 -2. 2),mod(ba表示a除以 b 所得的余数，也可用amod b 表示. 3辗转相除法与更相减损术求最大公约数的联系与区别：1都是求最大公约数的方法， 计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除
26、法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显. 2从结果表达形式来看，辗转相除法表达结果是以相除余数为0 则得到，而更相减损术则以减数与差相等而得到. 4用二分法求方程近似解，必须先判断方程在给定区间ba,上是否有解 ,即xf连续且满足0bfaf.并在二分搜索过程中需对中点处函数值的符号进行多次循环判定，故需要选择结构、循环结构，即可用Goto 语句和条件语句实现算法 . 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 26 页三、经典例题例 1)5int(，)05.0int(，)9 ,67mod(，45mod
27、 7= . 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( x表示的含义理解不透彻 ,将不超过 -0.05 的整数错认为是 0,将负数的大小比较与正数的大小比较相混淆. 正解：不超过 -0.05 的整数是 -1,所以答案为 D. 例 2 所谓同构数是指此数的平方数的最后几位与该数相等.请设计一算法判断一个大于 0 且小于 1000 的整数是否为同构数 . 错解： 算法思想：求出输入数的平方，考虑其个位或最后两位或最后三位
28、与输入数是否相等，假设相等，则为同构数. Read x xxyIf )10(yxor )100(yxor )1000(yxThen Print x End if End 错 因 ： 在 表 示个 位 或 最 后 两 位 或 最 后三 位 出 现 错误 ， “ / ”仅 表 示 除 ，y/10,y/100,y/1000都仅仅表示商 . 正解： 可用)1000,mod(),100,mod(),10,mod(yyy来表示个位，最后两位以及最后三位. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 26 页Read x xxyIf )10,m
29、od(yxor )100,mod(yxor )1000,mod(yxThen Print x End if End 例 3孙子算经中的“物不知数”问题： “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”可以用下面的算法解决：先在纸上写上 2，每次加 3，加成 5 除余 3 的时候停下来，再在这个数上每次加15，到得出 7 除 2 的时候，就是答数 . 试用流程图和伪代码表示这一算法. 解：流程图为：伪代码为：10 2m20 3mm30 If 35 ,mod mThen Goto 20 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -
30、 -第 20 页，共 26 页40 If 2)7,mod(mThen Print mGoto 80 50 End if60 15mm70 Goto 40 80 End 点评：这是孙子思想的表达，主要是依次满足三个整除条件. 例 4 分别用辗转相除法、更相减损法求192 与 81 的最大公约数 . 解：辗转相除法：S1 30281192S2 2123081S3 912130S4 32921S5 0339故 3 是 192 与 81 的最大公约数 . 更相减损法：S1 11181192S2 3081111S3 513081S4 213051S5 92130精选学习资料 - - - - - - -
31、- - 名师归纳总结 - - - - - - -第 21 页，共 26 页S6 12921S7 3912S8 639S9 336故 3 是 192 与 81 的最大公约数 . 点评：辗转相除法以除法为主， 更相减损术以减法为主， 计算次数上辗转相除法计算次数相对较少.辗转相除法是当大数被小数整除时停止除法运算，此时的小数就是两者的最大公约数， 更相减损术是当大数减去小数的差等于小数时减法停止，较小的数就是最大公约数.例 5 为了设计用区间二分法求方程0123xx在0，1上的一个近似解 误差不超过 0.001 的算法 ,流程图的各个框图如下所示,请重新排列各框图 ,并用带箭头的流线和判断符号“Y
32、”、“N ”组成正确的算法流程图,并写出其伪代码.(其中ba,分别表示区间的左右端点) 图 13-3-2 流程图为精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 26 页图 13-3-3 伪代码为10 Read ba,20 2)(0bax30 1)(23aaaf40 1)(20300 xxxf50 If 0)(0 xfThen Goto 120 60 If 0)()(0 xfafThen 70 0 xb100 End if 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 26
33、 页80 Else 90 0 xa100 End if 110 If 001. 0baThen Goto 20 120 Print 0 x130 End 点评：二分法的基本思想在必修一中已渗透，这里运用算法将二分法求方程近似解的步骤更清晰的表述出来. 例 6 用秦九韶算法计算多项式654323567983512)(xxxxxxxf在4x时的值时，3v的值为 . 解： 根据秦九韶算法，此多项式可变形为1235879653xxxxxxxf按照从内到外的顺序，依次计算一次多项式当4x时的值：40v75)4(31v346)7()4(2v577934)4(3v故当4x时多项式的值为57 . 点评：秦九韶
34、算法的关键是n 次多项式的变形 . 把一个n次多项式0111)(axaxaxaxfnnnn改写成0121)()(axaxaxaxaxfnnn，求多项式的值，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值，这样把求n次精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 26 页多项式的值问题转化为求n个一次多项式的值的问题， 这种方法成为秦九韶算法 .这种算法中有反复执行的步骤，因此，可考虑用循环结构实现.四、典型习题1以下短文摘自古代孙子算经一书，其引申出的“大衍求一术”称为“中国剩余原理”： “今有物不知其数，
35、三三数之剩二， 五五数之剩三， 七七数之剩二，问物几何？”答曰. A二十一B.二十二C.二十三D.二十四2用辗转相除法求52 与 39 的最大公约数的循环次数为. A1 次B.2 次C.3 次D.5 次3下面程序功能是统计随机产生的十个两位正整数中偶数和奇数的个数，并求出偶数与奇数各自的总和. For I from 1 to 10 10)90int( RndxPrint x; If Then xssnn22122Else xss11End If End for Print 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 25 页，共 26 页Pri
36、nt “奇数个数 =”； 1n，“偶数个数 = ”；2n4假设一个数的各因子之和正好等于该数本身，则该数成为完数.请补充完整以下找出 1100 之间的所有完数的伪代码. For afrom 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 End 5设计求被 9 除余 4，被 11 除余 3 的最小正整数的算法，画出流程图，写出伪代码 . 6利用辗转相除法或更相减损术求324,243,135的最大公约数 . 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 26 页，共 26 页