算法与程序设计简介.ppt

1 Visual FoxProVisual FoxPro 1.1 算法与算法描述 算法定义 算法描述 1.2 算法复杂性分析 时间复杂度 空间复杂度 1.3 程序设计简介 算法与程序 结构化程序设计 2 Visual FoxProVisual FoxPro 1.1 算法与算法描述 1.1.1 算法 1.1.算法是程序设计的基础，是计算机科学算法是程序设计的基础，是计算机科学 的核心。的核心。 2.2.算法是指解决某一问题的运算序列。或者算法是指解决某一问题的运算序列。或者 说算法是问题求解过程的运算描述，一个说算法是问题求解过程的运算描述，一个 算法由有限条可完全机械地执行的、有确算法由有限条可完全机械地执行的、有确 定结果的指令组成。定结果的指令组成。 3 Visual FoxProVisual FoxPro 3. 算法是满足下列特性的指令序列： (1) (1) 确定性确定性 组成算法的每条指令是清晰的，无歧义的。组成算法的每条指令是清晰的，无歧义的。 (2) (2) 可行性可行性 算法中的运算是能够实现的基本运算，每一种算法中的运算是能够实现的基本运算，每一种 运算可在有限的时间内完成。运算可在有限的时间内完成。 (3) (3) 有穷性有穷性 算法中每一条指令的执行次数有限，执行每条算法中每一条指令的执行次数有限，执行每条 指令的时间有限。指令的时间有限。 (4) (4) 输入输入 一个算法有零个或多个输入。一个算法有零个或多个输入。 (5) (5) 输出输出 一个算法至少产生一个量作为输出。一个算法至少产生一个量作为输出。 4 Visual FoxProVisual FoxPro 4. 选择算法的标准 通常求解一个问题可能会有多种算法可供选择通常求解一个问题可能会有多种算法可供选择 ，选择的主要标准是算法的正确性和可靠性。其次，选择的主要标准是算法的正确性和可靠性。其次 是算法所需要的存储空间少和执行时间短等。是算法所需要的存储空间少和执行时间短等。 在实际工程中我们遇到许多高难度计算问题，在实际工程中我们遇到许多高难度计算问题， 有的问题在巨型计算机上用普通算法来求解可能要有的问题在巨型计算机上用普通算法来求解可能要 数个月的时间，而且很难找到精确解。但用一个好数个月的时间，而且很难找到精确解。但用一个好 的算法，即使在普通的个人电脑上，可能只需数秒的算法，即使在普通的个人电脑上，可能只需数秒 钟就可以求得解答钟就可以求得解答 。 5 Visual FoxProVisual FoxPro 1.1.2 算法描述 1. 描述算法的方式 算法是问题的程序化解决方案。一个问题可以算法是问题的程序化解决方案。一个问题可以 设计不同的算法来求解，同一个算法可以采用不同设计不同的算法来求解，同一个算法可以采用不同 的形式来表述。的形式来表述。 描述算法可以有多种方式，如自然语言方式、描述算法可以有多种方式，如自然语言方式、 流程图方式、伪代码方式、计算机语言表示方式与流程图方式、伪代码方式、计算机语言表示方式与 表格方式等。表格方式等。 当一个算法使用计算机程序设计语言描述时，当一个算法使用计算机程序设计语言描述时， 就是程序。就是程序。 本书采用本书采用C C语言与自然自然语言相结合来描述语言与自然自然语言相结合来描述 算法。算法。 6 Visual FoxProVisual FoxPro 2. 算法描述举例 【例例1.11.1】 求两个整数求两个整数a,b(aa,b(ab)b)的最大公约的最大公约 数的欧几里德算法数的欧几里德算法: : (1) a (1) a除以除以b b得余数得余数r;r;若若r=0,r=0,则则b b为所求的为所求的 最大公约数。最大公约数。 (2) (2) 若若r0,r0,以以b b为为a,ra,r为为b,b,继续继续(1)(1)。 注意到任两整数总存在最大公约数注意到任两整数总存在最大公约数, ,上述辗转相上述辗转相 除过程中余数逐步变小除过程中余数逐步变小, ,相除过程总会结束。相除过程总会结束。 欧几里德算法又称为欧几里德算法又称为“辗转相除辗转相除”法，具体描法，具体描 述如下：述如下： 7 Visual FoxProVisual FoxPro 输入正整数输入正整数a,ba,b; ; if(aif(ab */ab */ r=r=a%ba%b; ; while(rwhile(r!=0)!=0) a= a=b;bb;b=r; /* =r; /* 实施实施“ “辗转相除辗转相除“ */“ */ r= r=a%ba%b; ; printfprintf( (最大公约数最大公约数b);b); 8 Visual FoxProVisual FoxPro 算法复杂性的高低体现运行该算法所需计算机资算法复杂性的高低体现运行该算法所需计算机资 源的多少。源的多少。 算法的复杂性越高，所需的计算机资源越多；反算法的复杂性越高，所需的计算机资源越多；反 之，算法的复杂性越低，所需的计算机资源越少之，算法的复杂性越低，所需的计算机资源越少 。 计算机资源，最重要的是时间资源与空间资源。计算机资源，最重要的是时间资源与空间资源。 需要计算机时间资源的量称为时间复杂度，需要需要计算机时间资源的量称为时间复杂度，需要 计算机空间资源的量称为空间复杂度。计算机空间资源的量称为空间复杂度。 算法分析是指对算法的执行时间与所需空间的估算法分析是指对算法的执行时间与所需空间的估 算，定量给出运行算法所需的时间数量级与空间算，定量给出运行算法所需的时间数量级与空间 数量级。数量级。 1.2 算法复杂性分析 9 Visual FoxProVisual FoxPro 在分析算法时，隐藏细节的数学表示法成为大写在分析算法时，隐藏细节的数学表示法成为大写O O记记 法法 一个算法的时间复杂度是指算法运行所需的时间。一个算法的时间复杂度是指算法运行所需的时间。 一个算法的运行时间取决于算法所需执行的语句（一个算法的运行时间取决于算法所需执行的语句（ 运算）的多少。算法的时间复杂度通常用该算法执运算）的多少。算法的时间复杂度通常用该算法执 行的总的语句（运算）的数量级决定。行的总的语句（运算）的数量级决定。 就算法分析而言，一条语句的数量级即执行它的频就算法分析而言，一条语句的数量级即执行它的频 数，一个算法的数量级是指它所有语句执行频数之数，一个算法的数量级是指它所有语句执行频数之 和。和。 1.2.1 时间复杂度 10 Visual FoxProVisual FoxPro 1. 时间复杂度定义 定义：定义： 对于一个数量级为的对于一个数量级为的 算法算法 ，如果存在两个正常数，如果存在两个正常数c c和和mm，对所有的，对所有的 nmnm，有，有 则记作则记作 ，称该算法具有，称该算法具有 用用 的运行时间，是指当的运行时间，是指当n n足够大足够大 时，该算法的实际运行时间不会超过的时，该算法的实际运行时间不会超过的 某个常数倍时间。某个常数倍时间。 11 Visual FoxProVisual FoxPro 2. 例如程序段：例如程序段： for(kfor(k=1;k void main()void main() long long a,b,c,ra,b,c,r; ; printfprintf(“(“请输入整数请输入整数a,ba,b: “);: “); scanf(“%ld,%ld“, /* ); /* 输入整数输入整数a,ba,b */ */ printf(“(%ld,%ld)“,a,bprintf(“(%ld,%ld)“,a,b);); if(aif(ab*/ab*/ r= r=a%ba%b; ; while(rwhile(r!=0)!=0) a= a=b;bb;b=r; /* =r; /* 实施实施“ “辗转相除辗转相除“ */“ */ r= r=a%ba%b; ; printfprintf(“=%ld(“=%ldn“,bn“,b); /* ); /* 输出求解结果输出求解结果 * */ / 23 Visual FoxProVisual FoxPro (2) 求n个整数的最大公约数程序实现 对于3个以上整数, 最大公约数有以下性质: (a1,a2,a3)=(a1,a2),a3) (a1,a2,a3,a4)=(a1,a2,a3),a4),. 应用这一性质,要求n个数的最大公约数,先求出 前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设置为整型。即有 24 Visual FoxProVisual FoxPro /* 求n个整数的最大公约数*/ #include void main() int k,n; long a,b,c,r,m100; printf(“请输入整数个数n: “); /* 输入原始数据 */ scanf(“%d“, printf(“请依次输入%d个整数: “,n); for(k=0;kb*/ r=a%b; while(r!=0) a=b;b=r; /* 实施“辗转相除“ */ r=a%b; printf(“(%ld“,m0); /* 输出求解结果 */ for(k=1;k=n-1;k+) printf(“,%ld“,mk); printf(“)=%ldn“,b); 25 Visual FoxProVisual FoxPro 1.3.2 结构化程序设计 1. 几个概念 不应该把面向对象与面向过程对立起来。不应该把面向对象与面向过程对立起来。 在面向对象程序设计中仍然要用到面向过程的在面向对象程序设计中仍然要用到面向过程的 知识。知识。 面向过程程序设计通常由结构化程序设计实现面向过程程序设计通常由结构化程序设计实现 。 任何简单或复杂的算法都可以由顺序结构、选任何简单或复杂的算法都可以由顺序结构、选 择结构和循环结构这三种基本结构组合而成。择结构和循环结构这三种基本结构组合而成。 顺序结构、选择结构和循环结构被称为程序设顺序结构、选择结构和循环结构被称为程序设 计的三种基本结构，也是结构化程序设计必须计的三种基本结构，也是结构化程序设计必须 采用的结构采用的结构。 26 Visual FoxProVisual FoxPro 2. 结构化程序设计的基本要点 （1 1） 自顶向下自顶向下, , 逐步求精；逐步求精； （2 2） 模块化设计；模块化设计； （3 3） 结构化编码。结构化编码。 自顶向下是指对设计求解的问题要有一个全面的自顶向下是指对设计求解的问题要有一个全面的 理解，从问题的全局入手，把一个复杂问题分解理解，从问题的全局入手，把一个复杂问题分解 成若干个相互独立的子问题。成若干个相互独立的子问题。 逐步求精是指程序设计的过程是一个渐进的过程逐步求精是指程序设计的过程是一个渐进的过程 。 27 Visual FoxProVisual FoxPro 模块化就是把大程序按照功能分为若干个较小的程模块化就是把大程序按照功能分为若干个较小的程 序。序。 一个程序是由一个主控模块和若干子模块组成的。一个程序是由一个主控模块和若干子模块组成的。 主控模块用来完成某些公用操作及功能选择，而子主控模块用来完成某些公用操作及功能选择，而子 模块用来完成某项特定的功能。模块用来完成某项特定的功能。 主控模块学院 子模块1子模块2 子模块11子模块12子模块21子模块22 子模块3 子模块23 28 Visual FoxProVisual FoxPro 去图书市场买书 第一步，有买书的意愿 第二步，确定要买什么书 第三步，确定到哪个书店或图书市场才可 以买到需要的书 第四步，坐车或步行到目的书店或目的图 书市场 第五步，找到需要的图书 第六步，付款 29 Visual FoxProVisual FoxPro 开始 有买书的意愿 确定要买什么书 确定到哪个书店或图书市场 才可以买到需要的书 坐车或步行到目的书店或 目的图书市场 找到需要的书 付款 得到需要的书 结束 30 Visual FoxProVisual FoxPro 上机： 1. 1. 上机通过例上机通过例1.41.4。 2. 2. 变通例变通例1.