高中信息科技选学模块:算法与程序设计资料整理

选学模块:算法与程序设计资料整理
算法的概念:算法是在有限步骤内求解某一问题时所使用的具有精确定义的一系列操作规则。
注:同一个问题可以有多种不同的算法予以解决
开始 开始 i?某个正整数 sum?0

有穷性(步骤是有限的) 确定性(步骤是无二义性限的)

i? 1 sum?0

算 法 基 础

算法的特征

能行性(步骤是可行的) 有 0 个或多个输入(算法可以没有输入) 有 1 个或多个输出(算法至少有 1 个输入) 自然语言:文字语言+必要的数学符号 伪代码:简化了的编程语言

sum?sum+i i?i-1

i<=1000 Y

N

sum?sum+i i?i+1

i<=1000 Y

N

输出sum
结束

输出sum
结束

此算法不符合“有穷性”
开始 x? 2 x?x / (x-2)

此算法不符合“确定性”
开始 x? 2 x?x+2 x?x+2 结束

算法的 描述方法
开始

变成

圆角矩形——开始、结束框 平行四边形——输入、输出框 矩形——处理框

输出x
结束

x?2
x?x+2

流程图 变成

菱形——判断框 圆形——连接框 有向线段——流程线
1

此算法不符合“能行性”
注:菱形框(判断框) 有一个入口, 两个出口

此算法没有输出”

输出sum
结束

一个入口

此算法输入输出框错 误,并不符合“能行性”

两个出口

常量:是指在程序执行过程中事先设置的、其值不发生改变的量 概念:变量是用来存储程序中要用到的数据,实质是内存中的某一单元。 变量
算法描述中 语句的构成
命名规则 变量名称:只能由字母、数字和下划线组成,且必须由字母开头。

概念:数组是一种特殊的变量、其存储的是一些类型相同的数据,且占用连续的内存单元 数组

算法的 (续) 基本模式 (结构)
见下一页

算 法 基 础

d
数组名

5
d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] d[9] d[10] 数组元素值 数组元素名 数组元素

数组元素下标 此数组规模=10

算术运算:^(乘方) ;*(乘) ;/(除) ;\(求商) ;
mod(求余数) ;+(加) ;-(减) ;

运算优先级 ^(乘方) ; *(乘) ;/(除) ; \(求商) ; mod(求余数) ; +(加) ;-(减) ;





运算符

常用函数: 若 x=-3.14 则 abs(x)=3.14 abs(-x)=3.14 sqr(x)无意义 sqr(-x)=3.14 int(x)=-4 int(-x)=3

关系运算:>,<,>= ,<= ,=, <> 运算优先级:相同 逻辑运算:not(非);and(与);or(或); 运算优先级:not(非)>and(与)>or(或) 不同运算之间的优先级:算术运算>关系运算>逻辑运算
abs(x)——绝对值函数:例:a=abs(x) a 的值为 x 的绝对值 a 的值为小于等于 x 的最大整数

常用函数

sqr(x)——算术平方根函数:例:a=sqr(x) a 的值为 x 的算术平方根 int(x)——取整函数:例:a=int(x)

表达式:由若干个常量,变量(数组) ,运算符以及常用函数等组成的式子。
例:a+3;a+b<c or b+c>a and c+a>b;(-a[2]+srq(a[2]^2-4*a[1]*[3]))/(2*a[1])
2

顺序模式(结构) 一个入口
算法描述中 语句的构成
步骤1 步骤2 步骤3

交换两个变量的值

输出一个三位正整 数的各位数字之和
输入n a?n \ 100 b?n \ 10 mod 10

典 型 例 题

输入a,b

输入a,b a?a+b b?a-b a?a-b 输出a,b

t?a a?b b?t
输出a,b

c?n mod 10 s?a+b+c 输出s

算法的 (续) 基本模式 (结构)
顺序模式(结构) 选择模式(结构) 循环模式(结构)
注:任何一个算法, 必定包含顺序模式

算 法 基 础

见上一页

一个出口

选择模式(结构)——选择模式嵌套的相当灵活 一个入口
Y
步骤A 选择条件 判断条件 N 步骤B
选择条件 Y 步骤A N

输出一个数的绝对值

输出三个数中的最大数
输入a,b,c

典 型 例 题
单分支选择模式
Y

输入x

输入x

Y

x>=0?

N

x<0?
Y

N

a>b?

N
max?b

max?a

a?x
输出a

a?-x

x?-x
输出x

