算法設(shè)計 課程設(shè)計資料報告材料

word《算法設(shè)計與分析》１　什么是算法？算法的特征有哪些？根據(jù)我自己的理解，算法是解決問題的方法步驟比如在解決高數(shù)問題的時候，可以分步驟進展解答，在編程的過程算法可以得到最好的表現(xiàn)算法是一系列解決問題的清晰指令，因為我最近在考研復習，對于會的題目還有進展屢次的鞏固，但是一步步的寫很浪費時間，所以我只是寫出關(guān)鍵指令，比如化簡通分，洛必達法如此，上下同階這樣可以提高效率算法的指令也是同樣的能夠?qū)σ欢ㄒ?guī)的輸入，在有限時間獲得所要求的輸出一個算法的優(yōu)劣可以用空間復雜度與時間復雜度來衡量２　假設(shè)給定某一算法，一般如何對其分析與評價？一個算法的復雜性的上下表現(xiàn)在運行該算法所需要的計算機資源的多少上面，所需的資源越多，我們就說該算法的復雜性越高；反之，所需的資源越低，如此該算法的復雜性越低計算機的資源，最重要的是時間和空間〔存儲器〕資源算法的復雜性有時間復雜性和空間復雜性之分 1.時間復雜性：例1：設(shè)一程序段如下〔為討論方便，每行前加一行號〕(1) for i:=1 to n do(2) for j:=1 to n do(3) x:=x+1 ...... 試問在程序運行中各步執(zhí)行的次數(shù)各為多少？ 解答：行號 次數(shù)(頻度)(1) n+1(2) n*(n+1)(3) n*n 可見，這段程序總的執(zhí)行次數(shù)是：f(n)=2n2+2n+1。

在這里，n可以表示問題的規(guī)模，當n趨向無窮大時，如果 f(n)的值很小，如此算法優(yōu)作為初學者，我們可以用f(n)的數(shù)量級O來粗略地判斷算法的時間復雜性，如上例中的時間復雜性可粗略地表示為T(n)=O(n2)2.空間復雜性:例2:將一一維數(shù)組的數(shù)據(jù)(n個)逆序存放到原數(shù)組中,下面是實現(xiàn)該問題的兩種算法:算法1:for i:=1 to n do b[i]:=a[n-i+1]; for i:=1 to n do a[i]:=b[i];算法2:for i:=1 to n div 2 do begin t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t end;算法1的時間復雜度為2n,空間復雜度為2n算法2的時間復雜度為3*n/2,空間復雜度為n+1顯然算法2比算法1優(yōu)，這兩種算法的空間復雜度可粗略地表示為S(n)=O(n)3、從下面算法策略中自選一組，結(jié)合某具體問題的求解來介紹算法思想，并加以總結(jié)、比擬： 遞歸與分治、動態(tài)規(guī)劃與貪心法、回溯法與分支限界法動態(tài)規(guī)劃算法類似于分治法，根本思想也是將待求解問題分解成假設(shè)干個子問題。

化整為零，減少了運算量貪心算法，是永不知足的求最優(yōu)解，有點類似于我們所說的完美主義者兩者之間有一樣點，總結(jié)來說某種程度上，動規(guī)是貪心的泛化，貪心是動規(guī)的特例貪心：A最優(yōu)+B最優(yōu)動態(tài)規(guī)劃：〔A+B〕最優(yōu)就單步而言貪心的A最優(yōu)是前一步的結(jié)果，B最優(yōu)需要遍歷找到動態(tài)規(guī)劃的A為前一步的可行解，需要選擇一個B后再去找A動態(tài)規(guī)劃算法之0-1背包問題：給定n種物品和一個背包物品i的重量是Wi，其價值為Vi，背包的容量為C應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大??與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一局部，而不一定要全部裝入背包，1≤i≤n?????這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解用貪心算法解背包問題的根本步驟是，首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包假設(shè)將這種物品全部裝入背包后，背包的物品總重量未超過C，如此選擇單位重量價值次高的物品并盡可能多地裝入背包依此策略一直地進展下去，直到背包裝滿為止???? 具體代碼如下：1. //4d2?貪心算法?背包問題??2. #include?"stdafx.h"??3. #include????4. using?namespace?std;???5. ??6. const?int?N?=?3;??7. ??8. void?Knapsack(int?n,float?M,float?v[],float?w[],float?x[]);??9. ??10. int?main()??11. {??12. ????float?M?=?50;//背包所能容納的重量??13. ????//這里給定的物品按單位價值減序排序??14. ????float?w[]?=?{0,10,20,30};//下標從1開始??15. ????float?v[]?=?{0,60,100,120};??16. ??17. ????float?x[N+1];??18. ??19. ????cout<<"背包所能容納的重量為："<c)??50. ????????{??51. ????????????break;??52. ????????}??53. ????????x[i]=1;??54. ????????c-=w[i];??55. ????}??56. ??57. ????//物品i只有局部被裝下??58. ????if?(i<=n)??59. ????{??60. ????????x[i]=c/w[i];??61. ????}??62. }??程序運行結(jié)果為：動態(tài)規(guī)劃之01背包狀態(tài)轉(zhuǎn)換方程?f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), ?f[i-1,j] }f[i,j]表示在前i件物品中選擇假設(shè)干件放在承重為 j 的背包中，可以取得的最大價值。

