《算法設(shè)計(jì) 課程設(shè)計(jì)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法設(shè)計(jì) 課程設(shè)計(jì)報(bào)告（11頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、《算法設(shè)計(jì)與分析》 １　什么是算法？算法的特征有哪些？ 根據(jù)我自己的理解，算法是解決問(wèn)題的方法步驟。比如在解決高數(shù)問(wèn)題的時(shí)候，可以分步驟進(jìn)行解答，在編程的過(guò)程算法可以得到最好的體現(xiàn)。 算法是一系列解決問(wèn)題的清晰指令，因?yàn)槲易罱诳佳袕?fù)習(xí)，對(duì)于會(huì)的題目還有進(jìn)行多次的鞏固，但是一步步的寫很浪費(fèi)時(shí)間，所以我只是寫出關(guān)鍵指令，比如化簡(jiǎn)通分，洛必達(dá)法則，上下同階。這樣可以提高效率。算法的指令也是同樣的。能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量。 ２　若給定某一算法，一般如何對(duì)其分析與評(píng)價(jià)？ 一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要

2、的計(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 可見，這段程序總的

3、執(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(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

4、 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)題分解成若干個(gè)子問(wèn)題?；麨榱?，減少了運(yùn)算量。 貪心算法，是永不知足的求最優(yōu)

5、解，有點(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)題都

6、具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解。用貪心算法解背包問(wèn)題的基本步驟是，首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 ???? 具體代碼如下： 1. //4d2?貪心算法?背包問(wèn)題?? 2. #include?"stdafx.h"?? 3. #include???? 4. using?namesp

7、ace?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開始?? 15. ????float?v[]?=?{0,60,100,120};??

8、16. ?? 17. ????float?x[N+1];?? 18. ?? 19. ????cout<<"背包所能容納的重量為："<

9、28. ????cout<<"選擇裝下的物品比例如下："<

10、v[]已按要求排好序?? 40. ????int?i;?? 41. ????for?(i=1;i<=n;i++)?? 42. ????{?? 43. ????????x[i]=0;//初始化數(shù)組x[]?? 44. ????}?? 45. ?? 46. ????float?c=M;?? 47. ????for?(i=1;i<=n;i++)//物品整件被裝下,x[i]=1?? 48. ????{?? 49. ????????if?(w[i]>c)?? 50. ????????{?? 51. ????????????break;?? 52. ????????}?? 53.

11、 ????????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件物品中選擇若干件放在承重為 j 的背包中，可以取得的最大價(jià)

12、值。 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à)值總和？ name weight value 1 2 3 4 5 6 7 8 9 10 a 2 6 0 6 6 9 9 12 12 15 15 15 b 2 3 0 3 3 6 6 9 9 9 10 11 c 6

13、5 0 0 0 6 6 6 6 6 10 11 d 5 4 0 0 0 6 6 6 6 6 10 10 e 4 6 0 0 0 6 6 6 6 6 6 6 這張表是至底向上，從左到右生成的。 為了敘述方便，用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

14、=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

15、 + 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

16、agMatrix[i]?=?[0];?? 9. ????}?? 10. ????for(i=1;i<=bagSize;i++)?? 11. ????{?? 12. ????????for(var?j:int=0;j?i)?? 16. ????????????{?? 17. ????????????????//i背包轉(zhuǎn)不下item?

17、? 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. ??

18、??????????else?? 28. ????????????{?? 29. ????????????????//將item裝入背包后的價(jià)值總和?? 30. ????????????????var?itemInBag:int;?? 31. ????????????????if(j==0)?? 32. ????????????????{?? 33. ????????????????????bagMatrix[j][i]?=?item.value;?? 34. ????????????????????continue;?? 35. ????????????????}?? 36

19、. ????????????????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. ????????}??

20、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. ??????

21、??}?? 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);??

22、62. ????????????curSize?-=?item.weight;?? 63. ????????}?? 64. ????}?? 65. ????return?answers;?? 66. }?? 四 結(jié)合實(shí)際，談?wù)劚菊n程學(xué)習(xí)的收獲、體會(huì)、建議與意見等。 通過(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ì)算。