第1章 算法与程序设计简介

《第1章 算法与程序设计简介》由会员分享，可在线阅读，更多相关《第1章 算法与程序设计简介（32页珍藏版）》请在金锄头文库上搜索。

1、主要内容,1.1 算法与算法描述 算法定义 算法描述 1.2 算法复杂性分析 时间复杂度 空间复杂度 1.3 程序设计简介 算法与程序 结构化程序设计,1,Visual FoxPro,1.1 算法与算法描述,1.1.1 算法 算法是程序设计的基础，是计算机科学的核心。 算法是指解决某一问题的运算序列。或者说算法是问题求解过程的运算描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。,2,Visual FoxPro,3. 算法是满足下列特性的指令序列： (1) 确定性 组成算法的每条指令是清晰的，无歧义的。 (2) 可行性 算法中的运算是能够实现的基本运算，每一种运算可在有限的时间内

2、完成。 (3) 有穷性 算法中每一条指令的执行次数有限，执行每条指令的时间有限。 (4) 输入 一个算法有零个或多个输入。 (5) 输出 一个算法至少产生一个量作为输出。,3,Visual FoxPro,4. 选择算法的标准,通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性。其次是算法所需要的存储空间少和执行时间短等。 在实际工程中我们遇到许多高难度计算问题，有的问题在巨型计算机上用普通算法来求解可能要数个月的时间，而且很难找到精确解。但用一个好的算法，即使在普通的个人电脑上，可能只需数秒钟就可以求得解答 。,4,Visual FoxPro,1.1.2 算法描述,

3、1. 描述算法的方式 算法是问题的程序化解决方案。一个问题可以设计不同的算法来求解，同一个算法可以采用不同的形式来表述。 描述算法可以有多种方式，如自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格方式等。 当一个算法使用计算机程序设计语言描述时，就是程序。 本书采用C语言与自然自然语言相结合来描述算法。,5,Visual FoxPro,2. 算法描述举例 【例1.1】 求两个整数a,b(ab)的最大公约数的欧几里德算法: (1) a除以b得余数r;若r=0,则b为所求的最大公约数。 (2) 若r0,以b为a,r为b,继续(1)。 注意到任两整数总存在最大公约数,上述辗转相除过程中

