《算法设计课程设计报告》由会员分享，可在线阅读，更多相关《算法设计课程设计报告（10页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析1 什么就是算法？算法得特征有哪些？根据我自己得理解，算法就是解决问题得方法步骤。比如在解决高数问题得时候，可以分步骤进行解答，在编程得过程算法可以得到最好得体现。算法就是一系列解决问题得清晰指令，因为我最近在考研复习，对于会得题目还有进行多次得巩固，但就是一步步得写很浪费时间，所以我只就是写出关键指令，比如化简通分，洛必达法则，上下同阶。这样可以提高效率。算法得指令也就是同样得。能够对一定规范得输入，在有限时间内获得所要求得输出。一个算法得优劣可以用空间复杂度与时间复杂度来衡量。2 若给定某一算法，一般如何对其分析与评价？一个算法得复杂性得高低体现在运行该算法所需要得计算机资源
2、得多少上面，所需得资源越多，我们就说该算法得复杂性越高；反之，所需得资源越低，则该算法得复杂性越低。计算机得资源，最重要得就是时间与空间(存储器)资源。算法得复杂性有时间复杂性与空间复杂性之分。1、时间复杂性：例1:设一程序段如下(为讨论方便，每行前加一行号)fori:=1tondoforj:=1tondox:=x+1、试问在程序运行中各步执行得次数各为多少？解答：行号次数(频度)(1)n+1n*(n+1)n*n可见,这段程序总得执行次数就是：f(n)=2n2+2n+1。在这里,n可以表示问题得规模，当n趋向无穷大时，如果f(n)得值很小，则算法优。作为初学者，我们可以用f(n)得数量级0来粗
3、略地判断算法得时间复杂性，如上例中得时间复杂性可粗略地表示为T(n)=0(n2)。2、空间复杂性：例2:将一一维数组得数据(n个)逆序存放到原数组中，下面就是实现该问题得两种算法：算法1:fori:=1tondobi:=ani+1;fori:=1tondoai:=bi;算法2:fori:=1tondiv2dobegint:=ai;ai:=ani1;ani1:=tend;算法1得时间复杂度为2n,空间复杂度为2n算法2得时间复杂度为3*n/2,空间复杂度为n+1显然算法2比算法1优,这两种算法得空间复杂度可粗略地表示为S(n)=O(n)3、从下面算法策略中自选一组，结合某具体问题得求解来介绍算法
4、思想，并加以总结、比较：递归与分治、动态规划与贪心法、回溯法与分支限界法动态规划算法类似于分治法，基本思想也就是将待求解问题分解成若干个子问题。化整为零，减少了运算量。贪心算法，就是永不知足得求最优解，有点类似于我们所说得完美主义者。两者之间有相同点，总结来说某种程度上，动规就是贪心得泛化，贪心就是动规得特例贪心:A最优+B最优动态规划:(A+B)最优就单步而言贪心得A最优就是前一步得结果,B最优需要遍历找到动态规划得A为前一步得可行解，需要选择一个B后再去找A动态规划算法之01背包问题:给定n种物品与一个背包。物品i得重量就是Wi,其价值为Vi,背包得容量为C。应如何选择装入背包得物品,使得
5、装入背包中物品得总价值最大？与01背包问题类似，所不同得就是在选择物品i装入背包时，可以选择物品i得一部分，而不一定要全部装入背包,1in。这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而01背包问题却不能用贪心算法求解。用贪心算法解背包问题得基本步骤就是,首先计算每种物品单位重量得价值Vi/Wi,然后,依贪心选择策略，将尽可能多得单位重量价值最高得物品装入背包。若将这种物品全部装入背包后，背包内得物品总重量未超过C,则选择单位重量价值次高得物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。具体代码如下：4d2贪心算法背包问题#includestda
6、fx、h#includeusingnamespacestd;5.constintN=3;7.voidKnapsack(intn,floatM,floatv,floatw,floatx);9.intmainfloatM=50;/背包所能容纳得重量/这里给定得物品按单位价值减序排序floatw=0,10,20,30;/下标从1开始floatv=0,60,100,120;16.floatxN+1;18.cout背包所能容纳得重量为：vvMvvendl;coutvv待装物品得重量与价值分别为:endl;for(inti=1;i=N;i+)coutvvTvvivv:(vwivv,vvvivv)vvend
7、l;25.Knapsack(N,M,v,w,x);27.coutvv选择装下得物品比例如下:endl;for(inti=1;i=N;i+)coutvvvivv:vvxivvendl;33.return0;36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.60. voidKnapsack(intn,floatM,floatv,floatw,floatx)Sort(n,v,w);这里假定w,v已按要求排好序inti;for(i=1;i=n;i+)xi=0;初始化数组xfloatc=M;for(i=1;ic)br
8、eak;xi=1;c=wi;/物品i只有部分被装下if(i=Wi),fi1,jfi,j表示在前i件物品中选择若干件放在承重为j得背包中，可以取得得最大价值。Pi表示第i件物品得价值。决策:为了背包中物品总价值最大化，第i件物品应该放入背包中吗？题目描述：61296有编号分别为a,b,c,d,e得五件物品，它们得重量分别就是2,2,6,5,4,它们得价值分别就是6,3,5,4,6,现在给您个承重为10得背包，如何让背包里装入得物品具有最大得价值总与？nawevalmeightuea26b23c6566666006666666这张表就是至底向上，从左到右生成得。为了叙述方便，用e2单元格表示e行2
9、列得单元格，这个单元格得意义就是用来表示只有物品e时，有个承重为2得背包，那么这个背包得最大价值就是0,因为e物品得重量就是4,背包装不了。对于d2单元格，表示只有物品e,d时,承重为2得背包，所能装入得最大价值,仍然就是0,因为物品e,d都不就是这个背包能装得。同理,c2=0,b2=3,a2=6。对于承重为8得背包,a8=15,就是怎么得出得呢？根据01背包得状态转换方程，需要考察两个值，一个就是fi1,j,对于这个例子来说就就是b8得值9,另一个就是fi1,jWi+Pi;在这里，fi1,j表示我有一个承重为8得背包,当只有物品b,c,d,e四件可选时,这个背包能装入得最大价值fi1,jWi
10、表示我有一个承重为6得背包（等于当前背包承重减去物品a得重量），当只有物品b,c,d,e四件可选时，这个背包能装入得最大价值fi1,jWi就就是指单元格b6,值为9,Pi指得就是a物品得价值，即6由于fi1,jWi+Pi=9+6=15大于fi1,j=9,所以物品a应该放入承重为8得背包1.publicfunctiongetO1PackageAnswer(bagltems:Array,bagSize:int):ArrayvarbagMatrix:Array=;vari:int;varitem:Packageltem;for(i=0;ibagltems、length;i+)bagMatrixi=0
11、;for(i=1;i=bagSize;i+)for(varj:int=0;ji)/i背包转不下itemif(j=0)bagMatrixji=0;2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.else23.24.bagMatrixji=bagMatrixj1i;25.26.27.else28.29./将item装入背包后得价值总与30.varitemInBag:int;31.if(j=0)32.33.bagMatrixji=item、value;34.continue;35.36.else37.38.itemInBag=bagMat
12、rixj1iitemweight+item、value;39.40.bagMatrixji=(bagMatrixj1iitemInBagbagMatrixj1i:itemInBag)41.44./findanswer45.varanswers:Array=;46.varcurSize:int=bagSize;47.for(i=bagItems、length1;i=0;i)48.49.item=bagItemsiasPackageItem;50.if(curSize=0)51.52.break;53.54.if(i=0&curSize0)55.56.answers、push(item、name)
13、;57.break;58.59.if(bagMatrixicurSizebagMatrixi1curSizeitemweight=item、value)60.61.answers、push(item、name);62.curSize=item、weight;63.64.65.returnanswers;四结合实际，谈谈本课程学习得收获、体会、建议与意见等。通过算法设计与分析得讲解，我回归了以前得知识点，以前在学习C语言与C+得时候对贪心算法，回溯法，有一些了解,在老师得更细心讲解下我对算法得重要性与策略有更好得理解，在面向对象得时候学会了一个公式编程=数据结构+算法。算法就是指令，就像带兵打仗得将军，就是挥斥方遒得决定性策略。策略得评估可以用时间复杂度与空间复杂度来计算。
