粤教版（2019）高中信息技术必修一 第三章 算法基础（38张PPT）

第三章 算法基础
理解算法的概念与特征，学会运用恰当的描述方法和控制结构表示简单算法，懂得描述程序设计语言产生与发展过程。
本章将用“设计从A市到B市最佳的旅行路线方案”为例，体验计算机解决问题的过程。
截止2017年10月，中国高速公路里程13.1万千米，位居世界第一，2020年将达15万千米；高铁里程2.2万千米，位居世界第一；城市轨道交通4153千米，位居世界第一。
计算机解决问题的过程
1、分析问题：建立模型，确定“做什么”；
2、设计算法：寻找“如何做”，并描述精确步骤；
3、编写程序：编写程序的任务就是用一种计算机能接受的程序设计语言来描述问题求解的算法；
4、调试运行：计算机验证语法错误，编程者验证结果确定无逻辑、计算错误。
3.1体验计算机解决问题的过程
问题：
若你想从A市到B市旅游，怎样找到耗时最少的旅行路线方案哪？
从A市到B市的交通情况
从图中可知，从A市经B1市到B市的联运班次有7×9=63（班），从A市经B2市到B市的联运班次有12×9=108（班），合计为S=63+108=171（班）
然后在171班次中找到能够中转且等待时间加上行驶时间最少的联运班次。
清洗后的数据表B1 Sheet1
清洗后的数据表B1 Sheet1
从A市到B市耗时最少的旅行路线问题的程序运行结果
3.2算法及其描述
算法
是指在有限步骤内求解某一问题所使用的一组定义明确的规则。
算法的特征
有穷性：一个算法在执行有穷步之后必须结束；
确定性：算法执行的每一步必须有确切的定义，不可含混不清；
数据输入：一个算法有零个或多个输入；
数据输出：一个算法有一个或多个输出，即最后的结果
可行性：算法中执行的任何计算步骤都可以被分解成基本的
可执行的操作步骤，即每个基本步骤都可以在有限时间内完成。
算法的描述
（1）用自然语言描述算法：如果算法中含有比较多的分支或者循环操作等时，使用自然语言比较难将其清晰表示出来；同时由于自然语言的歧义性会导致算法执行的不确定性。
设给定的两个正整数为m和n，求它们的最大公约数的步骤为：①以m除以n，令所得的余数为R。
②若R=0，则输出结果n，算法结束；否则，继续步骤③令m=n，n=R，并返回步骤①继续进行。
（2）用流程图描述算法：用程序框图来描述，使流程清晰、简洁。
例：用辗转相除法求两数的最大公约数
（1）输入m和n的值；
（2）用m除以n，令所得的余数为r；
（3）若r=0，则输出n,算法结束，否则继续（3）；
（4）令m=n，n=r，并返回步骤（1）。
开始
输入m和n
r=m % n
r=0
输出n
结束
m=n
n=r
否
是
牛刀小试：
例：利用流程图描述求一元二次方程ax2+ bx+c=0的根
1.输入a，b，c的值
2.令d=b*b-4*a*c
3.如果 d>=0
计算 x1=


x2=
输出x1,x2
转步骤4
否则输出“方程无解”转步骤4
4.结束程序
（3）用伪代码描述算法：用介于自然语言和计算机语言之间的文字和符号来描述算法，易于理解，便于向计算机程序设计语言过渡。
m=input(“请输入m的值”)
n=input(“请输入n的值”)
R=m%n
while R!=0:
{ m=n
n=R
R=m%n}
输出n
算法举例
有两个瓶子A和B ，A瓶装有雪碧，B瓶是可乐，问如何把雪碧和可乐互换。即A瓶原来雪碧，现改为盛可乐，B瓶则相反。
第一步：将A内溶液倒入C瓶中
第二步：将B内溶液瓶倒入A瓶中
第三步：将C内溶液瓶倒入B瓶中

