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

常用算法与程序设计11.1算法与算法描述算法定义算法描述1.2算法复杂性分析时间复杂度空间复杂度1.3程序设计简介算法与程序结构化程序设计常用算法与程序设计21.1算法与算法描述1.1.1算法1.算法是程序设计的基础，是计算机科学的核心。2.算法是指解决某一问题的运算序列。或者说算法是问题求解过程的运算描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。常用算法与程序设计33.算法是满足下列特性的指令序列：(1)确定性组成算法的每条指令是清晰的，无歧义的。(2)可行性算法中的运算是能够实现的基本运算，每一种运算可在有限的时间内完成。(3)有穷性算法中每一条指令的执行次数有限，执行每条指令的时间有限。(4)输入一个算法有零个或多个输入。(5)输出一个算法至少产生一个量作为输出。常用算法与程序设计44.选择算法的标准通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性。其次是算法所需要的存储空间少和执行时间短等。在实际工程中我们遇到许多高难度计算问题，有的问题在巨型计算机上用普通算法来求解可能要数个月的时间，而且很难找到精确解。但用一个好的算法，即使在普通的个人电脑上，可能只需数秒钟就可以求得解答。常用算法与程序设计51.1.2算法描述1.描述算法的方式算法是问题的程序化解决方案。一个问题可以设计不同的算法来求解，同一个算法可以采用不同的形式来表述。描述算法可以有多种方式，如自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格方式等。当一个算法使用计算机程序设计语言描述时，就是程序。本书采用C语言与自然自然语言相结合来描述算法。常用算法与程序设计62.算法描述举例【例1.1】求两个整数a,b(ab)的最大公约数的欧几里德算法:(1)a除以b得余数r;若r=0,则b为所求的最大公约数。(2)若r≠0,以b为a,r为b,继续(1)。注意到任两整数总存在最大公约数,上述辗转相除过程中余数逐步变小,相除过程总会结束。欧几里德算法又称为“辗转相除”法，具体描述如下：常用算法与程序设计7输入正整数a,b;if(ab){c=a;a=b;b=c;}/*交换a,b,确保ab*/r=a%b;while(r!=0){a=b;b=r;/*实施辗转相除*/r=a%b;}printf(最大公约数b);常用算法与程序设计8算法复杂性的高低体现运行该算法所需计算机资源的多少。算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需的计算机资源越少。计算机资源，最重要的是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。算法分析是指对算法的执行时间与所需空间的估算，定量给出运行算法所需的时间数量级与空间数量级。1.2算法复杂性分析常用算法与程序设计9在分析算法时，隐藏细节的数学表示法成为大写O记法一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总的语句（运算）的数量级决定。就算法分析而言，一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。1.2.1时间复杂度常用算法与程序设计101.时间复杂度定义定义：对于一个数量级为的算法，如果存在两个正常数c和m，对所有的n≥m，有则记作，称该算法具有用的运行时间，是指当n足够大时，该算法的实际运行时间不会超过的某个常数倍时间。)()(ngcnf)(nf))(()(ngOnf))((ngO常用算法与程序设计112.例如程序段：for(k=1;k=n;k++){x=x+y;y=x+y;s=x+y;}每个赋值语句执行频数为n，该算法的数量级为3n；其计算时间即时间复杂度为O(n)。常用算法与程序设计123.例如程序段：for(t=1,k=1;k=n;k++){t=t*2;for(j=1;j=t;j++)s=s+j;}内循环赋值语句执行频数算法的时间复杂度为O()。nn22)12(2)12(22222nnn2常用算法与程序设计134.算法时间关系：常见多项式时间算法:常见指数时间算法:一般地，当n取值比较大时，在计算机上实现指数时间算法是不可能的，就是比时间复杂度高的多项式时间算法运行也很困难。)()()log()()(log)1(32nOnOnnOnOnOO)()!()2(nnnOnOO)log(nnO常用算法与程序设计14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)0111)(ananananfmmmm)()(mnOnf常用算法与程序设计15【例1.3】估算下列程序段代表算法的时间复杂度。(1)t=1;m=0;for(k=1;k=n;k++){t=t*2;for(j=t;j=n;j++)m++;}时间复杂度为O(nlogn).常用算法与程序设计16(2)m=0;for(k=1;k=n;k++)for(j=k*k;j=n;j++)m++;时间复杂度为O().注意(1)、(2)中m++语句的执行次数的计算，具体见教材详列。nnnn常用算法与程序设计17一个算法的运行时间，与问题的规模相关，也与输入的数据相关。对算法的改进与优化，主要表现在有效缩减算法的运行时间与所占空间。例如把求解某一问题的算法时间从优化缩减为就是一个了不起的成果。或者把求解某一问题的算法时间的系数缩小，例如从2n缩小为3n/2，尽管其时间数量级都是，系数缩小了也是一个算法改进的成果。)(2nO)log(nnO常用算法与程序设计18算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。固定空间需求包括程序代码、常量与结构变量等所占的空间。可变空间需求包括数组元素所占的空间与运行递归所需的系统栈空间等。二维或三维数组是空间复杂度高的主要因素之一。在算法设计时，为降低空间复杂度，要注意尽可能少用高维数组。1.2.2空间复杂度常用算法与程序设计191.2.1算法与程序1.基本概念算法是程序设计的基础，是程序的核心。程序是某一算法用计算机程序设计语言的具体实现。具体来说，一个算法使用C语言描述，就是C程序。上机实践是检验算法与程序的标准。1.2程序设计简介常用算法与程序设计202.程序的内容一个程序应包括对数据的描述与对运算操作的描述两个方面的内容。著名计算机科学家沃思(NikiklausWirth)就此提出一个公式：数据结构＋算法＝程序(1.4)数据结构是对数据的描述，而算法是对运算操作的描述。常用算法与程序设计211.4程序实现求两个整数a,b的最大公约数(a,b)的欧几里德算法(见例1.1)，并应用欧几里德算法求n个整数的最大公约数。解：在欧几里德算法描述基础上进行数据描述即为求整数的最大公约数的程序。(1)求两个整数的最大公约数程序实现设置算法中的相关变量a,b,c,r为长整型变量，即有3.程序设计举例常用算法与程序设计22/*求整数a,b的最大公约数（a,b）*/#includestdio.hvoidmain(){longa,b,c,r;printf(请输入整数a,b:);scanf(%ld,%ld,&a,&b);/*输入整数a,b*/printf((%ld,%ld),a,b);if(ab){c=a;a=b;b=c;}/*交换a,b,确保ab*/r=a%b;while(r!=0){a=b;b=r;/*实施辗转相除*/r=a%b;}printf(=%ld\n,b);/*输出求解结果*/}常用算法与程序设计23(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/*求n个整数的最大公约数*/#includestdio.hvoidmain(){intk,n;longa,b,c,r,m[100];printf(请输入整数个数n:);/*输入原始数据*/scanf(%d,&n);printf(请依次输入%d个整数:,n);for(k=0;k=n-1;k++){printf(\n请输入第%d个整数：,k+1);scanf(%ld,&m[k]);}b=m[0];for(k=1;k=n-1;k++)/*控制应用n-1次欧几里德算法*/{a=m[k];if(ab){c=a;a=b;b=c;}/*交换a,b,确保ab*/r=a%b;while(r!=0){a=b;b=r;/*实施辗转相除*/r=a%b;}}printf((%ld,m[0]);/*输出求解结果*/for(k=1;k=n-1;k++)printf(,%ld,m[k]);printf()=%ld\n,b);}常用算法与程序设计251.3.2结构化程序设计1.几个概念不应该把面向对象与面向过程对立起来。在面向对象程序设计中仍然要用到面向过程的知识。面向过程程序设计通常由结构化程序设计实现。任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合而成。顺序结构、选择结构和循环结构被称为程序设计的三种基本结构，也是结构化程序设计必须采用的结构。常用算法与程序设计262.结构化程序设计的基本要点（1）自顶向下,逐步求精；（2）模块化设计；（3）结构化编码。自顶向下是指对设计求解的问题要有一个全面的理解，从问题的全局入手，把一个复杂问题分解成若干个相互独立的子问题。逐步求精是指程序设计的过程是一个渐进的过程。常用算法与程序设计27模块化就是把大程序按照功能分为若干个较小的程序。一个程序是由一个主控模块和若干子模块组成的。主控模块用来完成某些公用操作及功能选择，而子模块用来完成某项特定的功能。主控模块学院子模块1子模块2子模块11子模块12子模块21子模块22子模块3子模块23常用算法与程序设计28去图书市场买书第一步，有买书的意愿第二步，确定要买什么书第三步，确定到哪个书店或图书市场才可以买到需要的书第四步，坐车或步行到目的书店或目的图书市场第五步，找到需要的图书第六步，付款常用算法与程序设计29开始有买书的意愿确定要买什么书确定到哪个书店或图书市场才可以买到需要的书坐车或步行到目的书店或目的图书市场找到需要的书付款得到需要的书结束VisualFoxPro30精品课件！VisualFoxPro31精品课件！常用算法与程序设计32上机：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.