算法設(shè)計(jì) 課程設(shè)計(jì)資料報(bào)告材料

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

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

化整為零，減少了運(yùn)算量貪心算法，是永不知足的求最優(yōu)解，有點(diǎn)類似于我們所說(shuō)的完美主義者兩者之間有一樣點(diǎn)，總結(jié)來(lái)說(shuō)某種程度上，動(dòng)規(guī)是貪心的泛化，貪心是動(dòng)規(guī)的特例貪心：A最優(yōu)+B最優(yōu)動(dòng)態(tài)規(guī)劃：〔A+B〕最優(yōu)就單步而言貪心的A最優(yōu)是前一步的結(jié)果，B最優(yōu)需要遍歷找到動(dòng)態(tài)規(guī)劃的A為前一步的可行解，需要選擇一個(gè)B后再去找A動(dòng)態(tài)規(guī)劃算法之0-1背包問(wèn)題：給定n種物品和一個(gè)背包物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大??與0-1背包問(wèn)題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一局部，而不一定要全部裝入背包，1≤i≤n?????這2類問(wèn)題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解用貪心算法解背包問(wèn)題的根本步驟是，首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包假設(shè)將這種物品全部裝入背包后，背包的物品總重量未超過(guò)C，如此選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包依此策略一直地進(jìn)展下去，直到背包裝滿為止???? 具體代碼如下：1. //4d2?貪心算法?背包問(wèn)題??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. ????//這里給定的物品按單位價(jià)值減序排序??14. ????float?w[]?=?{0,10,20,30};//下標(biāo)從1開(kāi)始??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. }??程序運(yùn)行結(jié)果為：動(dòng)態(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 的背包中，可以取得的最大價(jià)值。

Pi表示第i件物品的價(jià)值決策：為了背包中物品總價(jià)值最大化，第 i件物品應(yīng)該放入背包中嗎 ？題目描述：有編號(hào)分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價(jià)值分別是6,3,5,4,6，現(xiàn)在給你個(gè)承重為10的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？nameweightvalue12345678910a26066991212151515b23033669991011c65000666661011d54000666661010e460006666666這表是至底向上，從左到右生成的為了表示方便，用e2單元格表示e行2列的單元格，這個(gè)單元格的意義是用來(lái)表示只有物品e時(shí)，有個(gè)承重為2的背包，那么這個(gè)背包的最大價(jià)值是0，因?yàn)閑物品的重量是4，背包裝不了對(duì)于d2單元格，表示只有物品e，d時(shí),承重為2的背包,所能裝入的最大價(jià)值，仍然是0，因?yàn)槲锲積,d都不是這個(gè)背包能裝的同理，c2=0，b2=3,a2=6對(duì)于承重為8的背包，a8=15,是怎么得出的呢？根據(jù)01背包的狀態(tài)轉(zhuǎn)換方程，需要考察兩個(gè)值，一個(gè)是f[i-1,j],對(duì)于這個(gè)例子來(lái)說(shuō)就是b8的值9，另一個(gè)是f[i-1,j-Wi]+Pi；在這里，?f[i-1,j]表示我有一個(gè)承重為8的背包，當(dāng)只有物品b,c,d,e四件可選時(shí)，這個(gè)背包能裝入的最大價(jià)值f[i-1,j-Wi]表示我有一個(gè)承重為6的背包〔等于當(dāng)前背包承重減去物品a的重量〕，當(dāng)只有物品b,c,d,e四件可選時(shí)，這個(gè)背包能裝入的最大價(jià)值f[i-1,j-Wi]就是指單元格b6,值為9，Pi指的是a物品的價(jià)值，即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裝入背包后的價(jià)值總和??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é)合實(shí)際，談?wù)劚菊n程學(xué)習(xí)的收獲、體會(huì)、建議與意見(jiàn)等。

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