算法与程序设计 郑宗汉郑晓明

《算法与程序设计 郑宗汉郑晓明》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计教材：算法设计与分析作者：郑宗汉,郑晓明清华大学出版社,2005主讲教师:韩爱丽计算机系统中的任何软件都是按特定算法实现的。算法性能的好坏直接决定了软件性能的优劣。故算法的设计与分析是计算机科学与技术的一个核心问题。用什么方法设计算法?如何判定一个算法的性能?所设计的算法需要多少运行时间和存储空间?第1章算法的基本概念1.1引言1.2算法的时间复杂性1.3算法的时间复杂性分析1.4算法的空间复杂性1.5最优算法1.1引言20世纪50s,欧几里德描述了求两个数的最大公因子的过程,该过程称为欧几里德算法。自此有了算法术

2、语。算法1欧几里德算法{辗转相除法}输入:正整数m,n输出:m,n的最大公因子1.inteuclid(intm,intn)2.{intr;3.do{r=m%n;m=n;n=r;}while(r)4.returnn;}定义1.1算法是求解某一特定问题的一组有穷规则的集合。DonaldE.Knuth给出的(确)算法特征:(1)有限性:算法在执行有限步后终止。(2)确定性:算法的每一步都有精确定义,每个动作都是清晰、无歧义的。(3)输入:算法有0个或多个输入。(4)输出:算法有一个或多个输出。(5)能行性:指算法中有待实现的运算都是基

3、本运算。1.算法的定义及特征说明：实际应用中不仅要求算法的步骤有限,还要求运行这些步骤所花费的时间可以接受。比如,步骤有限但需数年。算法的设计过程包括:对问题需求的说明、数学模型的拟制、算法的详细设计、正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。本书着重讲串行算法的设计与分析。穷举法指从有限集合中逐一列举集合的所有元素,对每个元素逐一判断和处理,从而找出问题的解。例1.百鸡问题鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一。百钱买百鸡,问鸡翁、母、雏各几何?令a:公鸡数,b:母鸡数,c:小鸡数约束方程:a+b+c

4、=100;5a+3b+c/3=100;c%3=02.算法设计实例:穷举法法1.a,b,c的取值范围为0~100,n钱买n鸡。算法1.1百鸡问题输入:三种鸡的购买总数n输出:解的数目k.公,母,雏的只数g[],m[],s[]voidchi_q(intn,intk,intg[],intm[],ints[]){inta,b,c;k=0;for(a=0;a<=n;a++)for(b=0;b<=n;b++)for(c=0;c<=n;c++)if((a+b+c==n)&&(5a+3b+c/3==n)&&(c%3==0)){g[k]=a;m[

5、k]=b;s[k]=c;k++;}}执行时间:外循环:n+1次中间循环:(n+1)(n+1)次内循环:(n+1)(n+1)(n+1)次当n=100时,内循环体的执行次数大于100万次。法2.a:0~n/5,b:0~n/3,c=n-a-b算法1.2改进的百鸡问题输入:三种鸡的购买总数n输出:解数目k.公,母,雏只数g[],m[],s[]voidch_q(intn,intk,intg[],intm[],ints[]){inta,b,c,i,j;k=0;i=n/5;j=n/3;for(a=0;a<=i;a++)for(b=0;

6、b<=j;b++){c=n-a-b;if((5a+3b+c/3==n)&&(c%3==0)){g[k]=a;m[k]=b;s[k]=c;k++;}}}执行时间:外循环:n/5+1次内循环:(n/5+1)(n/3+1)次当n=100时,内循环体的执行次数为2134=714,仅为100万次的万分之七。假定内循环体执行1次需1sn=100时,算法1:100万次,1s算法2:714次,714sn=10000时,算法1:11天零13小时算法2:6.7s百鸡问题的例子告诉我们:对于某些特定问题,在规模较小时,穷举法往往是一种

7、简单有效的方法,但随着问题规模的增大,采用穷举法的运行时间往往是不可接受的。例2.货郎担问题(旅行商问题,TSP)给定一个赋权有向图G=,其中V={1,2,…,n}表示顶点,边(i,j)E表示顶点i到j的距离,TSP问题求一条从某顶点出发、经过其它每个顶点一次且仅一次、再回到出发顶点的长度最短的回路。用邻接矩阵C表示各个城市之间的距离,称为费用矩阵;用数组T表示售货员的旅行路线。每条路线对应于城市的一个排列,n个城市共有n!个排列,采用穷举法逐一计算每条路线的费用,从中找出费用最小的路线。算法2穷举法版本的货郎担问题

8、输入:城市个数n,费用矩阵c[][]输出:旅行路线t[],最小费用minvoidTSP(intn,float&min,intt[],floatc[][]){intp[n],i=1;floatcost;min=MaxFloatNum;while(i<=n!){产生