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

计算机算法设计与分析小论文摘要:算法是一个系列解决问题的清晰指令,即在有限时间能够对一定规的输入,能够得到所需要的输出。如果一个算法本身是有缺陷的!那么他往往不是这个问题的最佳解决方法,可见一个算法的优劣是通过一定的准则来规定的。通过这学期的对《计算机算法分析设计》这门课程的学习让我们充分的了解到了计算机算法的多样性和复杂性,让我们更加细心和耐心的去对待这门课程。例如甲某要去某个地方旅游,他有很多种方案到旅游地,但是不见的每种方案都是合理最优的!这时就是需要考虑透过一定的算法来得到自己的最优路线。所以可见算法就是以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件,必须遵循软件工程的原则,设计出高效率的程序。一个高效的程序不仅需要编程技巧,更需要合理的数据组织和清晰高效的算法。目前我们将进行常见的算法分析设计策略介绍::直接或间接的调用自身的算法称为递归算法。或者说就是用自己来定义自己,不断调用自己的某一种状态。(1)递归满足2个条件:1)有反复执行的过程(调用自身)   2)有跳出反复执行过程的条件(递归出口):阶乘问题n!=n*(n-1)*(n-2)*...*1(n>0)//阶乘intresult(inti){ intsum=0; if(0==i) return(1); else sum=i*result(i-1); returnsum;}可见一个递归算法都有一个比较特殊的特点,那就是要先处理一些比较特殊的情况再处理递归关系。如上例中如果是0!的话!那么他的阶乘就是1,所以先处理0!这个特殊情况,然后再调用其他的递归关系得到自己想要的阶乘。比如当我们想要求出4!的结果那么我们就需要调用result(3)的结果而result(3)又要调用result(2)的结果!就这样直到得出答案为止。在我们日常,递归算法的出现可以帮助我们解决很多问题,正因为它的:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。:一个分治算法把问题实例划分成若干子实例(多数情况是分成两个),并分别递归地解决每个子实例,然后把这些子实例的解组合起来,得到原问题实例的解。,则很容易解决2)大问题可以分为若干规模小的相同问题3),考虑这样一问题:在一个整数组A[1...n]中,同时寻找最大值和最小值。下面我们来看一下用分治策略:将数组分割成两半,A[1...n/2]和A[(n/2)+1...n],在每一半中找到最大值和最小值,并返回这两个最小值中的最小值及这两个最大值中的最大值。过程 Min-Maxⅰ输入 n个整数元素的数组A[1...n]n为2的幂ⅱ输出 (x,y),A中的最大元素和最小元素ifhigh-low=1thenifA[low]<A[high]thenreturn(A[low],A[high]);elsereturn(A[high],A[low]);endifelsemid==[(low+high)/2];x1==min(low,mid);y1==max(low,mid);x2==min(mid+1,high);