算法設計 課程設計資料報告材料

《算法設計 課程設計資料報告材料》由會員分享，可在線閱讀，更多相關《算法設計 課程設計資料報告材料（11頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word 《算法設計與分析》 １　什么是算法？算法的特征有哪些？ 根據(jù)我自己的理解，算法是解決問題的方法步驟。比如在解決高數(shù)問題的時候，可以分步驟進展解答，在編程的過程算法可以得到最好的表現(xiàn)。 算法是一系列解決問題的清晰指令，因為我最近在考研復習，對于會的題目還有進展屢次的鞏固，但是一步步的寫很浪費時間，所以我只是寫出關鍵指令，比如化簡通分，洛必達法如此，上下同階。這樣可以提高效率。算法的指令也是同樣的。能夠對一定規(guī)的輸入，在有限時間獲得所要求的輸出。一個算法的優(yōu)劣可以用空間復雜度與時間復雜度來衡量。 ２　假設給定某一算法，一般如何對其分析與評價？ 一個算法的復雜性的上下表現(xiàn)在運行

2、該算法所需要的計算機資源的多少上面，所需的資源越多，我們就說該算法的復雜性越高；反之，所需的資源越低，如此該算法的復雜性越低。 計算機的資源，最重要的是時間和空間〔存儲器〕資源。算法的復雜性有時間復雜性和空間復雜性之分。 1.時間復雜性： 例1：設一程序段如下〔為討論方便，每行前加一行號〕 (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 可見

3、，這段程序總的執(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

4、 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、從下面算法策略中自選一組，結合某具體問題的求解來介紹算法思想，并加以總結、比擬： 遞歸與分治、動態(tài)規(guī)劃與貪心法、回溯法與分支限界法 動態(tài)規(guī)劃算法類似于分治法，根本思想也是將待求解問題分解成假設干個子問題。化整為零，減少了運算量。 貪心算法，

5、是永不知足的求最優(yōu)解，有點類似于我們所說的完美主義者。 兩者之間有一樣點，總結來說某種程度上，動規(guī)是貪心的泛化，貪心是動規(guī)的特例 貪心：A最優(yōu)+B最優(yōu)動態(tài)規(guī)劃：〔A+B〕最優(yōu)就單步而言貪心的A最優(yōu)是前一步的結果，B最優(yōu)需要遍歷找到動態(tài)規(guī)劃的A為前一步的可行解，需要選擇一個B后再去找A 動態(tài)規(guī)劃算法之0-1背包問題：給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大? ?與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一局部，而不一定要全部裝入背包，1≤i≤n。 ?????這2類問題

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

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

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. ????????}?? 5

11、3. ????????x[i]=1;?? 54. ????????c-=w[i];?? 55. ????}?? 56. ?? 57. ????//物品i只有局部被裝下?? 58. ????if?(i<=n)?? 59. ????{?? 60. ????????x[i]=c/w[i];?? 61. ????}?? 62. }?? 程序運行結果為： 動態(tài)規(guī)劃之01背包 狀態(tài)轉換方程?f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), ?f[i-1,j] } f[i,j]表示在前i件物品中選擇假設干件放在承重為 j 的背包中，可以取得的

12、最大價值。 Pi表示第i件物品的價值。 決策：為了背包中物品總價值最大化，第 i件物品應該放入背包中嗎 ？ 題目描述： 有編號分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價值分別是6,3,5,4,6，現(xiàn)在給你個承重為10的背包，如何讓背包里裝入的物品具有最大的價值總和？ 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

13、6 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列的單元格，這個單元格的意義是用來表示只有物品e時，有個承重為2的背包，那么這個背包的最大價值是0，因為e物品的重量是4，背包裝不了。 對于d2單元格，表示只有物品e，d時,承重為2的背包,所能裝入的最大價值，仍然是0，因為物品e,d都不是這個背包能裝的。 同理，c2=0，b2=3,

14、a2=6。 對于承重為8的背包，a8=15,是怎么得出的呢？ 根據(jù)01背包的狀態(tài)轉換方程，需要考察兩個值， 一個是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 =

15、 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a應該放入承重為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、?bagMatrix[i]?=?[0];?? 9. ????}?? 10. ????for(i=1;i<=bagSize;i++)?? 11. ????{?? 12. ????????for(var?j:int=0;j?i)?? 16. ????????????{?? 17. ????????????????//i背包轉不下ite

17、m?? 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裝入背包后的價值總和?? 30. ????????????????var?itemInBag:int;?? 31. ????????????????if(j==0)?? 32. ????????????????{?? 33. ????????????????????bagMatrix[j][i]?=?item.value;?? 34. ????????????????????continue;?? 35. ????????????????}??

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

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. }?? 四 結合實際，談談本課程學習的收獲、體會、建議與意見等。 通過算法設計與分析的講解，我回歸了以前的知識點，以前在學習C語言和C++ 的時候對貪心算法，回溯法，有一些了解，在教師的更細心講解下我對算法的重要性和策略有更好的理解，在面向對象的時候學會了一個公式 編程=數(shù)據(jù)結構+算法。算法是指令，就像帶兵打仗的將軍，是揮斥方遒的決定性策略。策略的評估可以用時間復雜度和空間復雜度來計算。 11 / 11