第二章 算法与程序设计-高中信息科技合格考一本通

１９　 第二章　算法与程序设计 一、算法的概念及特征 算法的概念 １􀆰算法是在有限步骤内求解某一问题所使用的操作步骤和方法. ２􀆰程序设计就是寻求解决问题的方法,确定这些步骤的过程就是算法与程序设计过程. 算法的特征 １􀆰有穷性:算法必须由有限个步骤组成,即算法一定要能够结束. ２􀆰确定性:算法中的每一个步骤都应该是确定的,不能有歧义. ３􀆰可行性:算法中的每一个步骤都可以被计算机执行,可以方便地用来解决某一类问题. ４􀆰有０个或多个输入:输入是指算法的执行需要从外界获取数据,为算法的某些阶段建 立初始状态,如果建立初始状态所需要的数据已经包含在算法中,那就不需要再输入. ５􀆰有一个或多个输出:算法用来解决问题,问题的解决不管成功与否,结果应以一定的方 式输出. 　 ２０　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 二、算法的描述方法 算法的描述就是把解决问题的方法和步骤用规范的方式描述出来.常用的算法描述方法 主要有以下三种: １􀆰自然语言:自然语言是采用人类日常生活中使用的语言.用自然语言描述算法通俗易懂. ２􀆰流程图:由一些简单的图形符号组成,用来表示问题解决的步骤及顺序的方法.用流 程图表示算法,整个流程直观、清晰(见表２Ｇ１). ３􀆰伪代码:伪代码是一种介于自然语言和计算机程序设计语音之间的算法描述语言.能 够较容易地被转换成程序设计语言. 表２Ｇ１　流程图中常用的符号 处理框 输入输出框 判断框 连接框 流程线 开始/结束符 三、算法的基本控制结构 １􀆰顺序结构 顺序结构:是一种自上而下,按先后顺序依次执行算法中各个步骤的结构,如图２Ｇ１所示. 图２Ｇ１　顺序的结构 ２􀆰分支结构 分支结构:也称为选择结构,是根据给定的条件进行判断,再依据判断结果的不同而执行 不同操作的一种结构.分支结构流程图中一定会有判断框,当满足条件时执行一个分支,不满 足条件时执行另外一个分支.分支结构分为单分支和双分支(多分支),如图２Ｇ２所示. 图２Ｇ２　分支结构 ２１　 ３􀆰循环结构 循环结构:也称为重复结构,是一种根据条件重复执行某一部分操作的结构,其中重复执 行的这部分操作也称为循环体.循环结构有两种模式:当型循环和直到型循环,如图２Ｇ３ 所示. 图２Ｇ３　循环结构 (１)当型循环先判断循环条件,后执行循环体.当判断框中的条件为“是”时,执行循环结 构中的循环体,再根据条件判断是否需要继续执行循环体,直到条件为“否”,循环结束.直到 型循环先执行循环体,再判断循环条件是否成立.先执行一次循环体,然后判断条件,当条件 为“否”时,返回重新执行循环体,再判断条件,直到条件为“是”时结束循环. (２)设计循环结构时要注意循环条件,控制循环的变量,循环体三个要素.循环次数确定 的情况下,可以借助计数器来控制循环的结束.循环次数不确定的情况下,用循环条件判断是 否为真或假来控制循环的执行与结束. (３)计数器累乘器的应用. 计数器:指算法执行过程中,用来统计某条指令或者程序执行的次数变量存储单元,赋变 量初值为０. 例如:　　　　Sum＝０　　　　　Sum 累加求和,赋初值为０ Sum＝Sum＋１ Sum 加１,覆盖前一次的结果 累乘器:指算法执行过程中,用来存储数据之积的变量存储单元,赋变量初值为１. 例如: Sum＝１ Sum 累乘求积,赋初值为１ Sum＝Sum∗i Sum 存储相乘之乘积,覆盖前一次的结果 四、算法实现过程 面对特定的问题,往往需要根据设计的算法编写特定的程序来解决问题.编程解决问题 的过程:提出问题—抽象与建模—设计算法—编写程序—调试运行. １􀆰提出问题 针对现状提出需要解决的问题. 　 ２２　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ２􀆰抽象与建模 抽象与建模是指从现实问题出发,忽略非本质的细节,提炼出核心要素,将具体的问题抽 象化,并将其描述称为一个明确已知条件、约束条件和求解目标的问题,再用数学符号来描述 计算模型. ３􀆰设计算法 针对特定问题的分析结果,设计一个对应求解的解决方法和实现方式. ４􀆰编写程序 确定算法后,就可以编写程序,选择合适的计算机程序设计语言,按照设计的算法来实现 问题的求解. ５􀆰调试运行 编写的程序需要调试验证所编写的程序是否能实现问题的求解,同时检验编写的程序是 否存在不足之处. 例２Ｇ１　什么是算法? 它与计算过程和程序有什么区别? 分析与解答:算法是指求解一个问题所需的具体步骤和方法,它是程序指令的有限序列. 算法有一系列明确定义的基本指令序列,描述特定问题的求解过程.程序有合法的输入,它能 够在有限时间内产生所需的输出. 例２Ｇ２　以下流程图描述的算法中,正确的是(　　). 分析与解答:本题考查算法特征:算法是在有限步骤内求解某一问题所使用的操作步骤和 方法,具有五个重要特征,即有穷性、可行性、确定性、可以没有输入、必须有输出等特征.图 A 正确,所有特征都符合;图B不符合可行性,分数分母不能为０;图 C不符合确定性,自然数是 不确定的变量;图D不符合有穷性,循环不能正常结束.即答案是 A. ２３　 例２Ｇ３　流程图２Ｇ４,关于算法特征的描述中正确的是(　　). 图２Ｇ４ A．此流程图不符合算法的可行性特征 B．此流程图符合算法的特征 C．此流程图不符合算法的确定性特征 D．此流程图不符合算法有一个或多个输出的特征 分析与解答:本题考查算法的五个主要特征:有穷性、可行性、确定性、可以没有输入、必须 有输出.根据单分支结构流程图的描述,进行条件判断时,如果条件成立执行“是”分支无输 出,不符合必须有输出的算法特征.即答案是D. 例２Ｇ４　按流程图２Ｇ５描述的算法执行结果是(　　). 图２Ｇ５ 　　 １􀆰N＝１,S＝０,N＜＝１００成立程序执行“是”分支,执行 S＝S＋１＝１;N＝N＋１＝２ ２􀆰N＝２,S＝１,N＜＝１００成立程序执行“是”分支,执行 S＝S＋１＝２;N＝N＋１＝３ ３􀆰N＝３,S＝２,N＜＝１００成立程序执行“是”分支,执行 S＝S＋１＝３;N＝N＋１＝４ 􀆺 １００􀆰N＝１００,S＝９９,N＜＝１００成立程序执行“是”分支,执行 S＝S＋１＝１００;N＝N＋１＝１０１ １０１．N＝１０１,S＝１００,N＜＝１００不成立程序执行“否”分支退出循环, 执行Prints＝１００ A．９９ B．１００ C．１０１ D．５０５０ 分析与解答:即答案是B. 例２Ｇ５　小明为机器人设计算法“机器人走棋盘”.观察图２Ｇ６(a)棋盘,为使机器人从 A 位置沿着箭头方向到达B位置方向,图b流程图中的条件应该设置成(　　). 　 ２４　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 图２Ｇ６ A．i＜＝５ B．i＜＝６ C．i＜５ D．i＜＝７ 分析与解答:本题考查循环概念:A从所在的行,到B所在的行一共有５行的间隔,需要前 进５格以后再左转一次,然后再前进一格到达B所在的位置.即答案是 A. 例２Ｇ６　如图２Ｇ７所示算法,如果输入n＝３０,输出s＝３２,则在空白横线处用s和n组成一 个表达式应填(　　). 　　 图２Ｇ７ 　　　 １􀆰s＝１,i＝１,s＜n成立程序执行“是”分支 s＝s＋i＝２,i＝i∗２＝２ ２􀆰s＝２,i＝２,s＜n成立程序执行“是”分支 s＝s＋i＝４,i＝i∗２＝４ ３􀆰s＝４,i＝４,s＜n成立程序执行“是”分支 s＝s＋i＝８,i＝i∗２＝８ ４􀆰s＝８,i＝８,s＜n成立程序执行“是”分支 s＝s＋i＝１６,i＝i∗２＝１６ ５􀆰s＝１６,i＝１６,s＜n成立程序执行“是”分支 s＝s＋i＝３２,i＝i∗２＝３２ ６􀆰s＝３２,i＝３２,s＜n不成立程序执行“否”分支退出循环 Prints＝３２ 分析与解答:本题考查循环结构,输入n＝３０,输出s＝３２,填入n和s组成的表达式,此处 为循环的判断控制条件,s的值由１变为３２不断地增加,最后跳出循环,所以s小于n,即答案 是s＜n. 例２Ｇ７　关于双重循环的表述中错误的有(　　). ①两个单循环在程序中前后排列,不能称之为双重循环; ２５　 ②内循环的循环变量和外循环的循环变量可以使用同名简单变量; ③双重循环的整个内循环体执行的次数就是外循环的循环次数. A．三个 B．—个 C．零个 D．两个 分析与解答:本题考查双重循环概念:①两个单循环在程序中前后排列,循环各自独立,互 相不影响,不属于双重循环,双重循环特点循环之间互相嵌套.②内循环的循环变量和外循环 的循环变量不能相同,否则在循环执行过程中出现逻辑错误.③双重循环由外向内,分外循环 和内循环,外循环执行的次数即为第一层循环的次数,内循环执行次数即为第二层循环的次 数,整个循环体执行的次数就是外循环次数和内循环次数相乘.即答案是D. 例２Ｇ８　如２－８图所示流程图,描述的算法执行结果是(　　). 图２Ｇ８ 　 １􀆰i＝１,n＝０,i＜＝１８成立程序执行“是”分支 k＝i＋１＝２＜＝１８成立程序执行“是”分支 验证i＋k是否等于１８,等于１８执行n＝n＋１ 如果i＋k不等于１８执行k＝k＋１＝３,内循环继续执行k＝k＋１＝４,k＝ k＋１＝５􀆺􀆺直到k＝１７,i＋k＝１８,执行n＝n＋１＝１,最后程序执行k＝ k＋１＞１８,跳出内循环执行i＝i＋１＝２ ２􀆰i＝２,n＝１,i＜＝１８成立程序执行“是”分支 k＝i＋１＝３＜＝１８成立程序执行“是”分支 验证i＋k是否等于１８,等于１８执行n＝n＋１ 如果i＋k不等于１８执行k＝k＋１＝４,k＝k＋１＝５􀆺􀆺直到k＝１６,i＋ k＝１８,执行n＝n＋１＝１,n＝n＋１＝２,最后程序执行k＝k＋１＞１８,跳出 内循环执行i＝i＋１＝３ ３􀆰i＝３,n＝２,i＜＝１８成立程序执行“是”分支 k＝i＋１＝４＜＝１８成立程序执行“是”分支 验证i＋k是否等于１８,等于１８执行n＝n＋１ 如果i＋k不等于１８执行k＝k＋１＝５,k＝k＋１＝６􀆺􀆺直到k＝１５,i＋ k＝１８,执行n＝n＋１＝１,n＝n＋１＝３,最后程序执行k＝k＋１＞１８,跳出 内循环执行i＝i＋１＝４后面依次反复以上步骤. A．８ B．９ C．１６ D．１７ 分析与解答:本题考查双重循环,右边部分详解得出规律,当i＋k＝＝１８时执行n＝n＋１, 一共１７组符合条件的数据,但是有一个隐含条件k＝i＋１,可以判断k＞i,所以继续缩小符合 条件的范围,只有８组.即答案是 A. 　 ２６　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 １􀆰如下四个流程图中,存在两个以上分支结构但不属于分支结构嵌套的是(　　). ２􀆰以下四种关于算法基本结构嵌套的叙述中,正确的有(　　). ①分支结构可以嵌套分支结构;②分支结构可以嵌套循环结构; ③循环结构可以嵌套分支结构;④循环结构可以嵌套循环结构. A．４种 B．３种 C．２种 D．１种 ３􀆰以下关于算法特征的表述中,正确的是(　　). A．输入:算法在执行时,有可能需要从外界获取数据,因此一个算法中必须有输入操作 B􀆰输出:算法的目的是解决问题,问题的结果应以一定的方式输出,因此算法必须有输出 C．算法可以用无限个步骤来实现 D．设计的算法可以和文字一样存在不确定的结果 ４􀆰以下流程图符合算法特征的是(　　). A．图a B．图b C．图c D．图d ２７　 ５􀆰流程图２Ｇ９输入一个学生成绩score,根据成绩的不同值,输出不同.若score＜６０,则输出 “请努力”,若６０＜＝score＜＝９０,则输出“及格”,若score＞９０,则输出“优秀”.在空白横线 处应填(　　). 图２Ｇ９ A．score＞９０ B．score＜９０ C．score＜＝９０ D．score＞＝６０andscore＜＝９０ ６􀆰如图２Ｇ１０所示算法,输入k是３,该算法输出结果是 . 图２Ｇ１０ 　 ２８　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ７􀆰如图２Ｇ１１所示算法,输出结果是 . 图２Ｇ１１ ８􀆰如图２Ｇ１２所示算法,输出结果是 . 图２Ｇ１２ ９􀆰图２Ｇ１３(a)是机器人所走棋盘,根据右侧图(b)的算法,机器人从 A位置沿箭头方向出发,将 达到(　　). 图２Ｇ１３ A．４位置 B．１位置 C．２位置 D．３位置 ２９　 １０􀆰如图２Ｇ１４所示算法,若输入x是２,则输出结果是(　　). 图２Ｇ１４ A．４８ B．１２０ C．２４０ D．１２ １１􀆰如图２Ｇ１５所示算法,若输入x是３,则输出结果是(　　). 图２Ｇ１５ A．１１　６ B．１９　５ C．１６　６ D．１５　６ 　 ３０　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 １２􀆰流程图２Ｇ１６描述的算法执行结果是(　　). 图２Ｇ１６ A．１５ B．２０ C．２５ D．３６ １３􀆰流程图２Ｇ１７描述的算法执行结果是(　　). 图２Ｇ１７ A．１５ B．１２ C．１０ D．８ ３１　 １４􀆰流程图２Ｇ１８描述的算法执行结果是(　　). 图２Ｇ１８ A． B． C． D． １５􀆰流程图２Ｇ１９描述的算法功能是(　　). 图２Ｇ１９ 　 ３２　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 A．从小到大依次输出三个数 B．从大到小依次输出三个数 C．按中、大、小依次输出三个数 D．按中、小、大依次输出三个数 １６􀆰流程图２Ｇ２０描述的算法功能是(　　). 图２Ｇ２０ A．统计连续输入的字符的个数 B．统计连续输入的 A与Z之间的字符个数 C．求输入数中的字符数 D．统计连续输入的数中 A与Z的个数 １７􀆰流程图２Ｇ２１描述的算法功能是(　　). 图２Ｇ２１ A．求１＋２＋４＋７＋１１＋􀆺前１０项的和 B．求１＋２＋４＋７＋１１＋􀆺前９项的和 C．求１＋２＋３＋４＋５＋􀆺前１０项的和 D．求１＋２＋３＋４＋５＋􀆺前９项的和 ３３　 １８􀆰流程图２Ｇ２２描述的算法功能是(　　). 图２Ｇ２２ A．求１∗３∗５∗􀆺∗９９的积 B．求１∗４∗７∗􀆺∗９７的积 C．求１∗４∗７∗􀆺∗１００的积 D．求１∗４∗７∗􀆺∗１０３的积 １９􀆰流程图２Ｇ２３描述的算法功能是(　　). 图２Ｇ２３ A．计算１＋２＋３＋􀆺＋４９＋６０的和 B．计算１＋３＋５＋􀆺＋９７＋１１９的和 C．计算１＋３＋５＋􀆺＋４７＋５９的和 D．计算１∗２∗４∗􀆺∗９８∗１１９的积 　 ３４　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ２０􀆰流程图２Ｇ２４描述的算法功能是(　　). 图２Ｇ２４ A．求输入的２０个数的和 B．求输入的２０个数中正数的和 C．求输入的２０个数中正数的个数 D．求输入的２０个数的平均值 １􀆰如图２Ｇ２５所示算法,若输入的x值分别为１０００、９８０、４３２５、６００、５５,输出结果是 . 图２Ｇ２５ ３５　 ２􀆰如图２Ｇ２６所示算法,若输入x值分别为１０、－８、０、－２、－５、３,输出结果是 . 图２Ｇ２６ ３􀆰如图２Ｇ２７所示算法,若a,b为正整数,则输出结果为a与 b的乘积,完成横线处流程 图 . 图２Ｇ２７ ４􀆰如图２Ｇ２８所示算法,输入a为２２,b为４,则输出结果为a除 b的商,完成横线处流程 图 . 图２Ｇ２８ 　 ３６　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ５􀆰如图２Ｇ２９所示算法,若输入n＝４,输出是１０８,则用a与n在空白横线处组成一个完整的表 达式,应填 . 图２Ｇ２９ ６􀆰如图２Ｇ３０所示算法,若输入n＝４,输出s＝１４,则在空白横线处用i、n组成一个表达式,应 填 . 图２Ｇ３０ ７􀆰如图２Ｇ３１所示算法,若输入s＝３２,输出s＝４,则用i和数字组成一个表达式,应填 . 图２Ｇ３１ ３７　 ８􀆰如图２Ｇ３２所示算法,小球从１０米高空落地,以后每次弹起的高度都要比前次减少２０％,经 过多少次后,小球弹起的高度小于０．０１米,请用h和数字组成表达式,应填 . 图２Ｇ３２ ９􀆰如图２Ｇ３３所示算法,计算s＝１/(１∗２)＋１/(２∗３)＋１/(３∗４)＋􀆺＋１/(n∗(n＋１)),则在 横线处用i和数字组成一个表达式,应填 . 图２Ｇ３３ １０􀆰如图２Ｇ３４所示算法,有一串数从第３项开始,每一项都是前两项的和,如１、１、２、３、５、８􀆺 求第２０项的值,则在流程图的横线处用a、b、c组成表达式,应填 . 图２Ｇ３４ 　 ３８　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 １１􀆰如图２Ｇ３５所示算法,有一数列:１、２、２、４、８、３２、２５６􀆺求这个数列的第n(n＞＝３)项,则空 白横线处用a、b、c组成一个表达式,应填 . 图２Ｇ３５ １２􀆰如图２Ｇ３６所示算法,s＝１/２１－１/２２＋１/２３－１/２４＋􀆺求前２０项之和,完成该图,则在横线 处应填 . 图２Ｇ３６ 参考答案 第一章 数据与大数据 巩固练习 1.C 2.C 3.C 4.A 5.D 6.D 7.D 8.D 9.C 10.C 11.B 12.A 13.A 14.B 15.B 16.D 17.C 18.C 19.D 20.C 21. A 22.C 23.B 24.C 25.C 26.D 27.C 28.B 29.C 30.A 31.A 32.D 33.D 34.D 35.D 36.C 37.D 38.C 39.A 40.B 41.C 42.C 43.C 44.C 45.B 46.A 47.A 48.A 49.A 50.A 51. A 52.D 53.A 54.A 55.1/0 56.8000 57.FE07 58.Hit 第二章 算法与程序设计 巩固练习 1.C 2.A 3.B 4.B 5.C 6.24 7.21 8.4 9.A 10.C 11.A 12.B 13.A 14.B 15.A 16.B 17.A 18.C 19.B 20.C 拓展提高 1.55 2.-5 3.s=s+b 4.a=a-b 5.a<-n 6.i>=n $7. -2 8.h=0.8h 9.1/(i*(i+1))10.c=a+b 11.c-a*b 12.t/2 第三章 Python语言程序设计 巩固练习 1.A 2.D 3.A 4.C 5.B 6.B 7.D 8.D 9.D 10.B 11.D 12.A 13. D 14.C 15.D 16.C 17.C 18.A 19.k<-9/i<-k 20.not p 巩固练习 1.A 2.28 3.19/70 4.ej 5.D 6.D 7.3xapple+2×pear-=-100 完整Python程序: for apple in range(0,34): pear-40-apple if 3*apple+2*pear-- 100. print(apple) print(pear)