02算法及算法的描述方法.ppt

C程序设计
(Programming in C )
School puter Science & Engineering, Xidian University, China
上次课程的内容提要
C语言是一种得到广泛应用的高级程序设计语言
用高级程序语言编写的程序需要进行翻译才能被计算机执行,对于C语言程序,该翻译过程由C编译器完成
明确本课程的学习目标:初步掌握程序设计基本知识和良好的程序设计风格
用计算机解决问题的首要步骤是分析问题并设计算法
算法描述了给定问题的解题步骤
流程图是一种算法描述方法
西安电子科技大学计算机学院- School puter Science & Engineering, Xidian University, China 2
素性判别
素性判别就是给定一个正整数,判定其是否为素数
素数的定义:一个大于1的整数,如果它的正因数只有1和它本身,就叫做素数,否则就叫合数。
如何判定给定正整数n是否为素数呢?根据定义。
从2开始找n的因子,若能找到一个介于2和n-1之间的n的因子,说明n不是素数;否则,n是素数。
西安电子科技大学计算机学院- School puter Science & Engineering, Xidian University, China 3
素性判别
Y
N
K← 2
K不能整除n?
K ← K+1
输出n是素数
输入n的值
开始
结束
Y
N
K等于n?
输出n不是素数
西安电子科技大学计算机学院- School puter Science & Engineering, Xidian University, China 4
求最大公约数
设有两个正整数m和n,如何求其最大公约数?
有多种方法,例如
求解速度最快的方法是辗转相除法。
辗转相除法(欧几里得算法):
给定两个正整数m和n,求它们的最大公约数(公因子)。
步骤1:【求余数】以n除m并令r为所得余数(0≤r<n)
步骤2:【余数为0?】若r=0,算法结束;n即为答案
步骤3:【互换】置m←n, n←r,转向步骤1。
西安电子科技大学计算机学院- School puter Science & Engineering, Xidian University, China 5
求最大公约数流程图
Y
N
r←m被n除的余数
r不等于0?
n ← r
输出n的值
输入正整数m和n
开始
结束
m ← n
结构不好!
西安电子科技大学计算机学院- School puter Science & Engineering, Xidian University, China 6
这次课的主要内容
结构化方法的基本结构:顺序结构、选择结构、循环结构
其他算法描述方法
N-S盒图方法
伪代码方法
西安电子科技大学计算机学院- School puter Science & Engineering, Xidian University, China 7
三种基本结构
西安电子科技大学计算机学院- School puter Science & Engineering, Xidian University, China 8
三种基本结构
1966年,Bohra和Jacopini提出了以下三种基本结构,作为构造算法的基本单元
顺序结构
选择结构
循环结构
顺序结构和选择结构的流程图如下图所示
A
B
顺序结构
a
b
p
A
B
成立
不成立
a
b
选择结构1
p
A
成立
不成立
a
b
选择结构2
西安电子科技大学计算机学院- School puter Science & Engineering, Xidian University, China 9
三种基本结构
循环结构
当型循环结构(while型循环)如图循环结构1所示
直到型循环结构(Until型循环) 如图循环结构2所示
p
A
成立
不成立
a
b
循环结构2
p
A
成立
不成立
a
b
循环结构1
西安电子科技大学计算机学院- School puter Science & Engineering, Xidian University, China 10