2022年高一数学必修三算法初步 2.pdf

1 第十一章 算法初步与框图（理）一、知识网络二、考纲要求1.算法的含义、程序框图（1）了解算法的含义，了解算法的思想. （2）理解程序框图的三种基本逻辑结构：顺序、条件分支、循环. 2.基本算法语句理解几种基本算法语句输入语句、输出语句、赋值语句、条件语句、循环语句的含义. 三、复习指南本章是新增内容，多以选择题或填空题形式考查，常与数列、函数等知识联系密切.考查的重点是算法语句与程序框图,以基础知识为主 ,如给出程序框图或算法语句,求输出结果或说明算法的功能 ;或写出程序框图的算法语句,判断框内的填空等考查题型.难度层次属中偏低 . 第一节算法与程序框图知识回顾1算法的概念：算法通常是指按一定规则解决某一类问题的明确和有限的步骤2.程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形. 3.程序框图的三种基本逻辑结构是顺序结构、条件结构、循环结构4.算法的描述方式有：自然语言、程序框图、程序语言5.算法的基本特征： 明确性：算法的每一步执行什么是明确的；顺序性：算法的 “ 前一步 ”是“ 后一步” 的前提， “ 后一步 ” 是“ 前一步 ” 的继续；有限性： 算法必须在有限步内完成任务，不能无限制的持续进行；通用性：算法应能解决某一类问题. 算法初步算法与程序框图算法语句算法案例算法概念框图的逻辑结构输入语句赋值语句循环语句条件语句输出语句顺序结构循环结构条件结构名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 23 页 - - - - - - - - - 2 典例精析例 1.如图所示是一个算法的程序框图，则该程序框图所表示的功能是解析：首先要理解各程序框的含义,输入 a,b,c三个数之后 ,接着判断 a,b的大小 ,若 b 小，则把 b赋给 a,否则执行下一步，即判断a与 c 的大小，若 c小，则把 c 赋给 a, 否则执行下一步，这样输出的 a是 a,b,c三个数中的最小值 .所以该程序框图所表示的功能是求a,b,c三个数中的最小值. 评注: 求 a,b,c三个数中的最小值的算法设计也可以用下面程序框图来表示.例 2.下列程序框图表示的算法功能是（）（1）计算小于 100 的奇数的连乘积（2）计算从 1 开始的连续奇数的连乘积（3）计算从 1 开始的连续奇数的连乘积，当乘积大于 100 时，计算奇数的个数（4）计算135n100成立时 n的最小值解析：为了正确地理解程序框图表示的算法，可以将执行过程分解，分析每一步执行的结果.可以看出程序框图中含有当型的循环结构,故分析每一次循环的情况,列表如名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 23 页 - - - - - - - - - 下: 第一次 :1 3,5Si；第二次 :1 3 5,7Si；第三次 :13 57,9Si,此时100S不成立 ,输出结果是 7,程序框图表示的算法功能是求使135n100成立时 n的最小值 . 选 D. 评注:通过列表 ,我们能清楚了解程序的每一步中的各个变量是怎样变化的,这正是程序运行的本质所在 .本题若要求编写求使135n100成立时 n的最小值的程序框图或程序时,很容易弄错输出的结果，应注意. 例 3.在音乐唱片超市里，每张唱片售价为25元，顾客如果购买5 张以上（含 5 张）唱片，则按九折收费，如果购买10 张以上（含 10 张）唱片，则按八折收费，请设计算法步骤并画出程序框图，要求输入张数x，输出实际收费y(元). 分析:先写出y与x之间的函数关系式，有25(5)22.5(510)20(10)xxyxxxx， 再利用条件结构画程序框图解： 算法步骤如下 : 第一步，输入购买的张数x, 第二步，判断x是否小于 5，若是，计算25yx；否则，判断x是否小于 10，若是，计算22.5yx；否则，计算20yx.第三步，输出y. 程序框图如下 : 评注:凡必须先根据条件做出判断，然后再决定进行哪一个步骤的问题，在画程序框图时，必须引入判断框，采用条件结构设计算法.如果变量分三级 (或以上 )时,就需要用到条件结构的嵌套,不能忽视结果中 “ 是” 、“ 否” 的书写，否则不知道执行哪一条路径.一般地 ,分 n段的分段函数 ,需要引入1n个判断框 .条件结构有以下两种基本类型.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 23 页 - - - - - - - - - 4 例 4.画出求222111123100的值的程序框图 . 分析:这是一个有规律的数列求和问题,每次都进行了相同的运算,故应用循环结构进行算法设计. 解:程序框图如下 : (1)当型循环 (2)直到型循环评注: (1) 解题关键是选择好计数变量i和累加变量S的初始值 ,并写出用i表示的数列的通项公式是 ；(2)循环结构主要用在一些有规律的重复计算的算法中,如累加求和 ,累乘求积等问题 .在循环结构中,要注意根据条件 ,设计合理的计数变量、 累加(积)变量以及它们的初始值等 ,特别要注意循环结构中条件的表述要恰当、精确，以免出现多一次或少一次循环. （3）循环结构分为两类：一类是当型循环结构，如下左图所示；另一类是直到型循环结构，如下右图所示 . 变式训练 画出求222111147100的值的程序框图 . 解：程序框图如下 :名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 23 页 - - - - - - - - - 5 例 5.某工厂 2005年的生产总值为 200 万元， 技术改进后预计以后后每年的年生产总值都比上一年增长 5%.设计一个程序框图，输出预期年生产总值超过300 万元的最早年份及2005年到此年份之前 (不包此年份 )的年生产总值的和 . 分析:本例可用循环结构来实现 . (1) 确定“循环体” :设 a为某年的年生产总值 ,n 为年份 ,S 为年产值的总和 ,则循环体为(2)初始化变量 :n 的初始值为 2005,a的初始值为 200,S的初始值为 0. (3)设定循环控制条件 :300a解: 程序框图如下 :,0.05 ,1.SSaaaann名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 23 页 - - - - - - - - - 6 评注 : 本问题的关健是设计好循环体, 注意SSa与 n 之间的对应关系 . 本题若将SSa放在1nn之后, 则输出时须重新赋值1nn，否则 n的值为超过 300 万的年份的下一年 .本题也可用当型循环结构来表示. 变式训练： 设计一个程序框图，求使1 235000Sn的最小 n的值，并输出此时S的值. 解：程序框图如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 23 页 - - - - - - - - - 7 基础自测一、选择题1下列说法正确的是（）A算法就是某个问题的解题过程；B算法执行后可以产生不同的结果；C解决某一个具体问题算法不同结果不同；D算法执行步骤的次数不可以很大，否则无法实施1解析 ：选项 A ，算法不能等同于解法；选项B，例如：判断一个正整数是否为质数，结果为“ 是质数 ” 和“ 不是质数 ” 两种；选项C，解决某一个具体问题算法不同结果应该相同，否则算法构造的有问题；选项D，算法可以为很多次，但不可以无限次选B2、如图所示的程序框图中，则第3 个输出的数是 ( ) A1 B. 32C.2 D. 522.解析： 前 3 个分别输出的数是1，32，2.故选 C. 3如图给出的是求201614121的值的一个程序框图，其中判断框内应填入的条件是（）A.i10? B.i20? D.i10？选4.(2007 年高考山东卷 )阅读右边的程序框图，若输入的n是 100，则输出的变量S和T的值依次是（）A2550，2500 B2550，2550 C2500，2500 D2500，2550 开始021Sni，1SSn2nn1ii结束是否输出S名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 23 页 - - - - - - - - - 9 4.解析： 依据框图可得1009896.22550S，999795.12500T.选 A.52006 年 1 月份开始实施的个人所得税法规定：全月总收入不超过1600元的免征个人工资、薪金所得税，超过1600元部分需征税设全月总收入金额为x 元，前三级税率如下左表所示：级数全月应纳税金额1600 x税率1 不超过500元部分5% 2 超过500至2000元部分10% 3 超过2000至5000元部分15% 开始00ST，TTnSSn2?n结束是否输出ST、输入n1nn1nn名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 23 页 - - - - - - - - - 10 当工资薪金所得不超过3600元，计算个人所得税的一个算法框图如图. 则输出、输出分别为( )A0.05 ;0.1xxB0.05 ;0.1185xxC0.0580;0.1 ;xxD0.0580;0.1185xx5解析 : 设全月总收入金额为x 元, 所得税额为y元,则y与 x之间的函数关系为0 (01600)(1600) 5% (16002100)25(2100) 10% (21003600)xyxxxx选 D.二、填空题6（2008 年高考山东卷） 执行右边的程序框图，若p=0.8, 则输出的 n=_. 6. 解析: 第一次循环后，10.82S，此时 n=2；第二次循环后，110.824S，此时 n3；第三次循环后，1110.8248S，此时4n，输出，故填 4.7. （2008年高考江苏卷）某地区为了解7080岁的老人的日平均睡眠时间（单位：h） ，随机选择了50 位老人进行调查，下表是这50 位老人睡眠时间的频率分布表：开始结束输入x输出 0 输出输出0 x1600?1600 x2100?2100n输出 S 结束是否图 2 开始输入 n i0 S0 i=i+1 S=S+2 输出 S 结束in? 否是图 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 23 页 - - - - - - - - - 15 知识回顾1任何一种程序设计语言都包含五种基本的算法语句，它们是输入语句， 输出语句，赋值语句，条件语句，循环语句2.输入语句的一般格式是;INPUT提示内容变量 ; 输出语句的一般格式是;PRINT提示内容表达式 ；赋值语句的一般格式是变量表达式；条件语句的一般格式是IFTHENENDIF条件语句体或IFTHENENDIF条件语句体 1ELSE语句体 2；循环语句的一般格式是DOLOOP UNTIL循环体条件和, WHILEWEND条件循环体. 输入语句、输出语句、赋值语句基本对应于程序框图中的顺序结构；条件语句、循环语句分别用来表达程序框图中的条件结构和循环结构.3. 常用符号运算符号：加 _+_，减 -_，乘*_，除/_ ，乘方 ab，整数取商，求余数 MOD. 逻辑符号：且 AND ，或 OR ，大于 ，等于 =，小于 =，小于等于 =，不等于 . 常用函数：绝对值ABS ，平方根 SQR ，取整 INT. 4. 算法案例（1）辗转相除法和更相减损术辗转相除法和更相减损术都是求两个正整数的最大公约数的方法. （1）辗转相除法就是对于给定的两个正整数，用大数除以小数，若余数不为0，则将小数和余数构成新的一对数，继续上面的除法，反复执行此步骤，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数. （2）更相减损术就是对于给定的两个正整数，若它们都是偶数，则将它们反复除以2( 假设进行了 k 次) ，直到它们至少有一个不是偶数后，将大数减小数，然后将差和较小的数构成一对新数，继续上面的减法，反复执行此步骤，直到差和较小的数相等，此时相等的数再乘以原来约简的2k即为所求两数的最大公约数. （2）秦九韶算法秦九韶算法是求多项式值的优秀算法. 设1110( )nnnnf xa xaxa xa ，改写为如下形式：( )f x1210().nnna xaxaxa xa设0101,nnvavv xa名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 23 页 - - - - - - - - - 16 21232310nnnnvv xavv xavvxa这样求 n 次多项式( )f x的值就转化为求n 个一次多项式的值 . 当多项式中有些项不存在时，可将这几项看做0nx，补齐后再利用秦九韶算法进行计算. 对于一个 n 次多项式，只需做n次乘法和 n 次加法运算即可 .（3）进位制K进制数的基数为 k，k 进制数是由01k之间的数字构成的 . 将十进制的数转化为k 进制数的方法是除k 取余法 . 110110(0,0,)nnnnka aa aakaa ak把 进制数化为十进制数的方法为1110()110nnnnknna aa aa kaka ka . 典例精析例 1写出用循环语句描述求11111123499100S的值的算法程序 . 解：算法程序如下：（1）当型循环（2）直到型循环评注: 在编写算法的程序时，可先画出程序框图，抓住程序框图表示算法这个核心.注意分别用当型循环和直到型循环语句编写的程序中，循环条件的区别与联系 . 例 2、某市对排污水进行综合治理，征收污水处理费，系统对各厂一个月内排出的污水量m吨收取的污水处理费y元，运行程序如下所示：1005015*(501315025(100)50)IFmTHENINPUTmIF mTHENymELSEELSEymEND IFEyND IFENmD12100( 1) (1) /1;SiWHILEiSSiiiiWENDPRINTSSEND12( 1) (1)/1100;SiDOSSiiiiLOOP UNTILiPRINT SSEND名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 23 页 - - - - - - - - - 17 请写出 y 与 m 的函数关系，并求排放污水150 吨的污水处理费用 . 解： 这个程序反映的是一个分段函数因为150100,m所以15025(150100)1400y，故该厂应缴纳污水处理费1400 元.评注: 解决分段函数要用条件语句来处理.本题可画出程序框图帮助理解.例 3 求三个数 72,120,168的最大公约数 . 解法 1:用辗转相除法先求 120,168的最大公约数 , 因为168120148,12048224,48242所以 120,168的最大公约数是24. 再求 72,24的最大公约数 , 因为72243,所以 72,24 的最大公约数为 24,即 72,120,168的最大公约数为24. 解法 2:用更相减损术先求 120,168的最大公约数 , 168-120=48,120-48=72,72-48=24,48-24=24 所以 120,168的最大公约数为24. 再求 72,24的最大公约数 , 72-24=48，48-24=24 72,24 的最大公约数为 24, 即 72,120,168的最大公约数为24. 评注 : 辗转相除法与更相减损术均是求两个正整数的最大公约数的方法 ,要理解和掌握它们的操作步骤. 变式 :试写出求正整数, ()m n mn的最小公倍数的算法程序 . 解: 13(50)5015(50) (50100)15025(100)(100)mmymmmm,0/INPUTm nSm nDOrm MOD nmnnrLOOPUNTILrSS mPRINTSEND名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 23 页 - - - - - - - - - 18 或例 4.用秦九韶算法求多项式5432( )23456f xxxxxx在2x时的值 . 分析：先改写多项式，再由内向外计算. 5432:( )23456(2)3)4)5)6f xxxxxxxxxxx解010213243541,243114265576120vvv xvv xvv xvv xvv x评注: 用秦九韶算法求多项式值,关健是正确将多项式改写,然后由内向外计算求得 . 本题也可简写为下式：12345622822 52 1144 11 26 57120例 5.完成下列进制的转化解:420(3)(10)(1)102021 3232 3101(2)用 8 反复去除 101,直到商为 0 止,所得的余数 (从末位读起 )就是十进制数 101的8 进制表示810181258 1401余数所以(10)(8)101145评注: 将k进制的数转化为k进制的数的方法是先将k进制的数转化为十进制的数，再将这个数转化为k进制的数 .(3)(10)(10)_(8)(1)10202_(2)101,1*10INPUTm niDOam ira MODniiLOOPUNTILrPRINTaEND名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 23 页 - - - - - - - - - 19 变式训练：下面是把二进制数(2)11111化为十进制数的一个程序框图,判断框内应填入的条件是 ( ) .5?.4 ?.4?.5?A iBiCiDi解:432(2)111111 21 21 21 21,故判断框内应填入的条件4i.选 C. 基础自测一、选择题1下列给出的赋值语句中正确的是（）A4MBMMC3BAD0 xy1. 解析:赋值语句的功能 .选 B 2当2x时，下面的程序输出的结果是( ) A3B7C15D172解析：0211,1 213,3217,72115. 选 C 3运行下列程序：,0INPUTm nDOrm MOD nmnnrLOOPUNTILrPRINTmEND10411isWHILEissxiiWENDPRINTIsUxETNNPD名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 23 页 - - - - - - - - - 20 当输入 56，42时，输出的结果是56428414 3.解析:该程序的功能是用辗转相除法求正整数, ()m n mn的最大公约数，故选D 4下边程序运行后输出的结果为( ) A50B5C25D04.解析:1,1;2,3;3,1;4,0;5,0jajajajaja.选 D 二、填空题5三个数3 2 4 , 2 4 3 , 1的最大公约数是 _5 解析:324243 181,13581 154,8154 127,54272.填276.阅读下列程序 : 015()51ajWHILEjaaj MODjjWENDPRINTaEND名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 23 页 - - - - - - - - - 21 当程序输入 x值为 123 时, 问运行的结果是 _. 6. 解析 : 算术运算符和 MOD分别用取商和余数 . 该程序的功能是把一个三位数各位上的数字颠倒过来 . 所以运行的结果是321. 7 （2005 年高考北京卷理14）已知 n 次多项式1011( )nnnnnP xa xa xaxa，如果在一种算法中，计算0kx （k2，3，4，n）的值需要 k1 次乘法，计算30()P x的值共需要 9次运算（ 6 次乘法， 3 次加法） ，那么计算100()Px的值共需要次运算 .下面给出一种减少运算次数的算法：0011( ),( )( )kkkP xaPxxP xa（k0， 1，2，n1） 利用该算法，计算30()P x的值共需要 6 次运算，计算100()Px的值共需要次运算 . 7解析：秦九韶算法适用一般的多项式1011( )nnnnnP xa xa xaxa 的求值问题 .直接法乘法运算的次数最多可到达2)1(nn，加法最多n 次.秦九韶算法通过转化把乘法运算的次数减少到最多 n次，加法最多 n 次.答案： 65；20. 8下面程序运行后输出的结果为_8解析: 22，-22 520033,xyIFxTHENxyELSEyyENDIFPRINTxy yxEND1001000100(100) 101010010INPUTxIFxANDxTHENaxbxacx MODxcbaPRINTxEND IFEND名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 23 页 - - - - - - - - - 22 三、解答题9.用秦九韶算法求多项式5432( )34157678f xxxxxx在2x时的值 . 543201021324354:( )34157678(34)15)76)7)83,421511769871898386f xxxxxxxxxxxvvv xvv xvv xvv xvv x9. 解10设计程序，求出满足11111023n的最小的正整数 n. 10解：11若(2)(6)(9)111111 ,210,85abc, 试判断, ,a b c的大小关系，并将 c化为 7 进制的数 . 6. 解析: (10)(10)(10)63,78,77abcbca7777711071401(140)c余数12.某电信公司规定：拨打市内电话时，如果不超过3 分钟，则收取话费0.2 元；如果通话时间超过 3 分钟，则超出部分按每分钟0.1 元收取通话费，不足一分钟按一分钟计算.设通话时间为 t（分钟） ，通话费用 y（元） ，如何设计一个程序，计算通话的费用. (提示:INT(x) 表示不大于 x 最大整数 ,如 INT(3.2)=3) 011/1101SiDOSSiiiLOOP UNTIL SPRINTiEND名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 23 页 - - - - - - - - - 23 12解：算法分析：数学模型实际上为： y 关于 t 的分段函数 .关系是如下：0.2,(03)0.20.1(3),(3,)0.20.1(31),(3,)tytttZtttZ其中t3表示取不大于 t3 的整数部分 . 算法步骤如下：第一步：输入通话时间t；第二步：如果 t 3 ，那么 y = 0.2；否则判断 tZ 是否成立，若成立执行 y= 0.2+0.1 (t3)；否则执行 y = 0.2+0.1（ t3+1）. 第三步：输出通话费用c .算法程序如下：;30.2( )0.20.1 (3)0.20.1 (3)1);INPUTttIF tTHENyELSEIFINT ttTHENytELSEyINT tEND IFENDIFPRINTyyEND名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 23 页 - - - - - - - - -