文档内容
~ 2025年教师资格证·《信息技术》~
数 据 结 构 与 算 法 1 / 5
主讲老师 孙珍珍
粉笔教师教育 粉笔教师第一节 算法基础P252
一、初识算法
（一）算法的概念
Ø是解决问题的方法和遵循的步骤
（二）算法的特征
1.有穷性：有限的时间和步骤后终止
2.确定性：有确定含义，无二义性
3.有效性：可行性，能正确执行
4.输入性：初始数据，可有可无
5.输出性：所求的结果，必有输出书上无
试题巩固
算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。以下说法不正确的是（ ）。
A.算法执行的每一个步骤都必须有确切的定义
B.一个算法在执行有穷步之后必须结束
C.在一个算法中，数据的输入必须要有一个或多个
D.算法中每个计算步骤都可以在有限时间内完成P253
二、问题求解方法
（一）解析法
Ø定义：指用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的
计算来实现问题求解
Ø实例：出租车计费问题。起步价 10 元（三公里内），3 ～ 10 公里之间每公里 2.1 元，超出 10
公里部分每公里 3 元。请根据公里数计算花费金额。P253
二、问题求解方法
（二）穷举法/枚举法/列举法
Ø定义：在已知答案范围的情况下，依次地枚举该范围内所有的取值，并对每个取值进行考查，确
定是否满足条件。
Ø实例：百钱买百鸡问题。用 100 元钱买 100 只鸡，公鸡每只 5 元，母鸡每只 3 元，小鸡 3 只 1
元，要求每种都买，问能买公鸡、母鸡、小鸡各买几只？P254
二、问题求解方法
（三）迭代法/递推法
Ø定义：通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。
Ø实例：猴子吃桃问题。每天吃掉当天的一半多一个，第十天剩一个，问第一天有多少桃。P254
二、问题求解方法
（四）递归法
Ø递归模型组成：递归出口（终止递归调用的条件）、递归体（包含函数自调用的部分）
Ø实例：求阶乘问题。求 n!。P254
二、问题求解方法
（四）递归法
Ø定义：一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。
Ø实例：求阶乘问题。求 n!。
F1 函数体中
F函数 F函数
调用 F 函数
函数体中
F 函数体中
调用F函数
F1函数
调用 F1 函数书上无
试题巩固
（2023 下·初中）一个算法的实现中若包含自我调用的过程，则称该算法为（ ）。
A. 递归算法
B. 解析算法
C. 穷举算法
D. 冒泡算法P255
三、算法的表示
（一）自然语言 【日常用语】
【例1】根据正方形的边长a，计算正方形的周长L和面积S。
ü 第一步：输入正方形的边长a的值。
ü 第二步：利用公式L=4×a计算出周长。
ü 第三步：利用公式S=a×a计算出面积。
ü 第四步：输出周长L和面积S的值。
【例2】输入任意两个数x和y的值，求两数中较大的值max。
ü 第一步：输入x和y的值。
ü 第二步：判断x是否小于等于y。
ü 第三步：如果x小于等于y成立，将y的值赋给max。
ü 第四步：如果x小于等于y不成立，将x的值赋给max。
ü 第五步：输出max的值。P255
三、算法的表示
（一）自然语言 【日常用语】
【例3】求S=1+2+3+…+n的值。P255
（二）伪代码
伪代码：日常用语 + 计算机语言
u
【例】输入任意两个数x和y的值，求两数中较大的值max。
begin
第一步：输入x和y的值。
input x和y
第二步：判断x是否小于等于y。
if x<=y then
第三步：如果x小于等于y成立，将y的值赋给max。
max=y
第四步：如果x小于等于y不成立，将x的值赋给max。
else
第五步：输出max的值。
max=x
output max
end书上无
试题巩固
（2023 下·初高中）元代数学家朱世杰编著的《四元玉鉴》中有这样一道题目：九百九十九文钱，
及时梨果买一千，一十一文梨九个，七枚果子四文钱。问：梨果多少价几何？请用伪代码实现该问题。P256
（三）流程图
1.流程图符号P257
（三）流程图
2.三种基本结构
选择结构
顺序结构
循环结构P257
（三）流程图
【例】根据正方形的边长a，计算正方形的周长L和面积S。用流程图表示。
第一步：输入正方形的边长a的值。
第二步：利用公式L=4×a计算出周长。
第三步：利用公式S=a×a计算出面积。
第四步：输出周长L和面积S的值。P258
（三）流程图
【例】输入任意两个数x和y的值，求两数中较大的值max。用流程图表示。
第一步：输入x和y的值。
第二步：判断x是否小于等于y
第三步：如果x≤y成立，将y赋值给max
第四步：如果x≤y不成立，将x赋值给max
第五步：输出max的值。P259
（三）流程图
【例】求S=1+2+3+…+n的值。用流程图表示。书上无
试题巩固
（2023上·高中）某地考试规定，考试成绩不低于75分为合格，下图是根据成绩判断是否合格的部
分流程图，如果输入的成绩为70，则该流程的执行顺序为（ ）。
A.①→②→③
B.①→②→④
C.①→②→③→④
D.①→②→④→③书上无
试题巩固
（2024 上·初中）某算法流程图如下，若输入 m 和 n 的值为 80 和 48，则
输出 m 的值 是（ ）。
A.8 B.16 C.20 D.32P178
3.应用举例
【例4】用递推法求Fibonacci数列的前20项，每行四项输出。
ØFibonacci数列为：1，1，2，3，5，8，13，21，34，……
项： 1 2 3 4 5 …
值： 1 1 2 3 5 …书上无
试题巩固
（2016下·高中）请画出利用穷举法解决鸡兔同笼问题的流程图。鸡兔同笼问题：今有雉兔同笼，
上有三十五头，下有九十四足，问雉兔各几何？书上无
试题巩固
【参考答案】P261
四、算法的分析
（一）正确性分析
（1）一组普通数据
（2）一组苛刻数据
（3）一切合法数据
（三）空间复杂度
Ø不是代码文件所占的存储空间
Ø是执行时所占用的附加空间数量P262
（二）时间复杂度
Ø不是算法执行所消耗的真正时间，与具体的硬件、编译器或运行环境无关
Ø只依赖问题规模（用n表示），通过算法中基本操作的执行次数来衡量，是一个预估值
Ø在执行次数中去掉常数项、去掉系数、保留最高阶，用大O表示
Ø量级大小：O(1) < O( log n) < O(n)