c>max? N Y
max?c 输出max

双分支选择模式

一个出口

一个入口 循环模式(结构)
“当型”循环模式
先 判断循环条件 若成立: 再 执行循环体 后 返回循环条件 若不成立:结束循环模式 执行之后的步骤 注:循环体有可能一次都不执行

循环初始化 循环条件

循环初始化
N

“直到型”循环模式
先 执行循环体 再 判断循环条件 若不成立:返回继续循环体 若成立: 结束循环模式 执行之后的步骤 注:循环体至少执行一次

Y
循环体

循环体

N
一个出口

循环条件

Y

“当型”循环模式 “直到型”循环模式
3

循环模式(结构)——典型例题
算法描述中 语句的构成
i?1 sum?0 i<=100 Y sum?sum+i i?i+1 N
图1
i?1 sum?sum+i i?i+1 N
i>100

输入一批学生的成绩,输出这些成绩 的平均分。 (当输入-1 时表示结束)
图3

图2
sum?0

sum?0 count?0
输入score

count?0 sum?0

图4

算 法 基 础

见第二页

score<>-1
sum?sum+score count?count+1
输入score

N

输入score

Y

sum?sum+score count?count+1

算法的 基本模式 (结构)
选择模式(结构) 循环模式(结构)

输出sum

Y 输出sum

N

score = -1

求 1+2+3+??+100 的和

(续)顺序模式(结构)

Y count=0 N
输出“数据异常” 输出sum/count

Y Y count = 1 N
输出 输出“数据异常” (sum+1)/(count-1)

Y

特殊变量 1:累加器(图 1 图 2 图 3 图 4 中的变量 sum) 作用:存储一些数据之和的变量 用法:1、置初值 sum?0 2、在循环体中执行累加操作 sum?sum+num
特殊变量 2:计数器(图 3 图 4 中的变量 count)

特殊变量 3:累乘器 作用:存储一些数据之积的变量 用法:1、置初值 sum?1 2、在循环体中执行累乘操作 sum?sum*num

作用:记录某事件发生的次数 用法:1、置初值 count?0 2、记录某事件发生时,在循环体中执行 count?count+1
4

循环模式(结构) 计数法:用某(些)计数器变量来控制循环。 (循环体执行次数已知) 控制循环的方法 标志法:用某(些)变量的值是否满足规定条件来控制循环。 (循环体执行次数未知)
(上页中图 3 图 4 即用标志法来控制循环)

概念:是指根据题目中给出的已知条件,找出已知条件与要求结果之间关系的数学表达式,并通过数学表达式的
计算实现问题的求解的方法

解析算法

一般设计步骤:1、是分析给出的已知条件(包含隐含条件) ; 2、明确求什么
3、找出关系表达式(有可能会涉及其他学科的知识如数学,物理等) 。

特点:没有特定的特征,可能是顺序模式,也有可能是选择模式或循环模式,甚至是几种模式的组合,完全取决于问题本身。 例题:见教材 P18~P21【例 1】计算并联电阻的总阻值(一) 【例 2】一元二次方程求解【例 3】计算并联电阻的总阻值(二)

算 法 实 例
枚举算法

概念:根据所需解决问题的条件,把该问题所有可能的解,一一列举出来,并逐个检验出问题真正解的方法。 一般设计步骤:1、确定枚举的范围。列举所有可能的结果,不能遗漏,也不能重复。
2、明确检验的条件。分析题目,明确检验的对象,检验的条件以及检验后需执行的相关操作 3、确定循环控制方式与列举方式。计数循环还是标志循环?是否可以借助循环控制变量进行列举

特点:一般采用循环模式嵌套选择模式的结构,也可以是
多重循环模式+选择模式嵌套的结构来设计枚举算法 注:当枚举算法所花费的时间过长时(几年十几年甚 至更长) ,这样的枚举算法是没有实际意义的

count?0 j?0 j<100 N
Y

教材 P23 例 5

i?2 i<=1000 Y f?true j?2
j<=i-1 and f=true

教材 P25 例 6
N

n?10047+j×100 Y count?count+1 输出n j?j+1 输出count
n mod 57=0 or n mod 67=0

N

N

例题:见教材 P22~P21
【例 4】寻找 37 的倍数 【例 5】一份单据中被涂抹的数字的推算 【例 6】1000 以内素数的推算

Y i mod j=0 N Y f?false j?j+1 f=true Y i?i+1 N

输出i

5

