3.2 算法及其描述 课件 2022—2023学年粤教版（2019）高中信息技术必修1（33张PPT）

(共33张PPT)
算法及其描述
算法及其描述
算法
算法及其描述
请用枚举的方法，讨论用数学的方法计算从昆明火车站到玉溪市区耗时最少的方法和步骤。
算法
算法的概念
算法
讨
论
火车站->呈贡的工具 所需时间 在呈贡转乘停留时间 呈贡->玉溪的交通工具 所需时间
小汽车 42分钟 0分钟 小汽车 47分钟
公交 116分钟 20分钟 城际班车 50分钟
地铁 50分钟 15分钟 高铁 37分钟
火车 42分钟 5分钟 火车 45分钟
算法及其描述
算法
我们计算时，我们可以这样进行枚举
算法的概念
算法
42+0+47
42+0+50
42+0+37
42+0+45
火车站->呈贡的工具 所需时间 在呈贡转乘停留时间 呈贡->玉溪的交通工具 所需时间
小汽车 42分钟 0分钟 小汽车 47分钟
公交 116分钟 20分钟 城际班车 50分钟
地铁 50分钟 15分钟 高铁 37分钟
火车 42分钟 5分钟 火车 45分钟
42+20+47
42+20+50
42+20+37
42+20+45
......
42+5+47
42+5+50
42+5+37
42+5+45
思路：
让每列的数分别和其它列进行组合计算，每次计算出的最小值保存在d里面。
设定d=10000。（d保存最小值，我们一开始设定d一个较大的值，如10000）
三个过程的时间分别用三组数来表示，即 用 。
讨
论
算法及其描述
算法
计算的步骤如下：
算法的概念
算法
第一步：设定d=10000
第二步：计算j= 的值
第三步：j和d比较，如j结果比d小，那么d=j,否则d=d
第四步：重复第二步，直到三组数里的所有组合都都被计算过（即：n1=1至4，n2=1至4，n3=1至4）。
第五步：输出d的值
算法
算法及其描述
算法
算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。简单说就是解决问题的方法和步骤。
算法的概念
算法
我们人找到算法之后，不能只是自己心知肚明，计算机是不清楚的。我们必须明确的告诉它要处理的具体对象和每一步的准确处理过程，否则计算机就无法工作，即算法的描述要求尽可能精确、详尽。
算法及其描述
算法
算法的特征
算法
有穷性
执行有限步之后结束，且每一步都执行时间都是有限的。
确定性
算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。
输入项
有零个或多个输入。
输出项
至少产生一个输出。(输出d,如果不输出，那......)
可行性
原则上能精确运行，用纸和笔做有限运算后可以完成。
算法及其描述
算法的描述
算法及其描述
人们日常生活中使用的语言。
自然语言的优点：通俗易懂。
缺点：容易产生歧义。
算法的描述
描述算法的三种基本方法之一：自然语言
算法的描述
例子：
“这个人连老张也不认识”。
意思之一：这个人不认识老张。
意思之二：老张不认识这个人。
“第四步：重复第二步，直到三组数里的所有组合都都被计算过（即：n1=1至4，n2=1至4，n3=1至4）”，这里怎么计算就不是很清楚。
算法及其描述
例子：求两个正整数的最大公约数
算法的描述
描述算法的三种基本方法之一：自然语言
算法的描述
①输入两个正整数m,n(m>n)；
②计算m除以n所得的余数r；
③m=n,n=r；
④若r＝0,则m,n的最大公约数等于m；否则转到步骤②；
⑤输出最大公约数m；
⑥结束。
算法及其描述
流程图也称程序框图，算法的一种图形化表示方法。
与自然语言描述算法相比，用流程图描述算法形象、直观、更容易理解。
算法的描述
描述算法的三种基本方法之一：用流程图来描述
算法的描述
图形符号 名称 功能
起止框 表示算法的开始和结束
输入/输出框 表示算法中数据的输入或输出
处理框 表示操作的内容（赋值、计算等）
判断框 表示判断的条件，成立出口处标Y/“是”，不成立出口处标N/“否”
流程线 连接程序框
连接符 表示流程图的待续
算法及其描述
算法的描述
描述算法的三种基本方法之一：用流程图来描述
算法的描述
算法及其描述
用介于自然语言和计算机语言之间的文字和符号来描述算法。
算法的描述
描述算法的三种基本方法之一：用伪代码描述算法
算法的描述
m=input("m=")
n=input("n=")
if m < n:
m, n = n, m
r = 1
while r != 0:
r = m% n
m = n
n = r
print m
算法及其描述
使用伪代码描述算法没有严格的语法限制，书写格式也比较自由，只要把意思表达清楚就可以了，它更侧重于对算法本身的描述。
在伪代码描述中，表示关键词的语句一般用英文单词，其他语句可以用英文语句，也可以用汉语语句。
算法的描述
描述算法的三种基本方法之一：用伪代码描述算法
算法的描述
优点：
用伪代码描述的算法简洁、易懂，修改起来也比较容易，并且很容易转化为程序语言代码。
缺点：
是不是很直观。
算法及其描述
算法的描述
描述算法的三种基本方法比较（小结）
算法的描述
自然语言表示法 流程图表示法 伪代码表示法
求两个正整数的最大公约数 ①输入两个正整数m,n(m>n)； ②计算m除以n所得的余数r； ③m=n,n=r； ④若r＝0,则m,n的最大公约数等于m；否则转到步骤②； ⑤输出最大公约数m； ⑥结束。 m=input("m=")
n=input("n=")
if m < n:
m, n = n, m
r = 1
while r != 0:
r = m% n
m = n
n = r
print m
算法及其描述
三种结构组合起来描述算法。可以改善算法的清晰度。提高算法的可读性。
算法的描述
算法的三种结构
算法的描述
计算机程序设计语言
计算机程序设计语言介绍
算法及其描述
计算机程序
计算机程序的运行
计算机程序设计语言
输入设备
存储器
输出设备
运算器
控制器
CPU
计算机之父约翰冯诺依曼
算法及其描述
计算机程序
计算机程序的运行
计算机程序设计语言
主频：
CPU的工作频率。一个时钟周期完成的指令数是固定的，所以主频越高，CPU的速度也就越快了。
CPU控制器在时钟频率的控制下，完成取指令和数据，运算器也是在时钟频率的控制下完成计算。
运算器
控制器
CPU
算法及其描述
计算机程序
计算机程序的运行
计算机程序设计语言
1、键盘输入的数据在什么情况下进入内存？运算器如何知道我要运算了？显示器如何知道我要显示数据？
2、计算机如何操作数据和命令的？
算法及其描述
计算机工作的本质就是周而复始的获取指令、执行指令的过程。
计算机程序
计算机程序的运行
计算机程序设计语言
输入设备
存储器
输出设备
运算器
控制器
CPU
数据流
指令流
控制流
算法及其描述
计算机程序设计语言
计算机工作原理
计算机程序设计语言
10110000
00001001
00000100
00001000
11110100
计算机如何实现“8+9”运算
选择内存的一块区域
9
加
8
输出
算法及其描述
计算机程序设计语言
计算机程序的运行
计算机程序设计语言
10110000
00001001
00000100
00001000
11110100
机器语言
MOV AL，9
ADD AL，8
HLT
汇编语言
实现“8+9”运算关系
算法及其描述
指挥机器工作的指示和命令，程序就是一系列按一定顺序排列的指令，执行程序的过程就是计算机的工作过程。指令集，就是CPU中用来计算和控制计算机系统的一套指令的集合，而每一种新型的CPU在设计时就规定了一系列与其他硬件电路相配合的指令系统。
如x86，x86-64，3D-Now等
计算机程序
指令集
计算机程序设计语言
如果把CPU看作一个人，首先它要有正常的工作能力（既执行能力），然后又有足够的逻辑能力（能明白做事的顺序），最后还要听的懂别人的话（既指令集），才能正常工作。而这些集中在一起就构成了所谓的“架构”，它可以理解为一套“工具”、“方法”和“规范”的**。
计算机主要有两种架构，即复杂指令集计算机和精简指令集计算机。ARM 为代表的精简指令集， x86 为代表的复杂指令集
信息系统中的计算机
计算机的工作原理
信息系统中的计算机和移动终端
计算机架构
观
察
观看视频《X86和ARM架构区别是什么 》，了解计算机指令集合。
算法及其描述
计算机程序设计语言
计算机程序的运行
计算机程序设计语言
MOV AL，9
ADD AL，8
HLT
10110000
00001001
00000100
00001000
11110100
机器语言
汇编语言
Print 8+9
高级语言
三种语言实现“8+9”运算关系
算法及其描述
机器语言
机器语言是机器能直接识别的程序语言或指令代码，无需经过翻译，每一操作码在计算机内部都有相应的电路来完成它，或指不经翻译即可为机器直接理解和接受的程序语言或指令代码。
汇编语言
汇编语言（Assembly Language）是任何一种用于电子计算机、微处理器、微控制器或其他可编程器件的低级语言，亦称为符号语言。特定的汇编语言和特定的机器语言指令集是一一对应的，不同平台之间不可直接移植。
高级语言
高级语言（High-level programming language）是一种独立于机器，面向过程或对象的语言。高级语言是参照数学语言而设计的近似于日常会话的语言。
计算机程序设计语言
计算机程序设计语言的发展历程
计算机程序设计语言
算法及其描述
计算机程序设计语言
计算机程序设计语言的发展历程
计算机程序设计语言
MOV AL，9
ADD AL，8
HLT
10110000
00001001
00000100
00001000
11110100
机器语言
汇编语言
Print 8+9
高级语言
计算机程序设计语言的发展经历了机器语言、汇编语言、高级语言三个历程。
三种语言实现“8+9”运算关系
算法及其描述
计算机程序设计语言
计算机程序设计语言：机器语言
计算机程序设计语言
机器语言是机器能直接识别的程序语言或指令代码，无需经过翻译，每一操作码在计算机内部都有相应的电路来完成它。
特点：用二进制表示，计算机可以直接识别。
缺点：难以被理解，程序设计任务繁重。
优点：运行效率最高。
上世纪60年代,科学家在检查电脑上的穿孔纸带
算法及其描述
计算机程序设计语言
计算机程序设计语言：汇编语言
计算机程序设计语言
汇编语言，也叫面向机器的程序设计语言，是第二代计算机语言，它用一些容易理解和记忆的字母，单词来代替一个特定的指令和操作数，比如：用“ADD”代表数字逻辑上的加减，“ MOV”代表数据传递等等。
特点：用助记符号代替二进制指令码和操作数。
缺点：只能针对机器特定硬件而编制，移植性差，机器不能直接识别。
优点：相对容易理解、运行效率依然很高。
算法及其描述
计算机程序设计语言
计算机程序设计语言：高级语言
计算机程序设计语言
高级语言（High-level programming language）是一种独立于机器，面向过程或对象的语言。高级语言是参照数学语言而设计的近似于日常会话的语言。
在编程语言经历了机器语言，汇编语言等更新之后，人们发现了限制程序推广的关键因素——程序的可移植性。需要设计一个能够不依赖于计算机硬件，能够在不同机器上运行的程序。这样可以免去很多编程的重复过程，提高效率，同时这种语言又要接近于数学语言或人的自然语言。
特点：近似于日常会话的语言。
缺点：不能被机器识别，必须经编译或者解释，运行效率底。
优点：抽象度高，移植性好，容易理解。
算法及其描述
计算机程序设计语言
计算机程序设计语言的工作原理
计算机程序设计语言
10110000
00001001
00000100
00001000
11110100
机器语言
Print 8+9
高级语言
编译
算法及其描述
计算机程序设计语言
计算机程序设计语言的工作原理
计算机程序设计语言
编译：编译就是把高级语言变成计算机可以识别的2进制语言。
直译语言（解释语言）：
直译语言由解释器将代码一句一句运行编译为机器码，一行一行的运行。如：JAVAScript, Pascal, C,PHP, Python。
编译语言：
编译语言是一种以编译器来实现的编程语言。它不像直译语言一样，由解释器将代码一句一句运行，而是以编译器，先将完整代码编译为机器码，再加以运行。如：C语言，C++,Basic等。
编译语言执行时会生成一个EXE文件。