资源简介

(共46张PPT)
第二章 算法与问题解决
—— 信息技术 必修一 ——
算法的概念
算法的概念
算法的概念
算法的概念
古代： 算法主要是“算术”，数值的算术运算。
广义上： 算法指解决问题或完成任务的一系列步骤。
算法的执行者往往是人。
计算机领域： 算法指的是用计算机解决问题的步骤，是为了解决问题而 需要让计算机有序执行的、无歧义的、有限步骤的集合。
算法的执行者是计算机。
用计算机能理解的语言描述算法，就称为计算机程序设计
是不是所有的问题都能用算法来解决呢？
算法的特征
有穷性：算法必须能执行有限个步骤后终止。
可行性： 算法中的每一步骤都要求是可实施的，并且执行的任何运算 都可以在有限的时间内完成。
确定性：算法中每一次执行都有明确的定义。
0个或多个输入：所谓0个输入是指本身给出了初始条件。
1个或多个输出：算法必须必须包含至少一个输出。
写出所有的素数
数出所有星星的数量
精卫填海
列出方程y＝2x＋1的所有实数解
将正数相加得出负数
找出班级里英语成绩最好的人
取两个区间的中点
程序运行后没有结果
算法的特征
判断是否算法就用特征来判断
1.在求一元二次方程实数根的算法中，当方程不存在实数根时，也要求输出“方程无实数根”。这一要求主要体现了算法特征中的
A.有穷性 B.确定性
C.有1个或多个输出 D.有0个或多个输入
2.关于算法的描述,下列选项中正确的是( )
A.一个算法,当没有输入时,也没有输出
B.一个算法的执行步骤可以是无限的
C.一个问题只能有一个种算法
D.一个算法可以没有输入
著名数学家华罗庚“烧水泡茶”的两个算法。
算法一
第一步：烧水；
第二步：水烧开后，洗刷茶具；
第三步：沏茶。
算法二
第一步：烧水；
第二步：烧水过程中，洗刷茶具；
第三步：水烧开后沏茶。
算法的特征
解决同一个问题可以有不同的算法
算法具体的实现方式很多
算法的要素
用算法解决问题时，必须明确参与运算的初始数据、运算是产生的中间数据以及代表问题解决的结果数据。
在对数据进行运算时，必须明确每一步运算的是什么、对哪些数据进行运算等。
在算法执行过程中，有时需要根据数据或运算结果的特点进行不同的处理，这时就需要运用控制转移来执行不同的操作。
（分支、循环)
计算机解决问题本质是”数据运算”
数据
运算
控制转移
算法的描述
同一个算法可以用不同的方式描述
算法的描述
（1）输入苹果的重量x
（2）判断苹果的重量是否大于2千克
（3）如果苹果的重量不大于2千克，应付款y=x*1.5
（4）如果苹果的重量大于2千克，应付款y=2*1.5+(x-2)*1.5*0.8
（5）输出应付款的金额
使用自然语言描述算法。
优点：通俗易懂，容易理解
缺点：书写烦琐，不确定性，容易出现歧义，
不能被计算机识别和执行。
算法的描述
使用流程图描述算法。
开始
输入苹果的重量x
X>2
Y=x*1.5
Y=2*1.5+(x-2)*1.5*0.8
输出应付款 y
结束
Y
N
(1)输入苹果的重量x
(2)判断苹果的重量是否大于2千克
(3)如果苹果的重量不大于2千克，应付款y=x*1.5
(4)如果苹果的重量大于2千克，应付款y=2*1.5+(x-2)*1.5*0.8
(5)输出应付款的金额
优点：直观形象，易于理解
缺点：分支增多时影响理解，
不能被计算机识别和执行。
算法的描述
算法的描述
使用伪代码描述算法。
车位探测结果→flag
IF flag=1 then （指示灯绿色，输出“空车位”）
else （指示灯红色，输出“非空车位”）
伪代码是符号接近计算机语言的算法描述方式，没有统一严格的规定，只要定义合理、表达正确即可。
风格很像程序设计语言，但又不是真正能被计算机理解的代码
优点：直观简洁，紧凑简练，转化成代码更方便
缺点：语法不统一，不易排查错误，不能被计算机识别和执行。
【1】介于自然语言和计算机语言之间的一种算法描述是( )
A.python程序设计语言
B.流程图
C.伪代码
D.高级语言
【2】用伪代码描述算法：
①输入a、b的值；
②c←a；
③a←b；
④b←c；
⑤输出a、b的值；
算法的描述
当输入a的值为3，b的值为5时，输出结果中a和b的值分别为
A.3　5 B.3　3
C.5　5 D.5　3
算法的描述
机器语言由二进制的0、1代码指令构成，能被计算机直接识别。但理解和记忆机器语言非常困难，并且容易出错，编程效率低。
汇编语言是符号化的机器语言，采用英文助记符代替机器指令，容易记忆和识别，提高了程序的可读性。但它是面向机器的语言，是为特定的计算机系统设计的，它要求软件工程师对相应的机器硬件非常熟悉
16位计算机的机器指令为：1101001000111011
汇编语言指令为：add2,3,result，运算结果写入result
程序语言的发展
都是低级语言
算法的描述
高级语言更接近自然语言，并不特指某一语言，也不依赖于特定的计算机系统，因而更容易掌握和使用，通用性也好。比较流行的高级语言有Java、C/C++、Python等，程序的可读性好，也便于修改、维护。
机器语言→汇编语言→高级语言
高级语言代码为：result=2+3
程序语言的发展
优点：计算机理解执行
缺点：需要学习，难度高
算法的描述
自然语言 流程图 伪代码 计算机语言
优点 通俗易懂 形象直观 容易理解 简洁易懂 语法任意 能让计算机执行
缺点 易产生歧义 情况复杂时，过多的流程线影响理解 不直观 错误不易发现 需要有学习基础
×
√
√
×
√
×
算法的描述
小明发现奶茶店的奶茶桶是需要人为更换的，因此他设计了一个算法，当奶茶容量少于500ml 的时候，会自动添加奶茶直至容量到达 500ml。
下列说法正确的是 ( )
A.通过压力计测算当前奶茶桶内奶茶的容量，属于数据的获取
B.该算法需要时刻计算当前奶茶桶内奶茶的容量，属于算法要素中的控制转移
C.当奶茶容量超过 500ml 的时候，奶茶停止添加，属于算法要素中的运算
D.该算法考虑了数据、运算、控制转移等要素，一定是合理的
A
算法的控制结构
大程序采用“自上而下，逐步细化”的方法，把大任务拆分成若干个小任务组成，每一个小任务再分解为若干个子任务，逐级分解，直至三种基本结构。
任何算法(程序)都可以由顺序结构、分支结构和循环结构这三种基本结构组合来实现
算法的控制结构
按照顺序从上往下依次执行，每条语句必须且只执行一次。
语句1
语句2
语句3
选择乘车日期和车次
选择或添加乘车人
提交购票订单
网上支付购票款
顺序结构
算法的控制结构
根据条件判断选择不同的分支执行：
条件为真时执行Y指向的语句，否则执行N指向的语句。
选择结构中，必有一个分支被执行，其余分支不执行。
分支结构
N
Y
语句块1
语句块2
条件表达式
语句块1
Y
N
条件表达式是否为真？
算法的控制结构
分支结构
该流程图的功能是什么？
求x，y，z三个数中的最大值
算法的控制结构
多分支
特点：条件判断选择不同分支，一次只执行一个分支，其余分支不执行
当<表达式1>条件成立时，执行<语句块1>, 本结构结束。若为假，则判断<表达式2>，依此类推。
直到找到一个为真的条件时，才执行相应的语句块，本结构结束。
对输入的整数a和b，找出其中的较大者赋给c并输出。解决该问题的算法流程图如图所示，该流程图中虚线框部分的内容可为(　　)
D
算法的控制结构
对某个条件进行判断，当符合条件时，执行Y指向的语句(循环体)，然后返回重新判断这个条件，当符合条件时，再次执行循环体。
重复上述过程，直到不符合条件，则跳出循环，执行循环体后面的指令。
N
Y
语句块1
语句块2
条件表达式
算法的控制结构
循环结构
B
C
某算法的部分流程图如图所示。执行这部分流程，若输入a为22，则下列说法正确的是
A. a 的值为 2
B. 循环条件“a=b？”一共执行了 3 次
C. 语句“a←a-b”一共执行了 3 次
D. 第 2 次执行循环条件时，b 的值为 6
常见问法：
变量值？
输出值？
语句执行几次？
作用？
做法：将每次循环的变量值列成表格
2.某算法的部分流程图如第 8 题图所示。
若输入 m 和 n 的值分别 8 和 6，运行该算法后，以下说法正确的是()
A．“n≠0？”共执行了 2 次
B．若输入 m 和 n 的值分别为 6 和 8，运行结果不变
C. 该算法的功能为求解 m 和 n 的最大公约数
D．流程图标记“①”所在处理框中的语句调换次序不影响该算法的功能
B
辗转相除法——最大公约数
×
√
×
×
×
算法解决问题的过程
抽象与建模
数据采集
算法解决问题的过程
从现实项目中的真实情境中提炼出核心的要素并加以确定或假设，最终定义出一个有明确已知条件和求解目标的问题，并用数学符号描述解决该问题的计算模型
问题：求全班的平均分
已知：每个学生的得分，假设为a1到aN
求解：班级的平均分，假设为aver
数学模型： 已知a1，a2，a3，a4，……,aN,求N个数的平均数aver
aver=(a1+a2+……+aN）/N
设计算法
数据采集
算法解决问题的过程
遵循算法的特征，围绕算法的要素设计算法，自顶向下，逐步细化
①. 输入a1到an
②. 表示第几个学生的变量i初始化为1
③. 如果i<=n,把第i个学生的成绩累加到sum中，否则转⑤
④. i增加1，然后转③ 输出结果aver
⑤. 总和sum除以N，结果记录在aver中
⑥. 输出变量aver的值
①输入数据
②处理数据
③输出处理结果
模拟策略：根据现实事物的实际流程和要求逐步进行处理
×
√
√
√
√
×
39
第一步：抽象与建模
第二步：设计算法
第三步：描述算法
算法解决问题的过程
计算机解决问题的过程
第一步：抽象与建模
第二步：设计算法
第三步：编写程序
第四步：调试运行程序
计算机解决问题过程
计算机解决问题过程
1.抽象与建模
绘制正多边形，除了要知道它的边数n和边长a，关键是要计算出每次旋转的角度。因此，解决这个问题的计算模型可以表示如下：
假设正多边形的边数为n, 边长为a。
则内角度数d的值为：d= (n-2) x180÷n。
每次旋转的角度为：180-d。
建立数学模型
计算机绘制一个正N边形
2.设计算法
基于问题的抽象与建模，绘制一个正多边形的算法可以做如下描述：
①输入要绘制的正多边形的边数n和边长a。
②计算正多边形的每个内角度数d, 其中d= (n-2) x180÷n。
③将以下过程重复执行n遍：画一条长度为a的线段，再将画笔方向向左（逆时针）旋转（180-d) 度。
输入数据
处理数据
输出数据
计算机解决问题过程
3. 编写程序
要让计算机按照预先设计的算法进行处理，需要将该算法用计算机程序设计语言描述，形成计算机程序。
计算机解决问题过程
import turtle
n=int (input ("please input n: "))
a=int (input ("please input a: "))
d= (n-2)*180/n
t=turtle. Pen()
for i in range(n) : #重复执行n遍
t.forward(a) ＃向前绘制长度为a的线段
t.left(180-d) ＃向左旋转（180-d) 度
4. 调试运行程序
通过运行程序，计算机会自动执行程序中的命令。但是，在将算法进行程序实现时，可能会因为录入错误、语法错误、逻辑错误等原因，导致程序不能正常运行或输出错误的结果。
此时，需要对程序进行调试，以便发现错误并进行修正。例如、字母大小写的疏忽可能直接决定程序能否正常运行，程序中参数的调整可能影响输出图形的形状。
计算机解决问题过程
45
1.用计算机解决问题一般经历下面几个过程:①设计算法,②调试运行,③编写程序,④抽象建模。以下排序正确的是( )
A.④①③② B.①②④③ C.③④①② D.④①②③
2.某景区使用了游客人数控制系统来控制景区内游览人数。该系统在景区各个人口和出口分别统计人数,并汇总计算得出景区内的大致人数。该过程属于计算机解决问题的一般步骤中的哪个环节( )
A.抽象建模 B.设计算法
C.编写程序 D.调试运行程序
A
D
计算机解决问题过程
×
√
√
√
√
×

展开更多......

收起↑