(共16张PPT)
3.2算法及其描述
编制计算机程序解决问题的全过程
分析问题
设计算法
编写程序
调试运行
检测结果
编程能够训练思维，它体现了一种抽象交互关系，自动化执行的思维模式。
编程重要的是逻辑思路，确定解决问题的详细方法和步骤，即设计算法。算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则，是能够被机械执行的动作或者指令的有穷集合。
在《几何原本》中，欧几里得阐述了关于求两个正整数的最大最大公约数的过程，这就是著名的欧几里得算法----辗转相除法，其具体过程如下：
设给定的两个正整数为m和n，求它们的最大公约数的步骤为：
①以m除以n，令所得的余数为R。
②若R=0，则输出结果n，算法结束；否则，继续步骤③
③令m=n，n=R，并返回步骤①继续进行。
实践
设给定的两个正整数m=112和n=64，利用辗转相除法，求它们的最大公约数。
算法如下：
（1）112除以64，余数为--------；
（2）-------除以-------余数为-------
（3）-------除以-------余数为-------。
答：112和64的最大公约数为--------
48
64
48
16
48
16
0
16
算法的特征
数据输入：一个算法有零个或多个输入；
确定性：算法执行的每一步必须有确切的定义，不可含混不清；
有穷性：一个算法在执行有穷步之后必须结束；
数据输出：一个算法有一个或多个输出，即最后的结果
可行性：算法中执行的任何计算步骤都可以被分解成基本的
可执行的操作步骤，即每个基本步骤都可以在有限时间内完成。
算法的描述
（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
语句组
开始
输入m和n
r=m
%
n
r=0
输出n
结束
m=n
n=r
否
是
(1)人们利用计算机解决问题的基本过程为（
）
①调试运行程序
②分析问题③设计算法
④问题解决
⑤编写
A.①②③④⑤
B.②④③⑤①
C.
④②③⑤①
D
②③⑤①④
(2)下面关于算法的描述，正确的是(
)。
A.算法不可以用自然语言描述
B.算法只能用流程图来描述
C.一个算法必须保证它的执行步骤是有限的
D.算法的流程图表示法有零个或多个输入，但只能有一个输出
(3)计算机能直接识别、理解执行的语言是(
)。
A.汇编语言B.
Pyhon语言C.
Basic语
言D.机器语言
(4)下列关于算法的叙述，正确的是(
)
A.解决一个问题的算法只有一种
B.有穷性是算法的基本特征之一
C.可行性不属于算法基本特征
D.算法对程序设计没有任何作用3.2算法及其描述
习题
一、选择题
1.在求解“一元二次方程实数根”的算法中，如果方程不存在实数解，也要求输出结果“无实数根”。此要求主要体现了算法特征中的（
B
）
A.有穷性?
B.数据输出?
C.确定性
D可行性
2.下列问题不能用算法描述的是（
C
）
A.已知a、b、c的值，求一元二次方程ax2+bx+c=0（a≠0）的实数根
B.计算某个班级语文成绩的平均分
C.列出方程y=2x+1的所有实数解
D.根据圆的半径求圆的面积和周长
3.求交换两个变量a
b的值的算法步骤如下：
①输入变量ab的值
②输出变量ab的值
③将变量a的值赋给变量b
④将变量b的值赋给变量c
⑤将变量c的值赋给变量a
⑥结束
其正确的顺序是（
D
）
①②③④⑤⑥
B.①⑤④③②⑥
①③④⑤②⑥
D.①④③⑤②⑥
4.“如果下雨在体育馆上体育课，不下雨则在操场上体育课”。有流程图来描述这一问题时，判断“是否下雨”的流程图符号是（
B
）
矩形
B.菱形
C.平行四边形
D.圆圈
5.执行如图所示的程序框图，若输出的S＝88，则判断框内应填入的条件是(
B
)
k>7?
B.
k>6?
C.
k>5?
D.
k>4?
二、填空题
1.程序的基本控制结构有
、
和
。（顺序结构、选择结构、循环结构）
流程图中表示判断的是
，表示计算和赋值的是
。（菱形、长方形）
介于自然语言和计算机语言之间的文字和符号来描述算法的是______________________。（伪代码）
已知一个学生的语文成绩为89，数学成绩为96，外语成绩为99，求这个学生成绩总分和平均分的一个算法如下，请将其补充完整：
第一步：取A=89，B=96，C=99.
第二步：
第三步：
第四步，输出计算结果。
答案：计算部分D=A+B+C
计算平均分E=D/3
