2022年高中信息科技的复习提纲算法与程序设计.docx

精选学习资料 - - - - - - - - - 优秀学习资料 欢迎下载高中信息科技（选学模块）的复习提纲算法与程序设计1.1 使用运算机解决问题的一般过程课本 P35 问题解决1用运算机解决问题的步骤：分析问题设运算法编写程序运行程序分析问题：明确要运算机做什么设运算法：查找到解决问题的途径和方法,并把方法步骤化；编写程序：选定编程语言,编制出相应的运算机程序；运行程序：让运算机一步一步地执行算法,以获得问题所需的运算结果；2运算机程序：指示运算机如何去解决问题或完成任务的一组可执行的指令；（明白）运算机科学克劳斯· 沃思指出：算法 +数结构 =程序3程序设计：寻求解决问题的方法,并将其实现步骤编写成运算机可以执行的程序的过程；4指令：用来规定运算机操作的命令；一条指令要求运算机执行一个动作；5指令集：运算机的全部指令组成了运算机的指令集；6典型的运算机指令：输入、输出、数学运算、规律判定、掌握转移指令7一个程序由两部分组成：指令部分和数据部分；指令部分是由一系列指令构成,描述解决这个问题的运算过 程；数据部分是用来储备运算所需的原始数据、运算的中间结果或最终结果；8设计程序需要考虑的两点：1.数据的储备 2.运算的过程（不仅须指出动作,仍须指出动作的次序）1.2 算法的概念（课本 P6）1（明白）算法的由来：由 9 世纪阿拉伯数学家花拉子密的名字；派生而来的,这位数学家一生发觉了很多求 解算术问题的方法,并编写了一本名为复原和化简的规章的书；这本书后来翻译成拉丁文,书名被简化成现在人们所熟识的“代数学 ” ；2 算法的定义：解决问题的详细方法和步骤；即,在有限步骤内求解某一问题所使用的具有精确定义的一系 列操作规章；也可以说是：能够清晰地表达解决问题的方法一步步是“ 怎样做” 的过程；3算法的特点：有穷性：执行步骤有限、能够终止或在合理的时间范畴内完成全部操作；确定性：必需有准确的含义,不能模糊、模棱两可；可行性：每个步骤能够在有限的时间内实际做到；有 0 个或多个输入；有一个或多个输出；1.3 算法的表示方法（课本 P8-9）1 算法的表示方法：自然语言、流程图、伪代码（强调有限和合理间范畴）自然语言：通过文字或数学表达式来描述解决问题的过程；（缺点：简单产生二义性；）主要格式：1 2 3 4 流程图：用直观易懂的、图形来描述算法的方法；最基本、常用的符号有：名师归纳总结 - - - - - - -第 1 页,共 8 页精选学习资料 - - - - - - - - - 优秀学习资料 欢迎下载处理框：框中指出要处理的内容,该框有一个入口和一个出口；输入、输出框：用来表示数据的输入或运算结果的输出；判定框：用来表示条件判定的情形,菱形框的四个顶点中,通常用上方的顶点表示入口,用另外三个顶点中两个来表示出口；所以对于判定框而言是一个入口,两个出口；连接框：用于连接因画不下而断开的流程线；流程线：指出流程掌握方向,即运作的次序；开头、终止符：用来表示算法的开头或终止；一个算法只能有一个开头处,只能有一个终止处；（书上说一个算法只能有一个开头处,但可以有多个终止处；这样的说法是错误的；要更正）流程图表示1.3.2伪代码： 介于自然语言和运算机程序语言之间的一种算法描述,常用方法；也是专业软件开发人员描述算法的一种输入： read（）输出： write （）,print （）赋值：变量与表达式与 2.3.1 数组（变量与常量的概念参见学科要求 P46,课本 P9）常量：指在程序执行过程中事先设置、其值不发生转变的量,即一个详细的数值；变量：指在程序运行过程中,取值可以转变的量,一般用字母表示；在运算机内部变量对应了肯定的储备单元；变量命名的基本规章 1. 只能由字母、数字和下划线三类字符组成,但第一个字符必需是字母；变量名不能为程序设计语言中的 保留字（关键词） ；2. 字母大小写都可以,变量名长度适当；3. 变量名与实际意义相符 变量的特点：变量的值“ 取之不尽,一冲就丢”；变量赋值的格式：变量表达式 将赋值号右边常量的值或变量的值存放到左边变量名对应的储备单元中,成为左边变量的值；名师归纳总结 表达式：指用运算符将常量、变量连接起来有意义的式子；课本P59-60 P59 第 2 页,共 8 页算术表达式：用算术运算符 将常量、变量连接起来有意义的式子；课本- - - - - - -精选学习资料 - - - - - - - - - 优秀学习资料 欢迎下载字符表达式 : 用字符运算符 将常量、变量连接起来有意义的式子；做算术表达式,再做字符表达式）+：只能是两个字符串间连接 如,“ 123” +“ 589” =“ 123589”&：可以是字符串与另一种类型的数据相连接 如,“ 123” &589=“ 123589”（优先级数值大于算术表达式,也就是先（优先级数值大于算术表达式,也就是先做算术表达式,再做字符表达式）如,2× 3 & “23”=623 留意在 VB 中使用 &符号时,肯定要在 &的前面和后面加上空格；关系表达式：用 关系运算符 将常量、变量连接起来有意义的式子；（课本 P59）字符大小比较的实质是其对应以 ASCII 码大大小；因此字母排列在前的小,排列在后的大, 例如 :” a”>”b” ,” m”>”g”. 对于多个字母组成的字符串比较大小,就是第一比较首字母,只有在首字母相同的情形下,才比较第 2 个字母的大小,依此类推；例如：”abc”>”abb”,”dog”<”dogs” ；P33. 规律表达式（课本 P60）留意： VB 中使用算术运算符运算的结果是数值；使用字符运算符运算的结果是字符串；使用关系运算符和规律运算符运算的结果是规律值,即：要么是 False,要么是 True；VB 中常用数学函数（课本P84）ab的表示 exploga*b 和logab的表示log （b）/log （a）重点把握前三个；需要懂得课本P84 中：名师归纳总结 - - - - - - -第 3 页,共 8 页精选学习资料 - - - - - - - - - 优秀学习资料 欢迎下载VB 中常用类型转换函数和字符串函数P85 应用举例函数返回值函数名函数的功能说明Ascx 字符转换为ASCII 码值Asc “A ” 65 Chrx ASCII 码值转换为字符Chr65 “A ”Valx 数字字符串转换为数值Val“ -1234 ” -1234 Strx 数值转换为字符串Str-1234 “-1234 ”Lenx 运算字符串的长度Len “hello ” 5 Midx,n,k 从字符串x 中的第 n 个字符起截取Mid “hello ”,3,3 “llo ”长度为 k 的子串Fixx 截掉数据的小数部分Fix3.1415926 3 计数器：（课本 P10,学科要求P58）在算法执行过程中,用来记录某种大事发生次数的变量；一般用法：在算法预备阶段中,应预置初值为 0；即 c=0 在算法执行过程中,每当指定的大事发生时,计数器计数,即把大事已发生的次数（计数器中的值）加 1 后,结果仍旧送回计数器中；即 c=c+1. 累加器：（课本 P11,学科要求 P59）用来生成并储备数据累加的变量；一般用法：在求和开头前的预备阶段中,应预置初值 0,即 sum=0 在算法执行过程中,每遇到一个符合要求的数据时,把这个数据累加到累加器中,即运算累加器与数据之和,并把结果重新储备到累加器中；即 sum=sum+a 累乘与累加的操作相像； （学科要求 P59）一般用法是：在求积开头前的预备阶段中,应预置初值 1,即 s=1 算法执行过程中,每遇到一个符合要求的数据时,把这个数据累乘到累乘器中,即运算累乘器与数据之积,并把结果重新储备到累乘器中；即 s=s*d. 循环变量： 用于掌握循环的变量；数组（学科要求 P79-80,课本 P27）特别、有用的变量； 规模为 n 的数组变量是由 n 个一般变量组成的,通常把组成数组的变量称为数组元素,一个数组变量中的全部元素拥有一个共同的名称,通过下标（一个从1 n 范畴内的整数值）指出数组变量中的特定元素；实际上,下标指出了一个数组元素在数组变量中的位置；通常用数组变量来储备一批类型、作用相同的数据；1.3.3 算法的执行流程算法中各个处理步骤的执行次序和模式；次序模式（次序结构）特点：执行完一个处理步骤（step1 ）后,次序执行下一个处理步骤step2 ；一个入口,一个出口挑选模式（分支结构）名师归纳总结 - - - - - - -第 4 页,共 8 页精选学习资料 - - - - - - - - - 优秀学习资料 欢迎下载特点：对某种情形e 进行判定,当结果为真时,执行处理步骤step1 ,否就执行处理步骤step2 ； 双分支结构单分支结构VB VB If 条件Then If 条件Then Step1 Step1 即条件为真时的语句即条件为真时的语句Else End If Step2 即条件为假的语句 留意：如结构图中显现的是：当条件为假时执行语End If 句,那么在写 VB 时,需要留意：在这个结构中通过把条件换成相反意思；Els 就已说明白是条件成立 的情形,所以就不需要再对条件进行判定了；·重复模式（循环结构）对某个条件进行判定,当结果为真时,执行一些语句,然后再次判定这个条件,当结果仍为真时,再次执行一些语句,并连续判定条件；总是重复上述过程,直到情形判定的结果为假；当型循环结构：VB: 直到型循环结构VB ：（把结构改成当型VB ：1）先判定, 后执行循环体1）先执行循环体,后循环结构）Do while 循环条件（直到型循环结构语句）循环体（即当循环循环体（第一遍）Do 条件为真时执行）Loop Do while此结构图中循环体循环条件相反意思后续步骤 （即, 当循环（即当循环条件循环体（即当循环条件为假时, 也就是出为假 时执行）口连接着的步骤,写在条件为真时执行）Loop Until此结这里）Loop 构图中 循环条件留意：如结构图中显现的是：当条件为假时执2）循环体执行的循环次数 可能是 0次或多次判定行循环体,那么在写2）循环体执行的循环 次数至少是 1次或多次VB 时,需要把循环条件换成相反意思；每个算法都是这三种模式（结构）的任意组合；掌握循环的几种常用方法（学科要求 P57）1）计数法：一般用于在循环次数确定的情形下；采纳一个变量,通过对该变量的计数来掌握循环的次数；当达到要求的循环次数后适时地退出循环,这样的变量称为循环变量；循环变量的初值、终值和步长的设定与循环次数相关；有时,循环变量仍参与其他运算；通常使用计数器来记录循环体执行次数并掌握循环执行情形；2）标志法：对于不确定循环次数的算法,往往用设置标志性条件的方法来掌握循环；设置标志性条件的方法通常有：以循环体中某个或几个变量满意规定条件作为循环终止的标志；名师归纳总结 - - - - - - -第 5 页,共 8 页精选学习资料 - - - - - - - - - 优秀学习资料 欢迎下载以输入某个特别的数据作为终止循环的标志；循环结构中简单显现的问题（学科要求分析循环结构的算法的运行结果（学科要求P57-58 ）死循环；随便转变循环体中各操作的执行次序；P56）列表法；功能分析法；三种模式的应用；（学科要求 P59-73）基本算法实例2.1 解析算法（课本 P18,学科要求 P79）用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式,并通过表达式的运算来实现问题求解；解析算法最关键的有两步（1）确定使用哪种执行流程来完成；（解析算法的结构：可能是次序结构（课本例 1）,也可能是次序结构和分支结构的组合（例 2）,也可能是次序结构和循环结构的组合（例 3）,也可以是三种结构的任意组合；这完全取决于问题本身；）（2）确定条件与结果之间的表达式；解析法的特点解析法的应用解析法的实现2.2 枚举算法（课本 P22,学科要求 P75-79）采纳一种盲目的搜寻方法,在搜寻结果的过程中,把各种可能的情形都考虑到,并对所得的结果逐一进行判定,过滤掉那些不合要求的,保留那些符合要求的,这种方法叫做枚举算法；在列举过程中,既不能遗漏,也不应当重复；基本结构：枚举算法最关键的有三步（1）确定列举的范畴；（2）确定满意挑选的条件；（3）确定循环掌握方式和列举方式枚举法的特点枚举法的应用枚举法的实现留意：枚举算法的优缺点（学科要求P77）：枚举法充分利用了运算机快速高效的特点,让运算机将全部可能的解无一例外地进行检验,因此列举正确,枚举法具有特别高精确性和全面性；也打算了其局限性- 效率不高； 当算法花费的时间过长时,这样的枚举算法是没有实际意义的；2.4 查找（课本 P34）一种查询数据或信息的技术,其目标是能以比较少的步骤或较短的时间找到所需的对象；在课本中是指以在程序的某个数组变量中储备的一批数据内,查找出特定的一个数据,或者确定在该数组内无这样的数据,来作为查找的目的；查找方法很多,除了次序查找、对分查找,仍有树形查找等等；次序查找（课本 P34,学科要求 P81）用待查关键字（查找键）和已知的数据逐个比较,直到找到与查找键值相等的值,即查找胜利；或查完全部已知数据,而未找到查找键字相等的值,即为查找失败；次序查找的原理次序查找的算法课本 P35+ 课堂上对其修改,学科要求P81 次序查找的实现名师归纳总结 对分查找（课本P35,学科要求 P81）第 6 页,共 8 页- - - - - - -精选学习资料 - - - - - - - - - 优秀学习资料 欢迎下载在有序数据 中,采纳查找键与有序数据内处于中间位置的元素进行比较,假如中间位置上的元素的数值与查找键不同,依据数据元素的有序性,就可以确定应当在数组的前半部分仍是后半部分连续进行查找；在新确定的范畴内,连续按上述方法进行查找,直到获得最终结果；对分查找的原理对分查找的算法课本 P35+ 课堂上对其修改 对分查找的实现2.3 排序（课本 P29,学科要求 P80）把杂乱无章的数据变成有序（递增 /递减）数据的过程；冒泡排序把待排序的 n 个元素的数组看成是垂直堆放的一列数据；从最下面的一个元素起,自下而上比较相邻的两个元素中的数据,将数值最小的数据换到上面的一个元素中；重复这一过程,直处处理完最终两个元素中的数据,称为一遍加工；当第一遍加工完成时,最小的数据已经上升到第一个元素的位置；然后对余下的 n-1 个元素重复上述处理过程,直至最终进行余下两个数据的比较和交换；冒泡排序的原理冒泡排序的算法（课本P32+ 课堂上的整理）冒泡排序的实现【挑选排序】是在参与排序的全部数组元素中找出最小（或最大）数据的元素,使它与第一个元素中的数据相互交换位置,然后再在余下的元素中找出最小（或最大）数据的元素,与其次个元素中的数据相互交换位置,以此类推,直到全部元素成为一个有序的序列；】（仅作参考）程序设计基础VB （Visual Basic：Windows 环境下广泛使用的一种应用程序开发工具,采纳面对对象的程序设计方法；它是一种可视化的程序设计工具,能用它来开发具有图形用户界面的应用程序；面对对象的程序设计语言：Simula67（最早）,Smalltalk （进展史中最重要）,C+ 、C 、VC+、VB、Java 、Dephi（目前流行）等；程序设计1. 变量（包括数组）定义As 变量类型2.Dim 变量名As 变量类型,变量名As 变量类型, 变量名变量类型可参见课本P58 表 3.4 运算符、表达式（详见上文）、随机函数的使用3. 输入 / 输出语句、赋值语句、注释语句输入语句：存入值的变量=inputbox “提示语言” 输出语句： Print 常量 /变量 /表达式（说明：输出两个以上的变量可用逗号分隔）赋值语句：变量 =常量 /变量 /表达式（留意： =两边的类型应一样,否就就应当用转换函数来实现）4. 注释语句：以开头的一段说明文字；5. 分支语句、循环语句（详见上文）书上的分支语句描述与我们平常写的有所不同,可自学一下,但是在考试书写时,建议采纳平常写的那种格式,这样名师归纳总结 - - - - - - -第 7 页,共 8 页精选学习资料 - - - - - - - - - 优秀学习资料 欢迎下载结构清晰,且不简单错；6.循环语句不仅是do while 语句；仍有For 语句；详细见PPT PPT） 解析算法、枚举算法、查找及排序的程序实现（详见下发的补充：程序代码的书写名师归纳总结 通常一条语句占一行；要在一行中写多条语句,需要在每条语句之间用冒号进行分隔；各关键词之间、 关键词与变量名第 8 页,共 8 页之间、常量名之间要用空格隔开；（课本 P65）- - - - - - -