武漢理工大學(xué)算法分析實(shí)驗(yàn)報(bào)告

1、學(xué)生學(xué)號(hào)實(shí)驗(yàn)課成績(jī)學(xué)生實(shí)驗(yàn)報(bào)告書(shū)算法設(shè)計(jì)與分析計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院李曉紅軟件工程zy1302班實(shí)驗(yàn)課程名稱 開(kāi)課學(xué)院 指導(dǎo)教師姓名 學(xué)生姓名 學(xué)生專業(yè)班級(jí)2015-2016 學(xué)年 第一學(xué)期部分內(nèi)容來(lái)源于網(wǎng)絡(luò)，有侵權(quán)請(qǐng)聯(lián)系刪除!實(shí)驗(yàn)課程名稱：算法設(shè)計(jì)與分析實(shí)驗(yàn)項(xiàng)目名稱分治與遞歸實(shí)驗(yàn)成績(jī)實(shí)驗(yàn)者專業(yè)班級(jí)軟件zy1302班組另U同組者實(shí)驗(yàn)日期2015年10月20日第一部分：實(shí)驗(yàn)分析與設(shè)計(jì)實(shí)驗(yàn)內(nèi)容描述（問(wèn)題域描述）1、利用分治法，寫(xiě)一個(gè)快速排序的遞歸算法，并利用任何一種語(yǔ)言，在計(jì)算機(jī)上實(shí)現(xiàn)，同時(shí) 進(jìn)行時(shí)間復(fù)雜性分析；2、要求用遞歸的方法實(shí)現(xiàn)。二.實(shí)驗(yàn)基本原理與設(shè)計(jì)（包括實(shí)驗(yàn)方案設(shè)計(jì)，實(shí)驗(yàn)手段的確定，試驗(yàn)

2、步驟等，用硬件邏輯或 者算法描述）本次的解法使用的是三向切分的快速排序”，它是快速排序的一種優(yōu)化版本。不僅利用了分治法和遞歸實(shí)現(xiàn)，而且對(duì)于存在大量重復(fù)元素的數(shù)組，它的效率比快速排序基本版高得多。它從左到右遍歷數(shù)組一次，維護(hù)一個(gè)指針 It使得alo.lt-1中的元素都小于v, 個(gè)指針gt使得agt+1.hi中的元素都大于v，個(gè)指針i使得alt.i-1中的元素都等于v，ai.gt中的元素都還未確定，如下圖所示：3*way partitioning overviewpublic class Quick3waypublic static void sort(Comparable a, int Io,

3、int hi) if (lo >= hi) return;int It = lo, i = lo + 1, gt = hi;Comparable pivot = alo;while (i <= gt)int cmp = pareTo(pivot); if (cmp > 0)exch(a, i, gt-);else if (cmp < 0)exch(a, i+, lt+);elsei+;sort(a, lo, lt - 1);sort(a, gt + 1, hi);三、主要儀器設(shè)備及耗材PC機(jī)部分內(nèi)容來(lái)源于網(wǎng)絡(luò)，有侵權(quán)請(qǐng)聯(lián)系刪除!第二部分：實(shí)驗(yàn)調(diào)試與結(jié)果分析一

4、、調(diào)試過(guò)程（包括調(diào)試方法描述、實(shí)驗(yàn)數(shù)據(jù)記錄，實(shí)驗(yàn)現(xiàn)象記錄，實(shí)驗(yàn)過(guò)程發(fā)現(xiàn)的問(wèn)題等）1、2、3、調(diào)試方法描述：對(duì)程序入口進(jìn)行斷點(diǎn)，隨著程序的運(yùn)行，一步一步的調(diào)試，得到運(yùn)行軌跡; 實(shí)驗(yàn)數(shù)據(jù)："R", "B", "W", "W", "R", "W", "B", "R", "R", "W",實(shí)驗(yàn)現(xiàn)象:"B","R"ItaJigto1234518910110011RBW

5、WRW8RR州BR0111RBnrgR1211RWbyR1210RRBr KJ1310Rwj Q|1>n itE13gRB0kJ249Jn *R* DRw25gORWwk 1258RRWR LJKJ257口BRnpKRW267IDRRBRw371>n尸Ri?R381uRRw制387BBRRRRRwW3*way partitioning trace (array contents after each loop iteration4、實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn)的問(wèn)題：（1）邊界問(wèn)題：在設(shè)計(jì)快速排序的代碼時(shí)要非常小心，因?yàn)槠渲邪浅ｊP(guān)鍵的邊界問(wèn)題，例如： 什么時(shí)候跳出 while循環(huán)，遞歸什么時(shí)

