计算机算法分析与设计论文正稿.doc

信息技术学院算法设计与分析课程考查论文题目0-1背包问题的算法设计策略对比与分析专业软件工程 班级2007级软件工程学号071164019姓名马进杰任课教师刘维群完成日期2010年6月20日0-(Algorithm)的概念是至关重要的。。。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。一个算法应该具有以下五个重要的特征:有穷性:一个算法必须保证执行有限步之后结束;确切性:算法的每一步骤必须有确切的定义;输入:;输出:。没有输出的算法是毫无意义的;可行性:。计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法=程序》.可见算法在计算机科学界与计算机应用界的地位。。;。(即存储器)资源。。;。。:用怎样的一个量来表达一个算法的复杂性;。让我们从比较两对具体算法的效率开始。:已知不重复且已经按从小到大排好的m个整数的数组A[1..m](为简单起见。还设m=)。[i]=c;。问题1的一个简单的算法是:从头到尾扫描数组A。[i]=c;[i]=c。我们用一个函数Search来表达这个算法:FunctionSearch(c:integer):integer;VarJ:integer;BeginJ:=1;{初始化}{}While(A[i]<c)and(j<m)do        j:=j+1;IfA[j]=cthensearch:=j{}elseSearch:=0;{在数组中找不到等于c的分量}End;。解决问题1的另一个算法利用到已知条件中A已排好序的性质。它首先拿A的中间分量A[m/2][m/2]=c则解已找到。如果A[m/2]>[1],A[2],..,A[m/2-1][1],A[2],...A[m/2-1]中继续查找;如果A[m/2]<[m/2+1],A[m/2+2],..,A[m][m/2+1],A[m/2+2],..,A[m]中继续查找。。。[i]=(即子数组下界大于上界)。。。它可以用函数B_Search来表达:FunctionB_Search(c:integer):integer;VarL,U,I:integer;{U和L分别是要查找的数组的下标的上界和下界}Found:b