高考理数完美复习专题十三算法初步完美

专题十三 算法初步 目 录 CONTENTS 考点一 算法初步 考点一 算法初步 必备知识 全面把握 核心方法 重点突破 考法例析 成就能力 必备知识 全面把握 考点一 算法初步 1．算法 (1)算法的定义 在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步 骤．现在，算法通常可以编成计算机程序，让计算机执行并解决问题． (2)算法的特点 确定性、顺序性、正确性、有限性、不唯一性和普遍性． 5 算法是能解决一类问题的通解通法，它不同于求解一个具 体问题的方法，它有如下的要求： (1)写出的算法必须能解决一类问题(如判断一个整数是否为质数)， 并且能够重复使用． (2)要使算法尽量简单，步骤尽量少． (3)要保证算法正确，且计算机能执行，如让计算机去执行“倒一杯 水”是做不到的． 考点一 算法初步 必备知识 全面把握 1．算法 6 (1)程序框图的定义 程序框图又称流程图，是一种用规定的程序框、流程线及文字说明来准确、直 观地表示算法的图形． (2)三种基本逻辑结构 ①顺序结构 由若干个依次(按箭头指向)执行的步骤组成，是任何一个算法都离不开的基本 结构，其程序框图如图所示． 2．程序框图 考点一 算法初步 7 ②条件结构 算法的流程根据条件是否成立有不同的流向，其程序框图如图(1)和图(2)所示． ③循环结构 从某处开始，按照一定的条件反复执行某些步骤的情况，反复执行的步骤称为 循环体．循环结构的三要素：循环变量、循环体、循环终止的条件．循环结构 又分为直到型循环结构和当型循环结构． 考点一 算法初步 直到型循环结构：先执行一次循环体，再对循环终止的条件进行判断， 如果不满足条件就继续执行循环体，直到满足条件时终止循环，其程序框 图如图所示． 当型循环结构：每次执行循环体前，先对条件进行判断，如果条件满足， 则执行循环体，不满足就终止循环，其程序框图如图所示． 考点一 算法初步 9 三种基本结构都具有以下特点： (1)只有一个入口． (2)只有一个出口(请注意一个菱形判断框有两个出口，而一个条件结构 只有一个出口，不要把菱形框的出口和条件结构的出口混为一谈)． (3)结构中的每一个部分都有机会被执行到，即对于每一个框来说，都应 当有一条从入口到出口的路径通过它． (4)结构内不能存在“死循环”(无终止的循环)． 考点一 算法初步 2．程序框图 10 (1)输入语句 ①输入语句的一般格式 ②输入语句的作用是实现算法的输入信息功能． (2)输出语句 ①输出语句的一般格式 ②输出语句的作用是实现算法的输出结果功能． 3.算法语句 INPUT“提示内容”；变量 PRINT“提示内容”；表达式 考点一 算法初步 11 (3)赋值语句 ①在表述一个算法时，经常要引入变量，并赋予该变量一个值．用来表明赋 给某一个变量一个具体的值的语句叫做赋值语句． ②赋值语句的一般格式 ③作用：赋值语句中的“＝”称为赋值号．赋值语句的作用是先计算出赋值 号右边表达式的值，然后把该值赋给赋值号左边的变量，使该变量的值等于 表达式的值． (4)条件语句 ①条件语句一般用在需要对条件进行判断的算法设计中，例如判断一个数的 正负、确定两个数的大小、求分段函数的函数值等问题要用到条件语句． ②条件语句常用运算符：“>(大于)”“＝(大于或等于)”“< ＝(小于或等于)”“≠(不等于)”． ③要区别好条件语句的两种格式：IF－THEN格式和IF－THEN－ELSE格式， 理解它们的区别与联系，以及在实际编写程序中各自的特点． 考点一 算法初步 12 a．IF－THEN－ELSE格式 考点一 算法初步 条件语句的两种格式及框图： 13 b．IF－THEN格式 考点一 算法初步 条件语句的两种格式及框图： 14 (5)循环语句 ①循环语句主要用来实现算法中的循环结构．在处理一些需要反复执行的运算 任务时，例如累加求和、累乘求积等问题中常常要用循环语句来编写程序． ②循环语句有两种格式：WHILE循环和UNTIL循环．WHILE循环语句尤其适用于 解决一些事先不确定循环次数的问题，WHILE循环语句中的表达式的结果为真 时，执行循环体，为假时跳出循环体． a．WHILE语句 b．UNTIL语句 考点一 算法初步 15 (2)秦九韶算法：计算多项式的值的一种方法，如下： 考点一 算法初步 ①更相减损术：用两数中较大的数减较小的数，把得到的差，与较小的数再构成新 的一对数；对这一对数，再用较大数减较小数，以同样的操作一直做下去，直到产 生一对相等的数，这个数就是最大公约数． 4．中国古代数学中的算法案例 (1)求两个正整数(奇数)最大公约数的算法 ②辗转相除法：用两数中较大的数除以较小的数，把所得的余数和较 小的数构成新的一对数，继续上面的除法，直到较大数被较小数整除， 这个较小的数就是最大公约数． 16 核心方法 重点突破 方法1 含有条件结构的程序框图  含有条件结构的框图问题的实质就是与分段函数相关的问题，处理 办法是仔细阅读框图，把条件结构所实现的程序功能弄清楚，可能是 分段函数求函数值、分段函数求值域，也可能是解决一个多分支问 题．总而言之，把条件结构所要表达的各分支的功能及条件弄清楚， 然后根据条件选择某一分支，是解决这类问题的关键．求解中一般需 要利用分类讨论思想． 考点一 算法初步 17 （例1)执行如图所示的程序框图，如果输出的结果为0，那么输入的x为(  ) A.0 B．－1或1 C．1 D．－1                    【解析】由程序框图可知，输出的y的值是0.在y＝－x2＋1中，令y＝0，解得x ＝1或x＝－1.将x＝1和x＝－1代入程序框图验证发现，当x＝－1时，y＝0；当 x＝1时，y＝5.∵当x>0时，y＝3x＋2>3，∴输入的x≤0.∴x＝－1，故选D. 【答案】D 考点一 算法初步 18 方法2 含有循环结构的程序框图  对于循环结构，要先弄清循环体、变量的初始值和循环的终止条 件．当循环次数较少时，可列出每一步的运行结果，直至程序结束， 自然就得出答案；当循环次数较多时，可逐一列出前面的若干步骤， 观察、归纳其中的规律，从而得出答案．这是最常用、最有效、最适 合学生认知水平的方法． 考点一 算法初步 19 考点一 算法初步 （例2)如图所示的3个程序框图中，能输出满足12＋22＋32＋…＋n2＞106的最 小正整数n的是________．(填序号) 【解析】图①中变量i2加给S后i再加1， 在检验条件时，满足条件后输出的i比 实际值多1，显然是未重视最后一次循 环的检验所致；图②中，i加1后再将i2 加给S，由于开始时i＝1，这样导致第 一次执行循环体时加的就是22，漏掉了 第1项，是由于未重视第一次执行循环 时的数据所致．图③是满足条件的． 【答案】③ 20 方法3 补全程序框图中的条件  解决此类问题，应结合初始条件和输出的结果，分析控制循 环的变量应满足的条件或累加、累乘的变量的表达式，明确进 入循环体时变量的情况、累加或累乘变量的变化．具体解题方 法有以下两种：一是先假定空白处填写的条件，再正面执行程 序，来检验填写的条件是否正确；二是根据结果进行回溯，直 至确定填写的条件． 考点一 算法初步 21 （例3)[河南2018模拟]执行如图所示的程序框图，若输入m＝0， n＝2，输出的x＝1.75，则空白判断框内应填的条件可能是(  ) A．|m－n|1 000，且当判断框条件不满足时输出，则“ ”内 应填“A≤1 000”．故选D. 考点一 算法初步 【答案】D 32 考法3 由程序框图确定程序的功能 考点一 算法初步 (例3)[课标全国Ⅱ2013·6]执行如图的程序框图，如果输入的N＝10，那 么输出的S＝(  ) 33 考点一 算法初步 34 【点拨】求解本题时应注意循环结束的条件是I6，结束运 行，故输出的S＝8. 【答案】8 考点一 算法初步 （例4)[江苏2018·4]一个算法的伪代码如图所示，执行此算法，最后输出的S的 值为________．