算法的基本方法.ppt

算法初步
教学目的
了解算法与程序的基本概念
掌握自然语言、流程图、伪代码等算法的表示方法
2
教学内容
算法与程序
算法的基本概念
算法的概念
算法的表示
算法设计的基本方法
枚举法
迭代法
排序
查找
3
一算法(algorithm)与程序
什么是程序(Program)?
程序和算法的关系是怎样的?
: P210
按一定的顺序安排的工作即操作序列
描述完成某项功能所涉及的对象和动作规则
计算机学科中,程序描述了计算机处理数据、解决问题的过程
4
5
科学家沃思提出:
程序=数据结构+算法
程序包括两方面的内容:
(1)对数据的描述:文件d:\。
(2)对操作的描述:指定操作步骤,
这些操作的先后顺序以及它们所作用的数据,要遵守一定的规则,即求解问题的的算法。
二算法的概念
1 什么是算法?
计算机来解决的某一类问题的方法或步骤
算法是程序的核心
例:小球称重
9个编号小球中有一个的质量偏小,其余的质量标准。用一天平,无需砝码,检出质量偏小的小球。
6
解法三:先将小球分成(1,2,3,4)与(5,6,7,8)两堆,若两堆的质量的相等则偏小的小球是第9个,否则将偏轻的小球分成两堆进行称量。
解法一:9个小球分成5堆,(1,2),(3,4),(5,6),(7,8),(9)
解法二:可将9个小球分成3堆进行称量, (1,2,3),(4,5,6),(7,8,9),若1,2相等,则称量第三堆,否则对偏轻的一堆继续称量。
7
哪种方法称量次数最少?
例:圆周率的计算
(1)割圆法
8
S正12边形=12 × △S=4
圆周率= S正12边形/R/R=3
公元3世纪,刘徽利用“割圆术”,也就是利用圆内接正六边形算起,依次将边数加倍,一直算到内接正3072边形的面积,从而得到圆周率的近似值为=,祖冲之把圆周率精确到小数点后15位
算法步骤:
①量出圆的半径R
②做圆的内接正n边形
③求小三角形的面积△S
④求圆的内接正n边形面积S= △S ×n
⑤求圆周率=S/R/R
⑥结束
9
(2)利用求圆周率公式
同一个问题,可用不同的算法来求解
算法不同,求解的效率不同
选择效率高、容易理解和编程实现的算法
2 算法的两个要素
算法是由操作与控制结构两个要素组成
(1)操作
①算术运算:加、减、乘、除等。
②关系运算:大于、大于等于、小于、小于等于、等于、不等于等。
③逻辑运算:与、或、非等。
④数据传送:输入、输出、赋值等。
10