02-算法与程序设计

江苏大学多媒体教学课件 计算机软件技术基础第二章 算法与程序设计基础江苏大学电气信息工程学院 2014 年 02月18:02:06

18:02:06

主要内容

NO: 2

第一节、算法分析第二节、程序设计

18:02:06

第一节 算法分析算法和数据结构是程序的两个重要方面， 这二者的有机结合就构成了程序。

NO: 3

通常用执行算法时所占用的空间大小和消 用数学符号“O”表示复杂度的数量级 耗时间的多少作为衡量算法优劣的标准。 例如： O(1) 常量级 即算法的分析主要包含时间和空间两个方 O(n),O(n2),...,O(nk) 多项式级 面，称为时间复杂度和空间复杂度。 O(log2n),O(nlog2n) 对数级 O(2n),O(en) 指数级

18:02:06

1、时间复杂度

NO: 4

算法中某一具体语句在算法的运行过程中执 行的次数即为该语句的频度，记做F(n); 时间复杂度是以算法中频度最大的语句来度 量的，可记做T(n) = O(F(n))。

for (k=0; k<n; k++) for (j=0; j<n; j++) for (i=0; i<n; i++) a[i] = 1;

18:02:06

2、空间复杂度

NO: 5

实现算法可能需占用的存储空间一般有： 1 ) 指令、常数和系统变量所占用的存储空间； 2) I/O数据所占用的存储空间； 3) 算法执行过程中所需的辅助空间。 算法的空间复杂度分析，是指对该算法在执 行过程中所需辅助空间大小的分析。 空间复杂度也用O(n)表示。 常见的空间复杂度有：O(1)、O(n)、O(n2)、O(n3)

18:02:06

3、算法的特性与描述

NO: 6

(1) 算法特性 算法是对特定问题的求解步骤的一种描述， 是指令的有限序列。 作为算法，有以下几个基本特性： 1 )有穷性，每条指令执行的次数与时间都 是有限的，必须在若干步之后终止； 2 )确定性，每条指令的含义明确，不能存 在二义，即在相同条件下的结果唯一； 3 )可行性，算法所描述的操作可以通过有 限的基本操作实现； 4)输 入，算法应当有0个或多个输入； 5)输 出，算法也应当有1个或多个输出。

18:02:06

NO: 7

(2)算法描述 算法描述即用某种描述语言或方法来表达算 法，或选用某一种高级语言在计算机上实现。

常用的算法描述语言有： 1)自然语言描述，即用人们日常使用的语言 来描述算法； 2)程序流程图描述，即用一组几何图形表示 各种类型的操作，在图形上用扼要的文字和符号 表示具体的操作，并用带有箭头的流线表示操作 的先后次序。

18:02:06

常用流程图符号起止框 I/0框 处理框 判断框 流线标号

NO: 8

模块名I/0内容

预定义或操作 单文档 手工输入 处理/存储

内部存储与操作 多文档 延时 显示 磁盘 阵列

需进行的操作关系/逻辑 表达式

连接符

磁带

18:02:06

NO: 9

3 ) 类 PASCAL 语 言 描 述 ， 用 一 种 类 似 于 PASCAL 语

法规则的程序语言来描述算法，在算 法中可随意注释，无须考虑是否合乎语法约束； 4 )高级语言描述，用严谨的某一高级语 言的语法和函数描述算法。

18:02:06

NO: 10

算法还应具有如下性能指标：

1)正确性 2)可读性 3)健壮性 4)高效性

18:02:06

第二节

程序设计基础迭代法递推法 递归法 穷举法 分治法

NO: 11

贪心法回溯法

18:02:06

1、迭代法迭代法一般用于求方程的近似根的算法设计。

NO: 12

例如：对于方程f(x) = 0,通过相应的数学推导可以得到 x = g(x),则其求根过程为： 1)将方程的任意一个近似根赋给变量x0 ; 2 )将 x0 的值保存于变量 x1 ,然后计算 g(x1) ,并将结果 存于变量x0 ; 3)当x0 与x1的差的绝对值还小于指定的精度( E )要求 时，重复第2步； 如若方程有根且用上述方法计算出来的近似根序列收敛， 则按上述方法求得的x0就是方程的根。

18:02:06

NO: 13 使用迭代法求根时应注 意如下两种的情况：

上述算法用C程序的形式如下：

{ x0 = 初始近似值；do { x1 = x0; x0 = g(x1);

1)若方程无解，算法 求出的近似根序列就不收敛 ，迭代过程会变成死循环。 故在使用迭代算法前应先考 察方程是否有解，并在程序 中对迭代的次数给予限制；

2)方程虽然有解，但 迭代公式选择不当，或迭代 } while (fabs(x0-x1)>E); 的初始近似根选择不合理， 也会导致迭代失败。 /* E为求值的精度 */

printf(“该方程的近似根为：%f\n”,x0); }

18:02:06

2、递推法

NO: 14

递推法是利用问题本身所具有的一种递推关 系求问题解的一种方法。 对于该法，设要求问题规模为N的解，当N=1 时，解或为已知，或能非常方便地得到解。能采 用递推法构造算法的问题必须有递推性质，当得 到问题规模为 i-1 的解后，由问题的递推性质， 能根据已求得的规模为 1 , 2 , … , i-1 的一系列 解，构造出问题规模为 i 的解。这样，算法可从 i=0 或 i=1 出发，重复地由已知规模为 i-1 的解， 通过递推，获得规模为i的解，直至得到规模为 N 的解。

18:02:06

NO: 15

例如：可以使用“递推”法输出费波那契 (Fibonacci)数列前20项的值。费波那契数 列是这样一个数列：其第0个元素为0,第1个 元素为1,其后的所有元素的值为其前面两个 元素值之和，即：{0,1,1,2,3,5,8,13 ,21,34,55,…… }。 该数列的递推过程可用如下公式表示为：

f (0 )= 0 ;f (1 )= 1 ;

f(n)=f(n-2)+f(n-1) (n>1);

18:02:06

NO: 16

输出斐波那契数列前20项的C程序片段如下：

int f[20]; f[0] = 0; f[1] = 1;

/* 用数组来存储数列的前20项 */

for (int i=0; i<20; i++){ if (i > 1) f[i] = f[i-2] + f[i-1]; /* 递推公式 */ pr

intf(“Fibonacci[%d] = %d\n”,i,f[i]); }采用递推法的前提是必须要知道一个初始值 ，并且可用适当的公式来描述相临几个数据项的 关系，并根据这个关系来进行推导。