高中信息科技(选学模块)的复习提纲 算法与程序设计

高中信息科技(选学模块)的复习提纲 算法与程序设计
1.1◇使用计算机解决问题的一般过程(课本 P3~5)
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

处理框

:框中指出要处理的内容,该框有一个入口和一个出口。

输入、输出框

:用来表示数据的输入或计算结果的输出。

判断框

:用来表示条件判断的情况,菱形框的四个顶点中,通常用上方的顶点表示入口,用另外

三个顶点中两个来表示出口。所以对于判断框而言是一个入口,两个出口。

连接框 :用于连接因画不下而断开的流程线。

流程线 :指出流程控制方向,即运作的次序。

开始、结束符

:用来表示算法的开始或结束。一个算法只能有一个开始处,只能有一个结束处。

(书上说一个算法只能有一个开始处,但可以有多个结束处。这样的说法是错误的。要更正)

☆流程图表示

? 伪代码:介于自然语言和计算机程序语言之间的一种算法描述,也是专业软件开发人员描述算法的一种 常用方法。

输入:read() 输出:write(),print() 赋值:

1.3.2☆变量与表达式与 2.3.1 数组
(变量与常量的概念参见学科要求 P46,课本 P9) 常量:指在程序执行过程中事先设置、其值不发生改变的量,即一个具体的数值。 变量:指在程序运行过程中,取值可以改变的量,一般用字母表示。在计算机内部变量对应了一定的存储单元。 变量命名的基本规则
1.只能由字母、数字和下划线三类字符组成,但第一个字符必须是字母。变量名不能为程序设计语言中的 保留字(关键词)。
2.字母大小写都可以,变量名长度适当。 3.变量名与实际意义相符 变量的特点:变量的值“取之不尽,一冲就丢”。 变量赋值的格式:变量←表达式
将赋值号右边常量的值或变量的值存放到左边变量名对应的存储单元中,成为左边变量的值。 表达式:指用运算符将常量、变量连接起来有意义的式子。课本 P59-60 ? 算术表达式:用算术运算符将常量、变量连接起来有意义的式子。课本P59

2

? 字符表达式:用字符运算符将常量、变量连接起来有意义的式子。(优先级数值大于算术表达式,也就是先 做算术表达式,再做字符表达式)
+:只能是两个字符串间连接 如,“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)
重点掌握前三个。需要理解课本 P84 中: a b 的表示 exp(log(a)*b) 和 log a b 的表示 log(b)/log(a)
3

? VB 中常用类型转换函数和 字符串函数 P85

函数名

函数的功能说明

应用举例

Asc(x)

字符转换为 ASCII 码值

Asc(“A”)

Chr(x)

ASCII 码值转换为字符

Chr(65)

Val(x)

数字字符串转换为数值

Val(“-1234”)

Str(x)

数值转换为字符串

Str(-1234)

Len(x)

计算字符串的长度

Len(“hello”)

Mid(x,n,k)

从字符串 x 中的第 n 个字符起截取 长度为 k 的子串

Mid(“hello”,3,3)

Fix(x)

截掉数据的小数部分

Fix(3.1415926)

函数返回值 65 “A” -1234 “-1234” 5 “llo” 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

? 选择模式(分支结构) 特点: 对某种情况 e 进行判断,当结果为真时,执行处理步骤 step1,否则执行处理步骤 step2。

双分支结构

单分支结构

VB If 条件 Then
Step1 (即条件为真时的语句)
Else
Step2 (即条件为假的语句)
End If 注意:在这个结构中通过 Els 就已说明了是条件成立 的情况,所以就不需要再 对条件进行判断了。

VB If 条件 Then
Step1 (即条件为真时的语句) End If
注意:若结构图中出现的 是:当条件为假时执行语 句,那么在写 VB 时,需要 把条件换成相反意思。

· 重复模式(循环结构)
对某个条件进行判断,当结果为真时,执行一些语句,然后再次判断这个条件,当结果仍为真时,再次 执行一些语句,并继续判断条件。总是重复上述过程,直到情况判断的结果为假。

当型循环结构:

直到型循环结构

VB:
Do while 循环条件
循环体(即当循环 条件为真时执行)
Loop
后续步骤(即,当循环 条件为假时,也就是出 口连接着的步骤,写在 这里)

VB:(把结构改成当型 循环结构)

VB:
(直到型循环结 构语句)

循环体(第一遍)

Do

Do while 此结构图中 循环条件相反意思
循环体(即当循环 条件为真时执行)
Loop

循环体
(即当循环条件 为假时执行)
Loop Until 此结 构图中循环条件

1)先判断,后执行循环体
2)循环体执行的循环次数 可能是0次或多次

注意:若结构图中出现 的是:当条件为假时执 行循环体,那么在写 VB时,需要把循环条 件换成相反意思。