概念:排序是对一批量地数据按照一定的顺序(从大到小(降序)或从小到大(升序) )进行排列的一种操作。

算 法 实 例

排序算法

排序方法——冒泡排序:理解冒泡排序思想(略) 概念:查找是查询数据或信息的技术,其目标为以较少的步骤或较短的时间找到所需的对象。
序是对一批量地数据按照一定的顺序(从大到小(降序)或从小到大(升序) )进行排列的一种操作。 思想:理解顺序查找思想(略)

(续) 查找算法 查找方法

顺序查找 特点:原数据无需排序,效率低 思想:理解顺序查找思想(略) 对分查找 特点:原数据需排序(升序或降序) ,效率高

输入 n

开始

开始

i?1 N i<=n-1 Y j? n N j>=i+1 Y N a[j]<a[j-1] Y a[j]??a[j-1] j?j-1 i?i+1

输入 key i?1

输入 key i?1 j?n

Y Y a[i]=key 输出 i N i?i+1

i<=n

N

输出 “无此数据”

Y m?(i+j)\2

i<=j

Y

输出 “无此数据”

a[m]=key Y 输出 m N N Y 结束 a[m]<key i?m+1 j?m-1

结束
冒泡排序参考流程图 顺序查找参考流程图
6

对分查找参考流程图

变量(数组)定义

变量定义: Dim 变量名称 As 变量类型 数组定义: Dim 数组名(下标的起始值 to 下标的终止值) As 变量类型

整型(整数) Integer (-32768—32767) 长整型(整数) Long (-2.1×109—-2.1×109)

程 序 设 计 实 现

变量类型

实型(实数) Single,double 字符串型(文本) String 布尔型(‘真’或‘假’) Boolean

输入语句:InputBox 输出语句:Print

用法:单个变量名 = InputBox(“提示信息”); 例:f = InputBox(“请输入摄氏温度 f:”)

用法:Print 变量名 1,变量名 2,?? 例:Print c 例:Print a,b 注释语句:在语句前加单引号(’),之后的语句起解释作用,不起任何作用 双分支选择模式流程图与 VB 代码 If 选择条件 then
Y
步骤A 选择条件 判断条件 N 步骤B

单分支选择模式流程图与 VB 代码
N

步骤 A Else 步骤 B End If

选择条件 Y 步骤A

If 选择条件 then 步骤 A End If

7

循环初始化 循环条件

VB 代码
N

循环初始化 Do While 循环条件 循环体 Loop

例 : 求 斐 波 那 契 数 列 (1,1,2,3,5,8,13,21, ??) 的第 n 项的 值,以及前 n 项的和。 (n 为<=44 的正 整数,输入得到。用数组变量完成) 。
VB 代码(包括变量的声明,输入输出) :
开始 a[1]?1 a[2]?1 输入 n Y i? 3 sum?a[1]+a[2] i<=n Y a[i]?a[i-1]+a[i-2] sum?sum+a[i] i?i+1 N n>2 N Y 输出 a[2] 输出 a[1]+a[2] n=2 N 输出 a[1] 输出 a[1]

Y
循环体

“当型”循环模式

VB 代码
循环初始化 循环体
循环初始化 Do 循环体 Loop Until 循环条件

N

循环条件

Y
“直到型”循环模式

Dim a(1 to 44) as Long Dim n as Integer Dim i as Integer Dim sum as Long a(1)=1 a(2)=1 n=InputBox(“请输入 n”) If n>2 then i=3 sum=a(1)+a(2) Do while i<=n a(i)=a(i-1)+a(i-3) sum=sum+a(i) i=i+1 Loop Print a(i-1),sum Else If n=2 then Print a(2),a(1)+a(2) Else Print a(1),a(1) End If End If 8

输出 a[i-1] 输出 sum 结束


相关文档

高中信息科技(选学模块)的复习提纲 算法与程序设计
选学模块算法与程序设计(知识整理)
高中信息科技《设计与创作》选学模块模拟考题
2009年上海市信息科技学业高中学业水平等级考试(选学模块——设计与创作)
高中信息技术会考资料整理
算法与程序设计-浙江省高中信息科技复习要点
07年6月份-福建省高中基础会考信息技术-模块《算法与程序设计》
福建省高中基础会考信息技术-模块《算法与程序设计》
高中信息技术选修模块《算法与程序设计》教学实践研究
07年6月份带答案-福建省高中基础会考信息技术-模块《算法与程序设计》
电脑版