1、第十章算法初步、统计与统计案例10.1算法初步必备知识预案自诊知识梳理1.算法的定义通常是指按照一定规则解决某一类问题的和的步骤.2.程序框图(1)概念:程序框图又称,是一种用、及来表示算法的图形.通常程序框图由程序框和流程线组成,一个或几个程序框的组合表示算法中的一个步骤;带方向箭头,按照算法步骤的执行顺序将连接起来.(2)程序框图的图形符号及其功能:3.三种基本逻辑结构名称内容顺序结构条件结构循环结构定义由若干个按先后顺序执行的步骤组成,这是任何一个算法都离不开的基本结构算法的流程根据条件是否成立而选择执行不同流向的结构形式从某处开始,按照一定的条件某些步骤的情况,反复执行的步骤称为适用情
2、境解决的问题不需分类讨论解决的问题需分类讨论解决的问题要进行许多重复的步骤,且这些步骤之间有相同的规律续表名称内容顺序结构条件结构循环结构程序框图(1)(2)(1)(2)4.中国古代数学中的算法案例(1)求两个正整数(奇数)最大公约数的算法更相减损术:用两数中较大的数减较小的数,把得到的差,与较小的数再构成一对新的数.再用这对数中较大的数减较小的数,以同样的操作一直做下去,直到产生一对相等的数,这个数就是最大公约数.辗转相除法:用两数中较大的数除以较小的数,把所得的余数和较小的数构成一对新的数,继续做上面的除法,直到较大的数被较小的数除尽,这个较小的数就是最大公约数.(2)秦九韶算法:计算多项
3、式的值的一种方法,如下:f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0=(anxn-1+an-1xn-2+an-2xn-3+a1)x+a0=(anxn-2+an-1xn-3+an-2xn-4+a2)x+a1)x+a0=(anx+an-1)x+an-2)x+a1)x+a0.考点自诊1.判断下列结论是否正确,正确的画“”,错误的画“”.(1)一个程序框图一定包含顺序结构,但不一定包含条件结构和循环结构.()(2)算法只能解决一个问题,不能重复使用.()(3)条件结构的出口有两个,但在执行时,只有一个出口是有效的.()(4)当型循环是给定条件不成立时,执行循环体,反复进行,直到
4、条件成立为止.()(5)输入框只能紧接开始框,输出框只能紧接结束框.()2.某地区打的士收费办法如下:不超过2公里收7元,超过2公里时,每车收燃油附加费1元,并且超过的里程每公里收2.6元(其他因素不考虑),计算收费标准的程序框图如图所示,则处应填()A.y=2.0x+2.2B.y=0.6x+2.8C.y=2.6x+2.0D.y=2.6x+2.8(第2题图)(第3题图)3.我国古代数学名著孙子算经有鸡兔同笼问题,根据问题的条件绘制如图的程序框图,则输出的x,y分别是()A.12,23B.23,12C.13,22D.22,134.如图的程序框图,当输出y=15后,程序结束,则判断框内应该填()A
5、.x1B.x2C.x3D.x4(第4题图)(第5题图)5.运行如图所示的框图对应的程序,输出的结果为.关键能力学案突破考点条件结构为主的结果输出型问题【例1】(1)对任意非零实数a,b,若ab的运算原理如图所示,则(log222)18-23=()A.1B.2C.3D.4(第(1)题图)(第(2)题图)(2)输入a=1+7,b=3+5,c=2+6,经过如图所示的程序运算后,输出的a,b,c的值分别为()A.1+7,3+5,2+6B.3+5,1+7,2+6C.3+5,2+6,1+7D.2+6,3+5,1+7解题心得条件结构程序框图的解题技巧(1)利用条件结构解决算法问题时,要根据题目的要求引入一个
6、或多个判断框,而判断框内的条件不同,对应的下一个程序框中的内容和操作要相应地进行变化,故要逐个分析判断框内的条件.(2)解决此类问题,可按下列步骤进行:先弄清变量的初始值;按照程序框图从上到下或从左到右的顺序,依次对每一个语句、每一个判断框进行读取,在读取程序框时,应注意判断后的结论分别对应着什么样的结果,然后按照对应的结果继续往下读取程序框图;输出结果.(3)如果含有嵌套的条件结构,一定要分清外层条件与内层条件及上下逻辑关系.对点训练1(1)如图是根据我国古代数学专著九章算术中更相减损术设计的程序框图,若输入的a=18,b=42,则输出的a=()A.2B.3C.6D.8(2)某算法的程序框图
7、如图所示,其中输入的变量x在1,2,3,24这24个整数中等可能随机产生.则按程序框图正确编程运行时输出y的值为3的概率为()A.12B.13C.16D.18考点循环结构为主的结果输出型问题(多考向探究)考向1逐步推理验证类型【例2】(1)执行如图所示的程序框图,如果输入的x=0,y=1,n=1,则输出x,y的值满足()A.y=2xB.y=3xC.y=4xD.y=5x(2)执行如图所示的程序框图,则输出的n等于()A.1B.2C.3D.4解题心得解决循环结构程序框图问题的注意事项(1)搞清楚判断框内的条件由计数变量还是累加变量来表示;(2)要注意判断框内的不等式是否带有等号,这直接决定循环次数
8、的多少;(3)要准确利用程序框图的赋值语句与两个变量之间的关系,把握程序框图的整体功能,这样可以直接求解结果,减少运算的次数.对点训练2(2017全国2,理8)执行下面的程序框图,如果输入的a=-1,则输出的S=()A.2B.3C.4D.5考向2归纳推理得出规律类型【例3】执行如图所示的程序框图,则程序最后输出的结果为()A.15B.25C.35D.45解题心得归纳推理法适用的循环结构程序框图类型(1)在解决一些有规律的科学计算问题,尤其是累加、累乘等问题时,往往可以利用循环结构来解决.执行循环结构首先要分清是先执行循环体,再判断条件,还是先判断条件,再执行循环体.其次注意控制循环的变量是什么
9、,何时退出循环.最后要清楚循环体内的程序是什么,是如何变化的.(2)当循环次数较多时,逐一列出前面的若干步骤,观察、归纳,利用周期性或规律性得出答案.对点训练3执行如图所示的程序框图,则输出的结果n=.考点程序框图的补全问题【例4】如图程序框图是为了求出满足3n-2n2 020的最小偶数n,那么在和两个空白框中,分别可以填入()A.A2 020和n=n+1B.A2 020和n=n+2C.A2 020和n=n+1D.A2 020和n=n+2解题心得补全程序框图的条件或内容时,应结合初始条件和输出结果,分析控制循环的变量应满足的条件,或累加、累乘的变量的表达式,明确进入循环体时变量的情况、累加或累
10、乘变量的变化.具体解题方法有以下两种:一是先假定空白处填写的条件,再正面执行程序,来检验填写的条件是否正确;二是根据结果进行回溯,直至确定填写的条件是什么.注意:此类问题务必先分清是直到型循环结构还是当型循环结构,二者判断框中的条件在同一问题中相反.对点训练4执行如图所示的程序框图,若输出k的值为8,则判断框内可填入的条件是()A.s34B.s56C.s1112D.s2524考点程序框图的功能判断问题【例5】如图是根据南宋数学家杨辉的“垛积术”设计的程序框图,该程序所能实现的功能是()A.求1+3+5+(2n-1)B.求1+3+5+(2n+1)C.求12+22+32+n2D.求12+22+32
11、+(n+1)2解题心得判断程序框图的功能,根据程序框图的运行,分析其功能即可.对点训练52020年国庆期间,全国共接待国内游客6.18亿人次,其中某30个景区日均实际接待人数与最大接待人数比值依次记为ai(i=1,2,30),若该比值超过1,则称该景区“爆满”,否则称为“不爆满”,则如图所示的程序框图的功能是()A.求30个景区的爆满率B.求30个景区的不爆满率C.求30个景区的爆满数D.求30个景区的不爆满数第十章算法初步、统计与统计案例10.1算法初步必备知识预案自诊知识梳理1.明确有限2.(1)流程图程序框流程线文字说明流程线程序框(2)起始和结束输入和输出的信息赋值、计算成立与否先后顺
12、序3.反复执行循环体考点自诊1.(1)(2)(3)(4)(5)2.D当满足条件x2时,即里程超过2公里,超过2公里时,每车收燃油附加费1元,并且超过的里程每公里收2.6元,所以y=2.6(x-2)+7+1=8+2.6(x-2),即整理可得y=2.6x+2.8.故选D.3.B由程序框图,得x=1,y=34,S=138;x=3,y=32,S=134;x=5,y=30,S=130;x=7,y=28,S=126;x=23,y=12,S=94.输出x=23,y=12.故选B.4.C当x=-3时,y=3;当x=-2时,y=0;当x=-1时,y=-1;当x=0时,y=0;当x=1时,y=3;当x=2时,y=
13、8;当x=3时,y=15,x=4,结束.所以y的最大值为15,可知x3符合题意.判断框应填x3,故选C.5.19第一次循环:S=91,S=1,k=2;第二次循环:S=19,k=4;第三次循环:S=13,k=8;第四次循环:S=1,k=16;第五次循环:S=19,k=32;第六次循环:S=13,k=64;第七次循环:S=1,k=128;第八次循环:S=19,k=256;第九次循环:S=13,k=512;第十次循环:S=1,k=1024;第十一次循环:S=19,k=20482017,输出S=19,故答案为19.关键能力学案突破例1(1)A(2)C(1)由程序框图可知,程序的作用是计算分段函数y=b
14、-1a,ab,a-1b,ab的函数值,因为(log222)18-23=34,a=3b=4,所以y=4-13=1,故选A.(2)结合题设中提供的算法流程图中算法程序可知:当输入数据a=1+7,b=3+5,c=2+6时,因为ac=2+6,则直接判定出b=1+73,则返回继续循环;S=1+log232,n=n+1=3,不满足S3,则返回继续循环;S=1+log232+log243=1+1=2,n=n+1=4,不满足S3,则返回继续循环;当n=k时,S=1+log232+log243+log2k+1k=1+log2k+12,n=k+1,要满足S=1+log2k+123,则k8,k最小值为8,此时n=k
15、+1=9.例4D因为程序框图为当型循环,所以当A满足条件时,才会进行循环,显然不能填A2020,故排除A,B,由于要求输出n为偶数,且n的起始值为0,所以n=n+2.对点训练4C由程序框图可知,程序执行过程如下:s=0,k=0,满足条件;k=2,s=12,满足条件;k=4,s=34,满足条件;k=6,s=1112,满足条件;k=8,s=2524,这时应不满足条件,才能输出k=8,故判断框内的条件是s1112.例5C根据题意得a=1,S=1,i=2;a=4,S=1+4,i=3;a=9,S=1+4+9,i=4;a=16,S=1+4+9+16,i=5;依次写出S的表达式,发现规律,满足C.对点训练5B根据题意得,程序框图中只有当ai1时,才计数一次,并且进入循环,进入下一次判断,而这一条件就是不爆满的意思,故程序框图的功能是求30个景区的不爆满率.故选B.