1)先执行循环体,后 判断
2)循环体执行的循环 次数至少是1次或多次

每个算法都是这三种模式(结构)的任意组合。
控制循环的几种常用方法(学科要求P57) 1)计数法:一般用于在循环次数确定的情况下。采用一个变量,通过对该变量的计数来控制循环的次数。 当达到要求的循环次数后适时地退出循环,这样的变量称为循环变量。循环变量的初值、终值和步长的设 定与循环次数相关。有时,循环变量还参与其他运算。
通常使用计数器来记录循环体执行次数并控制循环执行情况。 2)标志法:对于不确定循环次数的算法,往往用设置标志性条件的方法来控制循环。
5

? 设置标志性条件的方法通常有:以循环体中某个或几个变量满足规定条件作为循环结束的标志; ? 以输入某个特殊的数据作为结束循环的标志。
循环结构中容易出现的问题(学科要求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) ☆顺序查找的实现
6

? 对分查找(课本 P35,学科要求 P81)
在有序数据中,采用查找键与有序数据内处于中间位置的元素进行比较,如果中间位置上的元素的数值与查找 键不同,根据数据元素的有序性,就可以确定应该在数组的前半部分还是后半部分继续进行查找;在新确定的 范围内,继续按上述方法进行查找,直到获得最终结果。 ☆对分查找的原理 ☆对分查找的算法(课本 P35+课堂上对其修改) ☆对分查找的实现
2.3 排序(课本 P29,学科要求 P80)
把杂乱无章的数据变成有序(递增/递减)数据的过程。
? 冒泡排序
把待排序的 n 个元素的数组看成是垂直堆放的一列数据。 从最下面的一个元素起,自下而上比较相邻的两个元素中的数据,将数值最小的数据换到上面的一个元素 中。重复这一过程,直到处理完最后两个元素中的数据,称为一遍加工。 当第一遍加工完成时,最小的数据已经上升到第一个元素的位置。然后对余下的 n-1 个元素重复上述处理 过程,直至最后进行余下两个数据的比较和交换。 ☆冒泡排序的原理 ☆冒泡排序的算法(课本 P32+课堂上的整理) ☆冒泡排序的实现
? 【选择排序】
是在参加排序的所有数组元素中找出最小(或最大)数据的元素,使它与第一个元素中的数据相互交换位 置,然后再在余下的元素中找出最小(或最大)数据的元素,与第二个元素中的数据相互交换位置,以此类推, 直到所有元素成为一个有序的序列。】(仅作参考)
程序设计基础
VB(Visual Basic):Windows 环境下广泛使用的一种应用程序开发工具,采用面向对象的程序设计方法。它是 一种可视化的程序设计工具,能用它来开发具有图形用户界面的应用程序。 面向对象的程序设计语言:Simula67(最早),Smalltalk(发展史中最重要),C++、C﹟、VC++、VB、Java、Dephi (目前流行)等。
程序设计
1. ◇变量(包括数组)定义 Dim 变量名 As 变量类型,变量名 As 变量类型,……变量名 As 变量类型 变量类型可参见课本 P58 表 3.4
2. ☆运算符、表达式(详见上文)、随机函数的使用
3. ☆输入/输出语句、赋值语句、注释语句
输入语句:存入值的变量=inputbox(“提示语言”) 输出语句:Print 常量/变量/表达式
(说明:输出两个以上的变量可用逗号分隔) 赋值语句:变量=常量/变量/表达式
(注意:=两边的类型应一致,否则就应该用转换函数来实现) 4. 注释语句:
以’开头的一段说明文字。
7

5. ☆分支语句、循环语句(详见上文)
书上的分支语句描述与我们平时写的有所不同,可自学一下,但是在考试书写时,建议采用平时写的那种格式,这样 结构清楚,且不容易错。
循环语句不仅是 do while 语句;还有 For 语句;具体见 PPT
6. ★解析算法、枚举算法、查找及排序的程序实现(详见下发的 PPT) 补充:程序代码的书写
通常一条语句占一行。要在一行中写多条语句,需要在每条语句之间用冒号进行分隔。各关键词之间、关键词与变量名 之间、常量名之间要用空格隔开。(课本 P65)
8


相关文档

高中信息科技选学模块:算法与程序设计资料整理
高中信息科技 选学模块 复习
信息科技复习提纲(算法与程序设计)知识点
算法与程序设计-浙江省高中信息科技复习要点
信息科技复习知识点参考——统一模块和选学模块
高中信息科技《设计与创作》选学模块模拟考题
2009年上海市信息科技学业高中学业水平等级考试(选学模块——设计与创作)
上海市信息科技会考学业水平考试选学模块总复习
福建省高中基础会考信息技术-模块《算法与程序设计》
07年6月份-福建省高中基础会考信息技术-模块《算法与程序设计》
学霸百科
电脑版 | 学霸百科