6、候結(jié)束，是對(duì)指針的左半部分還是右半部分 排序等等；（2）程序的調(diào)試跳轉(zhuǎn)：在調(diào)試過(guò)程中要時(shí)刻記住程序是對(duì)那一部分進(jìn)行排序，當(dāng)完成了這部分的排序后， 會(huì)跳到哪里又去對(duì)另外的那一部分進(jìn)行排序，這些都是要了然于心的，這樣才能準(zhǔn) 確的定位程序。、實(shí)驗(yàn)結(jié)果分析（包括結(jié)果描述、實(shí)驗(yàn)現(xiàn)象分析、影響因素討論、綜合分析和結(jié)論等）1、實(shí)驗(yàn)結(jié)果:MF:Program FilesJavajdkl.8.0_66binjava 排序前：R> B,町 W, R, W, B> R, R, W, B, R 排序后：B, B, RR» Rj R, R» 叫 WJ W, WProcess finish

7、ed with exit code 02、時(shí)間復(fù)雜度：介于N和NIogN之間；3、空間復(fù)雜度：igN ；4、算法總結(jié)：三項(xiàng)切分的快速排序不是穩(wěn)定的排序，是原地排序，它的運(yùn)行效率由概率保證，同時(shí)取決 于輸入元素的分布情況，對(duì)于包含大量重復(fù)元素的數(shù)組，它獎(jiǎng)排序時(shí)間從線性對(duì)數(shù)級(jí)降低 到了線性級(jí)別，這非常的了不起。三、小結(jié)、建議及體會(huì)本次實(shí)驗(yàn)完成了三向切分的快速排序，其中不僅利用了分治法和遞歸，還對(duì)快速排序進(jìn)行 了優(yōu)化，使得對(duì)于存在大量重復(fù)元素的數(shù)組，能夠表現(xiàn)更高的效率。在實(shí)驗(yàn)過(guò)程中，我遇到了 不少的困難，但通過(guò)自己在網(wǎng)上大量的瀏覽文獻(xiàn)和資料，獨(dú)立解決了所有問(wèn)題，收獲了不少。 在下次的實(shí)驗(yàn)中，我也會(huì)繼

8、續(xù)努力的！實(shí)驗(yàn)課程名稱：算法設(shè)計(jì)與分析實(shí)驗(yàn)項(xiàng)目名稱動(dòng)態(tài)規(guī)劃算法實(shí)驗(yàn)成績(jī)實(shí)驗(yàn)者專業(yè)班級(jí)軟件zy1302班組另U同組者實(shí)驗(yàn)日期2015年12月1日第一部分：實(shí)驗(yàn)分析與設(shè)計(jì)實(shí)驗(yàn)內(nèi)容描述（問(wèn)題域描述）1、掌握動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的一般特征和步驟；2、使用動(dòng)態(tài)規(guī)劃法編程，求解 0/1背包問(wèn)題；3、 問(wèn)題描述：給定n種物品和一個(gè)背包，物品i的重量是 Wi,其價(jià)值為W,問(wèn)如何選擇裝入 背包的物品，使得裝入背包的物品的總價(jià)值最大？二. 實(shí)驗(yàn)基本原理與設(shè)計(jì)（包括實(shí)驗(yàn)方案設(shè)計(jì)，實(shí)驗(yàn)手段的確定，試驗(yàn)步驟等，用硬件邏輯或 者算法描述）0/1背包問(wèn)題的特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問(wèn)題定義狀態(tài)：即ci

9、v表示前i件物品恰放入一個(gè)重量為m的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：cim=maxci-1m,ci-1m-wi+pi這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。我來(lái)解釋 一下：“將前i件物品放入重量為m的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為 v的背包中”，價(jià)值為ci-1m；如果放第i件物品，那么問(wèn)題 就轉(zhuǎn)化為“前i-1件物品放入剩下的重量為m-wi的背包中”，此時(shí)能獲得的最大價(jià)值就是ci-1m-wi再加上通過(guò)放入第i件物品獲

10、得的價(jià)值pi。算法設(shè)計(jì)如下：F0 - 0F0 - 0 for i 1 to N do for k 1 to VFik Fi-1kif（k >= Ci）then Fik max（Fik,Fi-1k-Ci+Wi）return FNV三、主要儀器設(shè)備及耗材PC機(jī)第二部分：實(shí)驗(yàn)調(diào)試與結(jié)果分析一、調(diào)試過(guò)程（包括調(diào)試方法描述、實(shí)驗(yàn)數(shù)據(jù)記錄，實(shí)驗(yàn)現(xiàn)象記錄，實(shí)驗(yàn)過(guò)程發(fā)現(xiàn)的問(wèn)題等）1、調(diào)試方法：直接在方法入口斷點(diǎn)調(diào)試，一步一步跟蹤程序，弄明白程序的運(yùn)行軌跡；2、實(shí)驗(yàn)數(shù)據(jù)：int m = 10;int n = 3; in t w = 3, 4, 5;in t p = 4, 5, 6;3、實(shí)驗(yàn)中遇到問(wèn)題：（1