程序的三种基本结构
前面的算法用到了顺序结构、选择结构、循环结构这三种基本控制结构。任何复杂的算法都可以使用这三种基本控制结构组合来表示。
语句1
语句2
顺序结构表示程序中各个步骤按照出现的先后顺序依次执行。
程序的三种基本结构
选择结构表示程序的处理步骤出现了分支，需要按照某一个特定的条件选择其中一个分支执行，有单选择，双选择，多选择。
条件
语句1
语句2
Y
N
程序的三种基本结构
循环结构表示反复执行某些操作直到判断条件为假或者为真时才结束循环。如辗转相除法求两数最大数
条件
条件
语句组
Y
N
Y
N
语句组
程序的三种基本结构
计算机程序设计语言的发展历程
1.机器语言
机器语言
00110000
00000101
00000100
00000010 11110100
……
由于计算机采用的物理器件主要是电子元件，因此计算机只能识别二进制数1,0表示的指令集合，可直接识别和执行，但用二进制代码编制的程序编写任务繁重且难学、难理解、难记、难写、难修改，难调试，难移植，但是运行效率是最高的。
指令序号
机器指令
指令功能
1
10110000
00001001
把加数9送到累加器AL中。
2
00000100
00001000
把累加器AL中的内容与另一个数8相加，结果存在累加器AL中（即完成9+8的运算）。
3
11110100
停止操作。
指令序号
机器指令
指令功能
1
10110000
00001001
把加数9送到累加器AL中。
2
00000100
00001000
把累加器AL中的内容与另一个数8相加，结果存在累加器AL中（即完成9+8的运算）。
3
11110100
停止操作。
用inter 80386机器指令完成“9+8”的加法运算表
穿孔纸带
计算机程序设计语言的发展历程
2.汇编语言
汇编语言
MOV A，5
ADD A，2
HLT
……
也称符号语言，用符号和十进制数表示的语言。计算机不能直接识别和执行，需通过汇编程序翻译成机器语言，移植性不好，但由于是针对计算机特定硬件编制的程序，能够发挥硬件特长，质量高。
指令序号
汇编语言指令
指令功能
1
MOV AL,9
把加数9送到累加器AL中。
2
ADD AL,8
把累加器AL中的内容与另一个数8相加，结果存在累加器AL中（即完成9+8的运算）。
3
HTL
停止操作。
计算机程序设计语言的发展历程
3.高级语言
高级语言
LET X ＝ 5 + 2
PRINT X
END
……
第一种为Fortran语言，用于科学和工程运算。高级语言更接近于自然语言，用十进制数和表达式表示。需通过解释或编译程序翻译成机器语言，计算机才能执行。这种语言容易学、容易编写。
指令序号
Python语言指令
指令功能
1
Print（9+8）
实现“9+8”
指令序号
机器指令
指令功能
1
10110000
00001001
把加数9送到累加器AL中。
2
00000100
00001000
把累加器AL中的内容与另一个数8相加，结果存在累加器AL中（即完成9+8的运算）。
3
11110100
停止操作。
指令序号
汇编语言指令
指令功能
1
MOV AL,9
把加数9送到累加器AL中。
2
ADD AL,8
把累加器AL中的内容与另一个数8相加，结果存在累加器AL中（即完成9+8的运算）。
3
HTL
停止操作。
指令序号
Python语言指令
指令功能
1
Print（9+8）
实现“9+8”
Python是一种跨平台的计算机程序设计语言。 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。
Python在设计上坚持了清晰划一的风格，这使得Python成为一门易读、易维护，并且被大量用户所欢迎的、用途广泛的语言。
Python是一种解释型脚本语言，可以应用于以下领域：?
Web 和 Internet开发
科学计算和统计
人工智能
桌面界面开发
软件开发
后端开发
网络爬虫
二进制与十进制转换
二进制转换成十进制数
例如：(1011) 2=(?)10
十进制转换成二进制
例如: (14)10=(?)2
25
24
23
22
21
20
32
16
8
4
2
1
P20 章末习题1(3)
第1章补充
八进制与十进制转换
八进制转换十进制
例如：(41)8=(?)10
十进制转换八进制
例如：(35)10=(?)8
82
81
80
64
8
1
P20 章末习题1(3)
第2章补充
十六进制与十进制转换
十六进制有：0、1、2、3、4、5、6、7、8、9、A(10)、B(11)、C(12)、D(13)、E(14)、F(15)共十六个数。
十六进制转换成十进制
例如：(25)16=(?)10
十进制转换十六进制
例如：(43)10=(?)16
162
161
160
256
16
1
P20 章末习题1(3)
第2章补充
二进制与八进制转换
二进制与八进制转换
例如: (11001111100101)2=(?)8
八进制与二进制转换
例如：(1314)8=(?)2
第3章补充
二进制与十六进制转换
二进制转换十六进制
例如: (11001111100101)2=(?)16
十六进制转换二进制
例如：(A27)16 =(?)2
第3章补充