文档内容
2023下 粉笔 教资
《 信 息技术》
数 据 结 构与算法 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
（四）递归法
➢定义：一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。
F1 函数体中
F函数 F函数
调用 F 函数
函数体中
F 函数体中
调用F函数
F1函数
调用 F1 函数二、问题求解方法 P254
（四）递归法
➢定义：一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。
➢实例：求阶乘问题。求 n!。
递归出口：已知值
递归体：递归方式
分解 递推书上无
1.破解密码程序最常用的方法是按照一定的规则生成所有可能的密码去尝试，直到得到正确
的密码。该程序使用的算法是（ ）。
A.穷举法 B.递推法 C.递归法 D.解析法
2.“从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲什么呢？从前有座山，
山上有座庙......”这个故事蕴含了程序设计中的一种算法，这种算法是（ ）。
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的值。
第一步：输入n的值。
第二步：引入变量i，其初始值为1。
S的初始值为0。
第三步：将S加上i的结果赋给S。
第四步：i的值加1。
第五步：判断i的值是否大于n，
如果大于n，则执行第六步，
否则回到第三步继续往下执行。
第六步：输出S的值。三、算法的表示 P256
（二）伪代码 【日常用语 + 计算机语言】
【例】输入任意两个数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（三）流程图 P256
1.流程图符号（三）流程图 P257
2.三种基本结构
选择结构
顺序结构
循环结构（三）流程图 P258
【例】根据正方形的边长a，计算正方形的周长L和面积S。用流程图表示。
第一步：输入正方形的边长a的值。
第二步：利用公式L=4×a计算出周长。
第三步：利用公式S=a×a计算出面积。
第四步：输出周长L和面积S的值。（三）流程图 P259
【例】输入任意两个数x和y的值，求两数中较大的值max。用流程图表示。
第一步：输入x和y的值。
第二步：判断x是否小于等于y
第三步：如果x≤y成立，将y赋值给max
第四步：如果x≤y不成立，将x赋值给max
第五步：输出max的值。（三）流程图 P260
【例】求S=1+2+3+…+n的值。用流程图表示。3.应用举例 P278
【例4】用递推法求Fibonacci数列的前20项，每行四项输出。
➢Fibonacci数列为：1，1，2，3，5，8，13，21，34，……书上无
（2023上·初中）小刚设计的“机器人走棋盘”算法，算法流程图如下图（a）所示，机器人
在下图（b）中棋盘的“A”位置出发，沿箭头方向行走，执行完算法后将到达的位置是
（ ）。
A.①位置
B.②位置
C.③位置
D.④位置
（a） （b）书上无
（2022 上·高中）某算法的部分流程如图所示。执行循环部分流程的执行次数和a的值分别是
（ ）。
A.4 9
B.4 11
C.5 9
D.5 11书上无
（2021 下· 初中）将二进制数(11111) 转化为十进制数的流程图如下图所示，判断框内应填
2
入的是（ ）。
A. i>4
B. i<=4
C. i>5
D. i<=5书上无
（2016下·高中）请画出利用穷举法解决鸡兔同笼问题的流程图。鸡兔同笼问题：今有雉兔
同笼，上有三十五头，下有九十四足，问雉兔各几何？书上无
【参考答案】下
节
内
容