11、）剛開(kāi)始對(duì)動(dòng)態(tài)規(guī)劃算法不熟悉，編碼時(shí)出現(xiàn)很多的錯(cuò)誤，花費(fèi)了很多的時(shí)間;（2）沒(méi)有深度理解此處為什么要使用動(dòng)態(tài)規(guī)劃算法，導(dǎo)致對(duì)問(wèn)題的理解不深刻。二、實(shí)驗(yàn)結(jié)果分析（包括結(jié)果描述、實(shí)驗(yàn)現(xiàn)象分析、影響因素討論、綜合分析和結(jié)論等）1、實(shí)驗(yàn)結(jié)果："F:Program FilesJavajdkl,8*0_66binjava 第0號(hào)背包：0第丄號(hào)背包：1第2號(hào)背包；1Process finished with exit code 02、時(shí)間復(fù)雜度：nm;3、空間復(fù)雜度：nm （可優(yōu)化至 m）;4、算法總結(jié)：動(dòng)態(tài)規(guī)劃的基本思想：將一個(gè)問(wèn)題分解為子問(wèn)題遞歸求解，且將中間結(jié)果保存以避免重復(fù)計(jì)算。通常用來(lái)求

12、 最優(yōu)解，且最優(yōu)解的局部也是最優(yōu)的。求解過(guò)程產(chǎn)生多個(gè)決策序列，下一步總是依賴上一 步的結(jié)果，自底向上的求解。三、小結(jié)、建議及體會(huì)本次實(shí)驗(yàn)解決了 0/1背包問(wèn)題，掌握動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的一般特征和步驟。在實(shí)驗(yàn)過(guò) 程中，我遇到了很多不懂的問(wèn)題，但通過(guò)老師和同學(xué)們的幫助，和自己的努力，最終解決了所 有問(wèn)題，收獲頗豐。在今后的算法設(shè)計(jì)中，我會(huì)迎難而上！源代碼:實(shí)驗(yàn)一：import java.util.Arrays;public class Quick3waypublic static void sort(Comparable a)sort(a, 0, a.length - 1);public sta

13、tic void sort(Comparable a, int Io, int hi) if (lo >= hi)return;in t lt = lo, i = lo + 1, gt = hi;Comparable pivot = alo;while (true)int cmp = pareTo(pivot);if (cmp > 0)exch(a, i, gt-);else if (cmp < 0)exch(a, i+, lt+);elsei+;if (i > gt)break;sort(a, lo, lt - 1);sort(a, gt + 1, hi)

14、;private static void exch(Comparable a, int i, int j) Comparable temp = ai;ai = ajaj = temp;public static void show(Comparable a)System.out.pri ntl n( Arrays.toStri ng(a);public static void main(String args)"W", "B",Stri nga = "R","B","W", "W&qu

15、ot;, "R","W", "B","R","R","R"System.out.pri ntln(”排序前：t");show(a);sort(a); /對(duì)數(shù)組a進(jìn)行排序System.out.pri ntln(”排序后：t");show(a);實(shí)驗(yàn)二：package com.shaw n;public class PackageOlpublic in t pack(i nt m, int n, int w, int p)civ表示前i件物品恰放入一個(gè)重量為m

16、的背包可以獲得的最大價(jià)值in t c = new in tn + 1m + 1;for (int i = 0; i < n + 1; i+)ci0 = 0;for (int j = 0; j < m + 1; j+)c0j = 0;for (int i = 1; i < n + 1; i+)for (int j = 1; j < m + 1; j+)時(shí),II當(dāng)物品為i件重量為j時(shí)，如果第i件的重量(wi-1)小于重量jcij為下列兩種情況之一：II(1)物品i不放入背包中，所以 cij 為ci-1j 的值II(2)物品i放入背包中，則背包剩余重量為 j-wi-1, 所以

17、cij為ci-1j-wi-1的值加上當(dāng)前物品i的價(jià)值if (wi - 1 <= j)if (ci - 1j < (ci - 1j - wi - 1 + pi - 1)cij = ci - 1j - wi - 1 + pi - 1;elsecij = ci - 1j;elsecij = ci - 1j;return c;II 逆推法求出最優(yōu)解public int printPack(int c, int w, int m, int n)int x = new intn;II從最后一個(gè)狀態(tài)記錄c nm開(kāi)始逆推for (int i = n; i > 0; i-)含了/如果cim 大于ci-1m ，說(shuō) 明cim這個(gè)最優(yōu)值中包wi-1(注意這里是i-1，因?yàn)閏數(shù)組長(zhǎng)度是n+1)if (cim > ci - 1m)xi - 1 = 1;m -= wi - 1;for (int j = 0; j