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

1、计算机算法设计与分析小论文摘要：算法是一个系列解决问题的淸晰指令,即在有限时间内能够对一定规范的输入,能够得到所 需要的输出。如果一个算法本身是有缺陷的!那么他往往不是这个问题的最佳解决方法,可见 一个算法的优劣是通过一定的准则来规左的。通过这学期的对讣算机算法分析设讣这门 课程的学习让我们充分的了解到了讣算机算法的多样性和复杂性，让我们更加细心和耐心的 去对待这门课程。例如甲某要去某个地方旅游,他有很多种方案到旅游地,但是不见的每种方 案都是合理最优的!这时就是需要考虑透过一沱的算法来得到自己的最优路线。所以可见算 法就是以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件，

2、必须 遵循软件工程的原则，设汁出高效率的程序。一个高效的程序不仅需要编程技巧，更需要合 理的数据组织和淸晰高效的算法。目前我们将进行常见的算法分析设计策略介绍：1递归算法1.1递归算法介绍：直接或间接的调用自身的算法称为递归算法。或者说就是用自己来左义自己,不断调用自 己的某一种状态。12递归算法满足的条件(1)递归满足2个条件：1)有反复执行的过程(调用自身)2)有跳岀反复执行过程的条件(递归出口)13递归例子递归例子：阶乘问题n! = n * (n-l) * (n-2) * .* l(n>O)阶乘int result(int i)int SUnI 二 0;if (0 = i)retu

3、rn (1);elseSUm = i * result(il);return sum;可见一个递归算法都有一个比较特殊的特点,那就是要先处理一些比较特殊的 情况再处理递归关系。如上例中如果是0!的话！那么他的阶乘就是匚所以先处 理0!这个特殊情况，然后再调用其他的递归关系得到自己想要的阶乘。比如当 我们想要求出4!的结果那么我们就需要调用result (3)的结果而result (3) 乂要 调用result (2)的结果！就这样直到得出答案为止。在我们日常,递归算法的岀现可以帮助我们解决很多问题,正因为它的：结构清 晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、 调

4、试程序带来很大方便。2 分治算法21分治算法介绍：一个分治算法把问题实例划分成若干子实例(多数情况是分成两个)，并分别递归地解 决每个子实例，然后把这些子实例的解组合起来，得到原问题实例的解。2.2分治算法的特性D规模小，则很容易解决2) 大问题可以分为若干规模小的相同问题3) 利用子问题的解可以合并成该问题的解2.3分治算法的遇到问题为了阐明这个方法，考虑这样一问题：在一个整数组A1.n中，同时寻找最大值和最小值。 下面我们来看一下用分治策略：将数组分割成两半，A仁.n2和A(n+1.n,在每一半 中找到最大值和最小值，并返回这两个最小值中的最小值及这两个最大值中的最大值。if high-l

5、ow=l then过程Min-MaXi输入n个整数元素的数组A1 .nn为2的幕ii输出(,y), A中的最大元素和最小元素if Alow<Ahigh then return (AlowzAhigh); elsereturn (Ahigh,Alow);end ifelsemid = = (low+high)2;xl = = min(low,mid);yl = = max(lowzmid);x2= = min(mjd + lzhigh);y2= = min(mid + lzhgh);x= = mi n( ×lzx2)y= = max(yl,y2)return (XZy)Gnd i

6、f可见当我们在一个数组中如何同时选择最大最小值时，分治算法时一个不错半 选择。如上例中所示，我们把一个数组分成了 IOW部分和high部分两个较小当 部分，然后求出他们的mid。用IoW high部分分别和mid比较把其最大最小 值进行存放，最后再比较存放数当最大最小值。我们考虑的例子中只考虑了时2 的幕的情况。而且分成的子问题都是相互独立的，如果子问题不独立而是出现重复子问题 那往往我们选择的不是分治算法而是采用动态规划算法求解更加便利。3 动态规划：3.1动态规划介绍动态规划算法，就是递推+重复子问题。该算法效率主要与重复子问题的处理有关。动态 规划算法与分治法类似,其基本思想也是将待求解

7、问题分解成若个子问题，先求解子问题, 然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题, 经分解得到子问题往往不是互相独立的.典型的题目有陪审团、最大公共子串问题,流水作业调度，矩阵乘法背包问题和背包问题32动态规划介绍例子例：最大公共子串问题这个是动态规划的基础题目。这个问题，不妨设第一个串为a,长度为n,第二个串为b, 长度那么最长的子序列长度为f (n,m)当 an=amlf(n,m)=1 +f(n-1 Im-I)否则 f(n,m)=max(f(n-1),f(m-1)同时建立一个存储计算过的f (XIy)的矩阵，如果计算过了就直接使用。2.对已集装箱问题中

8、的背包问题和0-1背包问题的区别。背包问题可以将一个整体进行拆分 存放，而0-1背包问题必须存放的是一个整体！直到出现最大价值为之。比如当c=50而我这有三个小箱a.b.c重量分别是10 .20.30而价值分别对应60.100.120 !这 时当我们考虑装箱时！用背包问题的思想，不管是背包还是0-1背包都要体现价值最大化。 在这使用背包问题这价值为60+100+80分别是装了 a,b,和C的20重量！当我们考虑用0-1 背包时最大价值为100+120分别装了 b,c。这就是两者最大价值的实现和不同点。4 贪心算法：是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上 加

9、以考虑，他所做岀的仅是在某种意义上的局部最优解。该算法的应用：最小生成树，最短路径，哈夫曼编码活动时间安排的问题设有N个活动时间集合，每个活动都要使用同一个资源，比如说会议场，而且同一时间内 只能有一个活动使用，每个活动都有一个使用活动的开始Si和结朿时间fi,即他的使用区间 为(SiZfi),现在要求你分配活动占用时间表，即哪些活动占用该会议室，哪些不占用，使得 他们不冲突，要求是尽可能多的使参加的活动最大化，即所占时间区间最大化！1. #include><iostream>2. UsingnamQspagstd;3.3. VOidGreedyChOOSe(intlenji

10、nts,int*fjbool*flag);56 intmain(intargcj7 char*8. argv)9. 10. intsll=l,3,5j35,6,8,8,2j12;11. intf11=4,5j6j7,8,9,1,11,12j13,14;12.12. boolmarkll=;14.13. GreedyChoose(11,SJfJmark);14. for(inti;i<ll;i+)15. if(marki)18 cout<<i<<,'19.,;20. SyStem(HPaUSeM);21. return;22. 23.23. VOidGree

11、dyChOOSe(intlenint#s,int*fjbool*flag)24. 25. flag=true;26. intj=;27. for(intil;i<len;+i)28. if(si>=fj)29. 31.30. flagi=true;33 j=i;34. 35.35. 得出结果是0 37 10,也就是对应的时间段本次课程的心得体会：计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多 问题的解决，程序的编写都要依赖它，在软件还是而向过程的阶段，就有程序=算法+数据结 构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的 算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性 和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的汁算机应用系统 中的软件，都必须使用具体的算法来实现。算