4、余数逐步变小,相除过程总会结束。 欧几里德算法又称为“辗转相除”法，具体描述如下：,6,Visual FoxPro,输入正整数a,b; if(ab */ r=a%b; while(r!=0) a=b;b=r; /* 实施辗转相除 */ r=a%b; printf(最大公约数b);,7,Visual FoxPro,算法复杂性的高低体现运行该算法所需计算机资源的多少。 算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需的计算机资源越少。 计算机资源，最重要的是时间资源与空间资源。 需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。 算法分析是指对算法的执

5、行时间与所需空间的估算，定量给出运行算法所需的时间数量级与空间数量级。,1.2 算法复杂性分析,8,Visual FoxPro,在分析算法时，隐藏细节的数学表示法成为大写O记法 一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总的语句（运算）的数量级决定。 就算法分析而言，一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。,1.2.1 时间复杂度,9,Visual FoxPro,1. 时间复杂度定义,定义： 对于一个数量级为的 算法，如果存在两个正常数c和m，对所有的nm，有 则记

6、作 ，称该算法具有 用 的运行时间，是指当n足够大时，该算法的实际运行时间不会超过的某个常数倍时间。,10,Visual FoxPro,2. 例如程序段： for(k=1;k=n;k+) x=x+y; y=x+y; s=x+y; 每个赋值语句执行频数为n，该算法的数量级为3n； 其计算时间即时间复杂度为O(n)。,11,Visual FoxPro,3. 例如程序段： for(t=1,k=1;k=n;k+) t=t*2; for(j=1;j=t;j+) s=s+j; 内循环赋值语句执行频数 算法的时间复杂度为O( )。,12,Visual FoxPro,4. 算法时间关系： 常见多项式时间算法:

7、 常见指数时间算法: 一般地，当n取值比较大时，在计算机上实现指数时间算法是不可能的，就是比时间复杂度 高的多项式时间算法运行也很困难。,13,Visual FoxPro,5. 两个定理 定理1.1 时间复杂度符号O有以下运算规则： O(f)+O(g)=O(max(f,g) (1.1) O(f)O(g)=O(fg) (1.2) 定理1.2 如果 是n的m次多项式，则 (1.3),14,Visual FoxPro,【例1.3】 估算下列程序段代表算法的时间复杂度。 (1) t=1;m=0; for(k=1;k=n;k+) t=t*2; for(j=t;j=n;j+) m+; 时间复杂度为O(nl

8、ogn).,15,Visual FoxPro,(2) m=0; for(k=1;k=n;k+) for(j=k*k;j=n;j+) m+; 时间复杂度为O( ). 注意(1)、(2)中m+语句的执行次数 的计算，具体见教材详列。,16,Visual FoxPro,一个算法的运行时间，与问题的规模相关，也与输入的数据相关。 对算法的改进与优化，主要表现在有效缩减算法的运行时间与所占空间。 例如把求解某一问题的算法时间从 优化缩减为 就是一个了不起的成果。 或者把求解某一问题的算法时间的系数缩小，例如从2n缩小为3n/2，尽管其时间数量级都是，系数缩小了也是一个算法改进的成果。,17,Visual

9、 FoxPro,算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。 一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。 固定空间需求包括程序代码、常量与结构变量等所占的空间。 可变空间需求包括数组元素所占的空间与运行递归所需的系统栈空间等。 二维或三维数组是空间复杂度高的主要因素之一。 在算法设计时，为降低空间复杂度，要注意尽可能少用高维数组。,1.2.2 空间复杂度,18,Visual FoxPro,1.2.1 算法与程序 1. 基本概念 算法是程序设计的基础，是程序的核心。 程序是某一算法用计算机程序设计语言的具体实现。 具体来说，一个算法使用C语言

10、描述，就是C程序。 上机实践是检验算法与程序的标准。,1.2 程序设计简介,19,Visual FoxPro,2. 程序的内容 一个程序应包括对数据的描述与对运算操作的描述两个方面的内容。 著名计算机科学家沃思(Nikiklaus Wirth)就此提出一个公式： 数据结构算法程序 (1.4) 数据结构是对数据的描述，而算法是对运算操作的描述。,20,Visual FoxPro,1.4 程序实现求两个整数a,b的最大公约数(a,b)的欧几里德算法(见例1.1)，并应用欧几里德算法求n个整数的最大公约数。 解：在欧几里德算法描述基础上进行数据描述即为求整数的最大公约数的程序。 (1) 求两个整数的

11、最大公约数程序实现 设置算法中的相关变量a,b,c,r为长整型变量，即有,3. 程序设计举例,21,Visual FoxPro,/* 求整数a,b的最大公约数（a,b）*/ #include void main() long a,b,c,r; printf(请输入整数a,b: ); scanf(%ld,%ld, /* 输出求解结果 */ ,22,Visual FoxPro,(2) 求n个整数的最大公约数程序实现 对于3个以上整数, 最大公约数有以下性质: (a1,a2,a3)=(a1,a2),a3) (a1,a2,a3,a4)=(a1,a2,a3),a4),. 应用这一性质,要求n个数的最大公

12、约数,先求出前n-1个数的最大公约数b,再求第n个数与b的最大公约数；要求n-1个数的最大公约数,先求出前n-2个数的最大公约数b,再求第n-1个数与b的最大公约数；依此类推。因而，要求n个整数的最大公约数，需应用n-1次欧几里德算法。 为输入与输出方便，把n个整数设置成m数组，m数组与算法中的相关变量a,b,c,r设置为长整型变量，个数n与循环变量k设置为整型。即有,23,Visual FoxPro,/* 求n个整数的最大公约数*/ #include void main() int k,n; long a,b,c,r,m100; printf(请输入整数个数n: ); /* 输入原始数据 *

13、/ scanf(%d, ,24,Visual FoxPro,1.3.2 结构化程序设计 1. 几个概念 不应该把面向对象与面向过程对立起来。 在面向对象程序设计中仍然要用到面向过程的知识。 面向过程程序设计通常由结构化程序设计实现。 任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合而成。 顺序结构、选择结构和循环结构被称为程序设计的三种基本结构，也是结构化程序设计必须采用的结构。,25,Visual FoxPro,2. 结构化程序设计的基本要点 （1） 自顶向下, 逐步求精； （2） 模块化设计； （3） 结构化编码。 自顶向下是指对设计求解的问题要有一个全面的理解，

14、从问题的全局入手，把一个复杂问题分解成若干个相互独立的子问题。 逐步求精是指程序设计的过程是一个渐进的过程。,26,Visual FoxPro,模块化就是把大程序按照功能分为若干个较小的程序。 一个程序是由一个主控模块和若干子模块组成的。主控模块用来完成某些公用操作及功能选择，而子模块用来完成某项特定的功能。,27,Visual FoxPro,去图书市场买书,第一步，有买书的意愿 第二步，确定要买什么书 第三步，确定到哪个书店或图书市场才可以买到需要的书 第四步，坐车或步行到目的书店或目的图书市场 第五步，找到需要的图书 第六步，付款,28,Visual FoxPro,开始,有买书的意愿,确定要买什么书,确定到哪个书店或图书市场 才可以买到需要的书,坐车或步行到目的书店或 目的图书市场,找到需要的书,付款,得到需要的书,结束,29,Visual FoxPro,Visual FoxPro,30,精品课件！,Visual FoxPro,31,精品课件！,上机： 1. 上机通过例1.4。 2. 变通例1.4, 应用求两个整数a,b的最大公约数(a,b)的欧几里德算法求两个整数的最小公倍数a,b,并拓广到求n个整数的最小公倍数. （提示(a,b)*a,b=a*b,a,b,c=a,b,c,） 3. 上机通过习题5。 作业： 2. 3. 5. 6.,32,Visual FoxPro,