资源简介

(共25张PPT)
一、 算法的概念及描述
信息技术 必修1 数据与计算
算法与问题解决
第二章
知识过关
1. 算法的概念
广义地讲,“算法”指的是解决问题或完成任务的一系列步骤。在计算机科学领域内,“算法”指的是用计算机解决问题的步骤,是为了解决问题而需要让计算机有序执行的无歧义的、有限步骤的集合。
2. 算法的特征
特征 含义
有穷性 一个算法的处理步骤必须是有限的
可行性 一个算法中的每一步操作与要求都应该是算法执行者(人或者机器)可以实施的,同时是在现实环境中能做到并且能在有限的时间内完成的
确定性 算法中对于每个步骤的执行的描述必须是明确的
0个或多个输入 初始数据可以从外界输入,也可包含在算法中
1个或多个输出 算法必须有问题求解的结果,包含至少一个输出
3. 算法的要素
要素 含义
数据 用算法解决问题时,必须明确参与运算的初始数据、运算时产生的中间数据以及代表问题解决的结果数据
运算 对数据进行运算时,必须明确每一步的运算是什么、对哪些数据进行运算等
控制转移 在算法执行过程中,有时需要根据数据或运算结果的特点进行不同的处理,这时就需要运用控制转移来执行不同的操作。比如,控制程序实现分支结构或者循环结构
4. 算法的描述
(1)常见的算法描述方式有自然语言、流程图、伪代码和计算机程序设计语言等。
描述方式 含义
自然语言 指人们在日常生活中交流时使用的语言。用自然语言描述算法的方式通俗易懂,但缺乏直观性和简洁性,容易产生歧义
流程图 流程图用一些图形符号表示规定的操作,并用带箭头的流程线连接这些图形符号,表示操作进行的方向。用流程图描述算法的方式结构清晰,寓意明确
伪代码 指一种比较直观简洁的、符号接近计算机程序代码的算法描述方式,风格类似于计算机程序设计语言,但又不是真正的可以被计算机理解的代码
计算机程序 设计语言 为了让计算机帮助人们真正解决问题,需要将算法用计算机能够理解的语言来描述,这种语言称为计算机程序设计语言
(2)常用的流程图基本图形及其功能
图形 名称 功能
开始/结束符 表示算法的开始或结束
输入/输出框 表示算法中数据的输入或输出
处理框 表示算法中数据的运算处理
判断框 表示算法中的条件判断
流程线 表示算法中的流向
连接点 表示算法中的转接
(3)伪代码的语法约定
①条件判断语句
格式1:If条件then
　　(语句序列1)
Else
　　(语句序列2)
格式2:If条件then
　　(语句序列1)
②循环语句
格式:while条件
　　　　(循环体)
典例精选
【例1】 下列关于算法的说法,错.误.的是(　　)
A. 算法是解决问题的有序步骤
B. 算法有输入、输出、确定性、可行性、有穷性等基本特征
C. 解决同一问题的算法只有一种
D. 描述算法的方法主要有自然语言描述法、流程图描述法、伪代码法
【解析】 本题主要考查算法的描述。算法是解决问题的有序步骤;算法有输入、输出、确定性、可行性、有穷性等基本特征;解决同一问题的算法有多种;描述算法的方法主要有自然语言描述法、流程图描述法、伪代码描述法。
C
【例2】 在用万能求根公式求一元二次方程的解的算法中,在方程不存在实数解的情况
下,也要求输出“方程无实数根”。这体现了算法特征中的(　　)
A. 有穷性 B. 可行性
C. 有0个或多个输入 D. 有1个或多个输出
【解析】 本题考查算法的特征。分析题意可知,求一元二次方程实数根的算法,在方程无实根时也要求有输出,这与算法“有输出”的特征吻合,即算法一定要有结果输出。
D
【例3】 计算机编程解决“斐波那契数列(每一项都是前两项之和)”问题的过程由以下4个步骤组成:
①用Python中的循环结构编写程序
②调试运行程序,发现错误并进行修正
③设计算法:设计输入、处理、输出等一系列算法
④抽象与建模:用数学符号F(0)＝F(1)＝1,F(n)＝F(n－1)＋F(n－2)(n≥2,n∈N)描述解决问题的计算模型的正确顺序是(　　)
A.①②③④ B.③④①②
C.④③②① D.④③①②
【解析】 本题考查算法的表示。先抽象与建模,再设计算法,接着编写程序,最后调试运行程序。
D
【例4】 某算法用伪代码描述如下。
输入两个正整数x,y
if x＜y then
　　z←(y-x)/2
Else
　　z←(x-y)/2
输出z
关于上述算法,下列说法中正确的是(　　)
A. 不符合“可行性”特征 B. 无法用流程图描述
C. 运用了循环结构的控制转移 D. z为正整数x与y差值的一半
【解析】 本题考查算法及其描述。题中用伪代码来描述算法,其每一个步骤都有明确的作用和含义,符合“可行性”等算法特征。本题的算法可以用自然语言、流程图等方式来描述。由伪代码可知,该算法运用了分支结构的控制转移。为了保证x、y的差为正,需要对x与y的大小关系进行判断,z为正整数x与y差值的一半,D正确。
D
【例5】 “梅森素数”指的是符合条件m＝2p－1的数,其中指数p与整数m均为素数。小李想找出10000以内所有“梅森素数”,设计算法过程如下:
①设计核心算法:如何判断素数
②调试运行程序,重点检测边界条件
③借助Python语言,通过具体编程实现
④将问题抽象成条件的判断与素数的判断,并完成建模
下列选项中,解决该问题的过程的正确顺序是(　　)
A. ①②③④ B. ②①④③
C. ④①③② D. ①④②③
【解析】 本题考查算法的表示。抽象与建模是第一步,设计算法是第二步,计算机编程实现是第三步,调试程序是最后一步。
C
自我检测
1. 下列关于算法的说法,正确的是(　　)
A. 算法解决问题的一般过程依次为“设计算法—抽象与建模—描述算法”
B. 数据、运算和控制转移是算法的三大要素
C. 任何算法都必须有至少一个输入数据和一个输出数据
D. 同一种算法只能用一种表示方法
【解析】 本题主要考查算法的描述。算法解决问题的一般过程依次为“抽象与建模—设计算法—描述算法”;数据、运算和控制转移是算法的三大要素;算法可以没有输入,但必须有输出;同一种算法能用多种表示方法,如伪代码、算法流程图等。
B
2. 编程求解问题时,要求输出“所有的偶数”。这一要求违.反.了算法的特征中的(　　)
A. 有输出 B. 确定性
C. 有穷性 D. 可行性
【解析】 本题考查算法的特征。由于不可能输出所有的偶数(无穷多个),C正确。
C
3. 下列关于算法描述的说法,错.误.的是(　　)
A. 流程图用特定的简单图形符号表示规定操作,结构清晰、寓意明确
B. 用自然语言描述算法通俗易懂,但容易出现歧义,且表述烦琐
C. 伪代码的语法接近计算机程序语言,描述简练,且能够被计算机执行
D. 用计算机程序设计语言描述的算法,可以被计算机理解和执行
【解析】 伪代码不能被计算机执行。伪代码指的是一种比较直观简洁的、符号接近计算机程序代码的算法描述方式,其风格很像计算机程序设计语言,但又不是真正的可以被计算机理解的代码。
C
4. 下面流程图所表述的算法,违.反.的算法特征是(　　)
A. 该算法没有数据输入
B. 该算法没有数据输出
C. 不符合算法的有穷性特征
D. 不符合算法的确定性特征
【解析】 本题主要考查算法的特征。分析流程图可知,该算法会陷入“死循环”,不符合算法的有穷性特征。
C
5. 下列问题中,不.能.用算法来描述的是(　　)
A. 已知圆锥的底面半径和高,求表面积和体积
B. 求方程y＝2x＋1的所有整数解
C. 计算某班同学的英语平均分
D. 求一元二次方程ax2＋bx＋c＝0(a≠0)的两个实数解
【解析】 本题主要考查算法的描述。方程y＝2x＋1的所有整数解有无数个,不满足算法的有穷性特征,因此不能用算法来描述。
B
6.下列选项中,可以用于描述算法的有(　　)
①中文　②流程图　③伪代码　④计算机程序设计语言　⑤英文
A. ①④⑤ B. ②③⑤
C. ①②③④ D. ①②③④⑤
【解析】 算法的描述方式有自然语言、流程图、伪代码和计算机程序设计语言。
D
7. 费马平方和定理:质数能表示为两个平方数之和的充分必要条件是该质数被4除余1,如13＝22＋32。现通过编程来验证3和99之间所有质数是否符合费马平方和定理。
解决该问题的算法步骤如下:
①列举a在[1,]范围内的所有整数,计算对应的b,即b＝。
②变量n表示3和99之间的数,变量a和b的平方表示两个平方数,即n＝a2＋ b2。
③若根据质数n除以4余1能够找到整数b,则符合定理。
④判断n是否为质数。
⑤若根据质数n除以4余3无法找到整数b,则符合定理。
正确的算法步骤顺序是(　　)
A. ②④①③⑤ B. ②④⑤①③
C. ②①④③⑤ D. ②①④⑤③
A
【解析】 本题主要考查利用算法解决问题。由选项可知,首先是②变量n表示3和99之间的数,变量a和b的平方表示两个平方数,即n＝ a2＋ b2;根据题干可知,接下来判断n是否为质数,即④判断n是否为质数;③⑤没有先后顺序,A正确。
8. 某算法用伪代码描述如下:
输入一个自然数a
if a*2＞10 then
　　a←10
else
　　a←a+1
输出a
关于上述算法,下列说法中错.误.的是(　　)
A. 符合算法的可行性特征
B. 若输入a的值为6,则输出a的值为7
C. 该算法可以用流程图表示
D. 该算法最后输出的结果都是不大于10的自然数
【解析】 本题主要考查算法的描述。分析伪代码,符合算法的“可行性”特征;若输入a的值为6,则输出a的值为10;该算法可以用流程图表示;该算法最后输出的结果都是不大于10的自然数。
B
9. 某算法的自然语言描述与流程图表示分别如下:
自然语言 第1步:输入一个实数x 第2步:判断x与0的大小关系,若x＜0,则y＝2x－1,否则y＝x2－1 第3步:输出y的值 第4步:算法结束
流程图中处理框①、②处可分别填入的是(　　)
A. ①y←x2－1　②x←2x－1 B. ①y←x2－1　②y←2x－1
C. ①y←2x－1　②y←x2－1 D. ①x←x2－1　②y←2x－1
B
【解析】 对于同一个算法,可以用不同的表示方法来描述。分析自然语言描述和流程图描述,可知自然语言中的第2步对应着流程图中的判断部分。由自然语言可知,处理框①和②的功能是求y的值。在执行过程中,当条件“x＜0 ”不成立时,会执行①,否则会执行②。对照自然语言描述,处理框②处是在求解当“x＜0 ”成立时的y值,即“y←2x－1”;处理框①处是在求解当“x＜0 ”不成立时的y值,即“y←x2－1”。B正确。一、 算法的概念及描述
1. 算法的概念
广义地讲,“算法”指的是解决问题或完成任务的一系列步骤。在计算机科学领域内,“算法”指的是用计算机解决问题的步骤,是为了解决问题而需要让计算机有序执行的无歧义的、有限步骤的集合。
2. 算法的特征
特征 含义
有穷性 一个算法的处理步骤必须是有限的
可行性 一个算法中的每一步操作与要求都应该是算法执行者(人或者机器)可以实施的,同时是在现实环境中能做到并且能在有限的时间内完成的
确定性 算法中对于每个步骤的执行的描述必须是明确的
0个或多个输入 初始数据可以从外界输入,也可包含在算法中
1个或多个输出 算法必须有问题求解的结果,包含至少一个输出
3. 算法的要素
要素 含义
数据 用算法解决问题时,必须明确参与运算的初始数据、运算时产生的中间数据以及代表问题解决的结果数据
运算 对数据进行运算时,必须明确每一步的运算是什么、对哪些数据进行运算等
控制转移 在算法执行过程中,有时需要根据数据或运算结果的特点进行不同的处理,这时就需要运用控制转移来执行不同的操作。比如,控制程序实现分支结构或者循环结构
4. 算法的描述
(1)常见的算法描述方式有自然语言、流程图、伪代码和计算机程序设计语言等。
描述方式 含义
自然语言 指人们在日常生活中交流时使用的语言。用自然语言描述算法的方式通俗易懂,但缺乏直观性和简洁性,容易产生歧义
流程图 流程图用一些图形符号表示规定的操作,并用带箭头的流程线连接这些图形符号,表示操作进行的方向。用流程图描述算法的方式结构清晰,寓意明确
伪代码 指一种比较直观简洁的、符号接近计算机程序代码的算法描述方式,风格类似于计算机程序设计语言,但又不是真正的可以被计算机理解的代码
计算机程序 设计语言 为了让计算机帮助人们真正解决问题,需要将算法用计算机能够理解的语言来描述,这种语言称为计算机程序设计语言
(2)常用的流程图基本图形及其功能
图形 名称 功能
开始/结束符 表示算法的开始或结束
输入/输出框 表示算法中数据的输入或输出
处理框 表示算法中数据的运算处理
判断框 表示算法中的条件判断
流程线 表示算法中的流向
连接点 表示算法中的转接
(3)伪代码的语法约定
①条件判断语句
格式1:If条件then
　　(语句序列1)
Else
　　(语句序列2)
格式2:If条件then
　　(语句序列1)
②循环语句
格式:while条件
　　　　(循环体)
【例1】 下列关于算法的说法,错误的是(　C　)
A. 算法是解决问题的有序步骤
B. 算法有输入、输出、确定性、可行性、有穷性等基本特征
C. 解决同一问题的算法只有一种
D. 描述算法的方法主要有自然语言描述法、流程图描述法、伪代码法
【解析】 本题主要考查算法的描述。算法是解决问题的有序步骤;算法有输入、输出、确定性、可行性、有穷性等基本特征;解决同一问题的算法有多种;描述算法的方法主要有自然语言描述法、流程图描述法、伪代码描述法。
【例2】 在用万能求根公式求一元二次方程的解的算法中,在方程不存在实数解的情况下,也要求输出“方程无实数根”。这体现了算法特征中的(　D　)
A. 有穷性
B. 可行性
C. 有0个或多个输入
D. 有1个或多个输出
【解析】 本题考查算法的特征。分析题意可知,求一元二次方程实数根的算法,在方程无实根时也要求有输出,这与算法“有输出”的特征吻合,即算法一定要有结果输出。
【例3】 计算机编程解决“斐波那契数列(每一项都是前两项之和)”问题的过程由以下4个步骤组成:
①用Python中的循环结构编写程序
②调试运行程序,发现错误并进行修正
③设计算法:设计输入、处理、输出等一系列算法
④抽象与建模:用数学符号F(0)＝F(1)＝1,F(n)＝F(n－1)＋F(n－2)(n≥2,n∈N)描述解决问题的计算模型的正确顺序是(　D　)
A.①②③④
B.③④①②
C.④③②①
D.④③①②
【解析】 本题考查算法的表示。先抽象与建模,再设计算法,接着编写程序,最后调试运行程序。
【例4】 某算法用伪代码描述如下。
输入两个正整数x,y
if x＜y then
　　z←(y-x)/2
Else
　　z←(x-y)/2
输出z
关于上述算法,下列说法中正确的是(　D　)
A. 不符合“可行性”特征
B. 无法用流程图描述
C. 运用了循环结构的控制转移
D. z为正整数x与y差值的一半
【解析】 本题考查算法及其描述。题中用伪代码来描述算法,其每一个步骤都有明确的作用和含义,符合“可行性”等算法特征。本题的算法可以用自然语言、流程图等方式来描述。由伪代码可知,该算法运用了分支结构的控制转移。为了保证x、y的差为正,需要对x与y的大小关系进行判断,z为正整数x与y差值的一半,D正确。
【例5】 “梅森素数”指的是符合条件m＝2p－1的数,其中指数p与整数m均为素数。小李想找出10000以内所有“梅森素数”,设计算法过程如下:
①设计核心算法:如何判断素数
②调试运行程序,重点检测边界条件
③借助Python语言,通过具体编程实现
④将问题抽象成条件的判断与素数的判断,并完成建模
下列选项中,解决该问题的过程的正确顺序是(　C　)
A. ①②③④
B. ②①④③
C. ④①③②
D. ①④②③
【解析】 本题考查算法的表示。抽象与建模是第一步,设计算法是第二步,计算机编程实现是第三步,调试程序是最后一步。
1. 下列关于算法的说法,正确的是(　B　)
A. 算法解决问题的一般过程依次为“设计算法—抽象与建模—描述算法”
B. 数据、运算和控制转移是算法的三大要素
C. 任何算法都必须有至少一个输入数据和一个输出数据
D. 同一种算法只能用一种表示方法
【解析】 本题主要考查算法的描述。算法解决问题的一般过程依次为“抽象与建模—设计算法—描述算法”;数据、运算和控制转移是算法的三大要素;算法可以没有输入,但必须有输出;同一种算法能用多种表示方法,如伪代码、算法流程图等。
2. 编程求解问题时,要求输出“所有的偶数”。这一要求违反了算法的特征中
的(　C　)
A. 有输出
B. 确定性
C. 有穷性
D. 可行性
【解析】 本题考查算法的特征。由于不可能输出所有的偶数(无穷多个),C
正确。
3. 下列关于算法描述的说法,错误的是(　C　)
A. 流程图用特定的简单图形符号表示规定操作,结构清晰、寓意明确
B. 用自然语言描述算法通俗易懂,但容易出现歧义,且表述烦琐
C. 伪代码的语法接近计算机程序语言,描述简练,且能够被计算机执行
D. 用计算机程序设计语言描述的算法,可以被计算机理解和执行
【解析】 伪代码不能被计算机执行。伪代码指的是一种比较直观简洁的、符号接近计算机程序代码的算法描述方式,其风格很像计算机程序设计语言,但又不是真正的可以被计算机理解的代码。
4. 下面流程图所表述的算法,违反的算法特征是(　C　)
A. 该算法没有数据输入
B. 该算法没有数据输出
C. 不符合算法的有穷性特征
D. 不符合算法的确定性特征
【解析】 本题主要考查算法的特征。分析流程图可知,该算法会陷入“死循环”,不符合算法的有穷性特征。
5. 下列问题中,不能用算法来描述的是(　B　)
A. 已知圆锥的底面半径和高,求表面积和体积
B. 求方程y＝2x＋1的所有整数解
C. 计算某班同学的英语平均分
D. 求一元二次方程ax2＋bx＋c＝0(a≠0)的两个实数解
【解析】 本题主要考查算法的描述。方程y＝2x＋1的所有整数解有无数个,不满足算法的有穷性特征,因此不能用算法来描述。
6.下列选项中,可以用于描述算法的有(　D　)
①中文　②流程图　③伪代码　④计算机程序设计语言　⑤英文
A. ①④⑤ B. ②③⑤
C. ①②③④ D. ①②③④⑤
【解析】 算法的描述方式有自然语言、流程图、伪代码和计算机程序设计语言。
7. 费马平方和定理:质数能表示为两个平方数之和的充分必要条件是该质数被4除余1,如13＝22＋32。现通过编程来验证3和99之间所有质数是否符合费马平方和定理。
解决该问题的算法步骤如下:
①列举a在[1,]范围内的所有整数,计算对应的b,即b＝。
②变量n表示3和99之间的数,变量a和b的平方表示两个平方数,即n＝a2＋b2。
③若根据质数n除以4余1能够找到整数b,则符合定理。
④判断n是否为质数。
⑤若根据质数n除以4余3无法找到整数b,则符合定理。
正确的算法步骤顺序是(　A　)
A. ②④①③⑤ B. ②④⑤①③
C. ②①④③⑤ D. ②①④⑤③
【解析】 本题主要考查利用算法解决问题。由选项可知,首先是②变量n表示3和99之间的数,变量a和b的平方表示两个平方数,即n＝a2＋b2;根据题干可知,接下来判断n是否为质数,即④判断n是否为质数;③⑤没有先后顺序,A正确。
8. 某算法用伪代码描述如下:
输入一个自然数a
if a*2＞10 then
　　a←10
else
　　a←a+1
输出a
关于上述算法,下列说法中错误的是(　B　)
A. 符合算法的可行性特征
B. 若输入a的值为6,则输出a的值为7
C. 该算法可以用流程图表示
D. 该算法最后输出的结果都是不大于10的自然数
【解析】 本题主要考查算法的描述。分析伪代码,符合算法的“可行性”特征;若输入a的值为6,则输出a的值为10;该算法可以用流程图表示;该算法最后输出的结果都是不大于10的自然数。
9. 某算法的自然语言描述与流程图表示分别如下:
自然语言 第1步:输入一个实数x 第2步:判断x与0的大小关系,若x＜0,则y＝2x－1,否则y＝x2－1 第3步:输出y的值 第4步:算法结束
流程图中处理框①、②处可分别填入的是(　B　)
A. ①y←x2－1　②x←2x－1
B. ①y←x2－1　②y←2x－1
C. ①y←2x－1　②y←x2－1
D. ①x←x2－1　②y←2x－1
【解析】 对于同一个算法,可以用不同的表示方法来描述。分析自然语言描述和流程图描述,可知自然语言中的第2步对应着流程图中的判断部分。由自然语言可知,处理框①和②的功能是求y的值。在执行过程中,当条件“x＜0 ”不成立时,会执行①,否则会执行②。对照自然语言描述,处理框②处是在求解当“x＜0 ”成立时的y值,即“y←2x－1”;处理框①处是在求解当“x＜0 ”不成立时的y值,即“y←x2－1”。B正确。

展开更多......

收起↑