Pi表示第i件物品的價值決策：為了背包中物品總價值最大化，第 i件物品應(yīng)該放入背包中嗎 ？題目描述：有編號分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價值分別是6,3,5,4,6，現(xiàn)在給你個承重為10的背包，如何讓背包里裝入的物品具有最大的價值總和？nameweightvalue12345678910a26066991212151515b23033669991011c65000666661011d54000666661010e460006666666這表是至底向上，從左到右生成的為了表示方便，用e2單元格表示e行2列的單元格，這個單元格的意義是用來表示只有物品e時，有個承重為2的背包，那么這個背包的最大價值是0，因為e物品的重量是4，背包裝不了對于d2單元格，表示只有物品e，d時,承重為2的背包,所能裝入的最大價值，仍然是0，因為物品e,d都不是這個背包能裝的同理，c2=0，b2=3,a2=6對于承重為8的背包，a8=15,是怎么得出的呢？根據(jù)01背包的狀態(tài)轉(zhuǎn)換方程，需要考察兩個值，一個是f[i-1,j],對于這個例子來說就是b8的值9，另一個是f[i-1,j-Wi]+Pi；在這里，?f[i-1,j]表示我有一個承重為8的背包，當只有物品b,c,d,e四件可選時，這個背包能裝入的最大價值f[i-1,j-Wi]表示我有一個承重為6的背包〔等于當前背包承重減去物品a的重量〕，當只有物品b,c,d,e四件可選時，這個背包能裝入的最大價值f[i-1,j-Wi]就是指單元格b6,值為9，Pi指的是a物品的價值，即6由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a應(yīng)該放入承重為8的背包以下是actionscript3 的代碼1. public?function?get01PackageAnswer(bagItems:Array,bagSize:int):Array??2. {??3. ????var?bagMatrix:Array=[];??4. ????var?i:int;??5. ????var?item:PackageItem;??6. ????for(i=0;i?i)??16. ????????????{??17. ????????????????//i背包轉(zhuǎn)不下item??18. ????????????????if(j==0)??19. ????????????????{??20. ????????????????????bagMatrix[j][i]?=?0;??21. ????????????????}??22. ????????????????else??23. ????????????????{??24. ????????????????????bagMatrix[j][i]=bagMatrix[j-1][i];??25. ????????????????}??26. ????????????}??27. ????????????else??28. ????????????{??29. ????????????????//將item裝入背包后的價值總和??30. ????????????????var?itemInBag:int;??31. ????????????????if(j==0)??32. ????????????????{??33. ????????????????????bagMatrix[j][i]?=?item.value;??34. ????????????????????continue;??35. ????????????????}??36. ????????????????else??37. ????????????????{??38. ????????????????????itemInBag?=?bagMatrix[j-1][i-item.weight]+item.value;??39. ????????????????}??40. ????????????????bagMatrix[j][i]?=?(bagMatrix[j-1][i]?>?itemInBag???bagMatrix[j-1][i]?:?itemInBag)??41. ????????????}??42. ????????}??43. ????}??44. ????//find?answer??45. ????var?answers:Array=[];??46. ????var?curSize:int?=?bagSize;??47. ????for(i=bagItems.length-1;i>=0;i--)??48. ????{??49. ????????item?=?bagItems[i]?as?PackageItem;??50. ????????if(curSize==0)??51. ????????{??52. ????????????break;??53. ????????}??54. ????????if(i==0?&&?curSize?>?0)??55. ????????{??56. ????????????answers.push(item.name);??57. ????????????break;??58. ????????}??59. ????????if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight]==item.value)??60. ????????{??61. ????????????answers.push(item.name);??62. ????????????curSize?-=?item.weight;??63. ????????}??64. ????}??65. ????return?answers;??66. }??四 結(jié)合實際，談?wù)劚菊n程學習的收獲、體會、建議與意見等。

通過算法設(shè)計與分析的講解，我回歸了以前的知識點，以前在學習C語言和C++ 的時候?qū)ω澬乃惴?，回溯法，有一些了解，在教師的更細心講解下我對算法的重要性和策略有更好的理解，在面向?qū)ο蟮臅r候?qū)W會了一個公式 編程=數(shù)據(jù)結(jié)構(gòu)+算法算法是指令，就像帶兵打仗的將軍，是揮斥方遒的決定性策略策略的評估可以用時間復雜度和空間復雜度來計算11 / 11。