第2章算法.ppt

第二章
本章要点
算法的概念
算法的特性
算法的表示
主要内容
算法的概念
简单算法举例
算法的特性
算法的表示
结构化程序设计方法
引言
程序伴随着计算机的诞生而产生。而在程序设计时,首先需要确定待求解问题的算法,然后才能进行程序设计。简单问题的算法比较容易,而复杂问题的算法往往一时难以确定。本章的目的在于使读者了解算法的概念、算法的表示方法、特征以及常用算法的类型;逐步掌握如何对问题进行分析,建立数学模型,以至确定算法和解题步骤。
因此,瑞士科学家Niklaus Wirth提出:
程序=算法+数据结构
算法是程序的灵魂

什么是算法
算法:是为解决某一应用问题而采用的方法和步骤
不同问题有不同算法,同一问题也可有不同算法,
择优而用。
1、计算机算法的分类
(1)数值计算算法:求数值解,根据数学知识找出让计算机计算的方法,研究得比较深入,算法比较成熟。
(2)非数值计算算法:范围广泛,只有少数问题(排序、查找等)的算法研究得比较深入,大部分问题的算法需程序员临时考虑。
2、算法学习
(1)课程中结合语法学习介绍典型算法,不系统讲解算法。
(2)学习中注意算法的收集和掌握(非常重要!)
本章介绍算法的概念、特点和表示等。
简单算法举例
一、简单算法举例
求5!=1×2×3×4×5
1、一般考虑:将1、2、3、4、5依次乘到累乘器p(存放乘积的变量)上——不便于推广。
2、便于推广的计算机算法。设计两个变量——p(代表被乘数及累乘器)和i(乘数)(P15)。
算法如下:
算法开始
S1: 1→p
S2: 2→i
S3: p*i→p
S4: i+1→i
S5: 如果i小于等于5,返回S3;否则到下一步
S6: 输出结果(p的值)
算法结束
问题:如果改成求1×3×5×7×9×11,算法应该怎样设计?
,输出判断结果。
闰年的条件:①能被4整除但不能被100整除,或者②能被100又能被400整除的年份。
算法如下:
S1: 2000→y
S2: 若y ①能被4整除但不能被100整除,或者
②能被400整除,输出“y是闰年”信息
否则,输出“y不是闰年”信息
S3: y+1→y
S4: 如果y小于等于2500,返回S2;否则算法结束
求1-1/2+1/3-1/4+…+1/99-1/100变量设计:分母deno、项值term、和sum、符号sign算法开始S1: 1→sign;0→sum;1→denoS2: sign*(1/deno)→termS3: sum+term→sumS4: (-1)*sign→signS5: deno+1→denoS6: 如果deno小于等于100,返回S2;否则到下一步S7: 输出结果(sum的值)算法结束