終稿- -算法設(shè)計與分析實驗報告格式 3

算法設(shè)計與分析實驗報告一 實驗名稱 統(tǒng)計數(shù)字問題 評分 實驗日期 2013 年 11 月 4 日 指導(dǎo)教師 int result num 10 0 void process int m int main int argc char argv cout sizeof result num endl int file count 0 文本文件的標(biāo)題序號 char ctu y while ctu y ctu Y process file count cout 是否繼續(xù) y Y ctu file count return 0 void process int m memset result num 0 sizeof result num 每次新的運算均需要 把數(shù)組值都置為 ostringstream tstr int paper page tstr input m txt ofstream fout test tstr str c str 保存頁碼的文件 tstr str tstr output m txt ofstream fout result tstr str c str 保存結(jié)果的文件 cout paper page fout test paper page fout test close for int i 1 i paper page i int tmp i while tmp int num tmp 10 result num num tmp tmp 10 cout tmp endl for int j 0 j 10 j fout result result num j n fout result close 5 程序程序調(diào)試調(diào)試中的中的問題問題 出現(xiàn)一些小錯誤 修改后程序可運行 六六 實驗結(jié)實驗結(jié)果果 定義數(shù)組 a 10 存放 0 到 9 這 10 個數(shù)出現(xiàn)的次數(shù) 個位為第 0 位 第 j 位 的數(shù)字為 r 采用 while 循環(huán)從低位向高位統(tǒng)計 a 統(tǒng)計從個位算起前 j 位 0 9 個數(shù) b 如果 j 1 位為 0 去掉第 j 1 位補 0 個數(shù) c 統(tǒng)計第 j 1 位出現(xiàn) 1 r 1 個數(shù) d 統(tǒng)計第 j 1 位出現(xiàn) r 個數(shù) 基本滿足實驗要求 算法設(shè)計與分析實驗報告二 實驗名稱 分治法實現(xiàn)歸并排序算法 評分 實驗日期 2013 年 11 月 4 日 指導(dǎo)教師 姓名 專業(yè)班級 計算機 學(xué)號 201 一一 實驗實驗要求要求 1 了解用分治法求解的問題 當(dāng)要求解一個輸入規(guī)模為n 且n的取值相當(dāng) 大的問題時 如果問題可以分成k個不同子集合 得到k個不同的可獨立求解的子問題 其中 1 k n 而且子問題與原問題性質(zhì)相同 原問題的解可由這些子問題的解合并 得出 那末 對于這類問題分治法是十分有效的 2 掌握分治法的一般控制流程 DanCDanC p q globalglobal n A 1 n integerinteger m p q 1 p q n ifif Small p q thenthen return G p q elseelse m Divide p q p m q returnreturn Combine DanC p m DanC m 1 q endifendif end DanC 3 實現(xiàn)典型的分治算法的編程與上機實驗 驗證算法的時間復(fù)雜性函數(shù) 二二 實驗實驗內(nèi)容內(nèi)容 1 編程實現(xiàn)歸并排序算法 程序中加入比較次數(shù)的計數(shù)功能 輸出排序結(jié)果和 比較次數(shù) 2 輸入10組相同的數(shù)據(jù) 驗證排序結(jié)果和完成排序的比較次數(shù) 3 與復(fù)雜性函數(shù)所計算的比較次數(shù)比較 4 用表格列出比較結(jié)果 5 給出文字分析 三三 程序算法程序算法 1 歸并排序算法 procedure MERGESORT low high A low high 是一個全程數(shù)組 它含 有high low 1 0個待排序的元素 integer low high if lowmid then for k j to high do 處理剩余的元素 B i A k i i 1 repeat else for k h to mid do B i A k i i 1 repeat endif 將已歸并的集合復(fù)制到A end MERGE 2 快速排序算法 QuickSort p q 將數(shù)組A 1 n 中的元素 A p A p 1 A q 按不降次序排列 并假定A n 1 是一個確定的 且大于 A 1 n 中所有的數(shù) int p q global n A 1 n if p q then j Partition p q 1 劃分后j成為劃分元素的位置 QuickSort p j 1 QuickSort j 1 q endif end QuickSort procedure PARTITION m p 退出過程時 p帶著劃分元素所在的下標(biāo)位置 integer m p i global A m p 1 v A m i m A m 是劃分元素 loop loop i i 1 until A i v repeat i由左向右移 loop p p 1 until A p v repeat p由右向左移 if i p then call INTERCHANGE A i A p A i 和A p 換位 else exit endif repeat A m A p A p v 劃分元素在位置p End PARTITION 4 程序代程序代碼碼 1 歸并排序 include include include include define M 11 typedef int KeyType typedef int ElemType struct rec KeyType key ElemType data typedef rec sqlist M class guibing public guibing sqlist b for int i 0 i M i r i b i void output sqlist r int n for int i 0 i n i cout setw 4 r i key cout endl void xuanze sqlist b int m int n int i j k for i m i n 1 i k i for j i jb j key k j if k i rec temp b k b k b i b i temp void merge int l int m int h sqlist r2 xuanze r l m xuanze r m h output r M int i j k k i l for j m i mk if r i key r j key r2 k r i i else r2 k r j j output r2 M while j h r2 k r j j k while i m r2 k r i i k output r2 M private sqlist r void main cout guibingfa1運行結(jié)果 n sqlist a b int i j 0 k M 2 n M srand time 0 for i 0 i M i a i key rand 80 b i key 0 guibing gx a cout 排序前數(shù)組 n gx output a M cout 數(shù)組排序過程演示 n gx merge j k n b cout 排序后數(shù)組 n gx output b M cin get 2 快速排序 include include include include define MAXI 10 typedef int KeyType typedef int ElemType struct rec KeyType key ElemType data typedef rec sqlist MAXI class kuaisu public kuaisu sqlist a int m n m for int i 0 i n i b i a i void quicksort int s int t int i if s t i part s t quicksort s i 1 quicksort i 1 t else return int part int s int t int i j rec p i s j t p b s while i j while i p key j b i b j while i j b j b i b i p output return i void output for int i 0 i n i cout setw 4 b i key cout endl private sqlist b int n void main cout kuaisu1 cpp運行結(jié)果 n sqlist a1 int i n MAXI low 0 high 9 srand time 0 for i 0 i n i a1 i key rand 80 kuaisu px a1 n cout 數(shù)組排序過程演示 n px quicksort low high cout 排序后數(shù)組 n px output cin get 5 程序程序調(diào)試調(diào)試中的中的問題問題 排序算法設(shè)計比較經(jīng)典也比較難 調(diào)試中 不乏出現(xiàn)各種問題 借鑒了經(jīng)典算法 最終完成實驗 六六 實驗結(jié)實驗結(jié)果果 1 歸并排序 2 快速排序 算法設(shè)計與分析實驗報告三 實驗名稱 動態(tài)規(guī)劃算法實現(xiàn)多段圖的最短路徑問題 評分 實驗日期 2013 年 11 月 4 日 指導(dǎo)教師 姓名 專業(yè)班級 計算機 學(xué)號 2 104 一一 實驗實驗要求要求 1 理解最優(yōu)子結(jié)構(gòu)的問題 有一類問題的活動過程可以分成若干個階段 而且在任一階段后的行為依賴于該階 段的狀態(tài) 與該階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān) 這類問題的解決是多階段 的決策過程 在50年代 貝爾曼 Richard Bellman 等人提出了解決這類問題的 最優(yōu)化 原理 從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計方法 動態(tài)規(guī)劃 對于一個多階段過程問題 是否可以分段實現(xiàn)最優(yōu)決策 依賴于該問題是否有最優(yōu) 子結(jié)構(gòu)性質(zhì) 能否采用動態(tài)規(guī)劃的方法 還要看該問題的子問題是否具有重疊性質(zhì) 最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)子結(jié)構(gòu)性質(zhì) 原問題的最優(yōu)解包含了其子問題的最優(yōu)解 子問題重疊性質(zhì) 子問題重疊性質(zhì) 每次產(chǎn)生的子問題并不總是新問題 有些子問題被反復(fù)計算多次 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動態(tài)規(guī)劃算法的兩個基本要素 2 理解分段決策Bellman方程 每一點最優(yōu)都是上一點最優(yōu)加上這段長度 即當(dāng)前最優(yōu)只與上一步有關(guān) Us 初始值 uj第j段的最優(yōu)值 3 一般方法 1 找出最優(yōu)解的性質(zhì) 并刻畫其結(jié)構(gòu)特征 2 遞歸地定義最優(yōu)值 寫出動態(tài)規(guī)劃方程 3 以自底向上的方式計算出最優(yōu)值 4 根據(jù)計算最優(yōu)值時得到的信息 構(gòu)造一個最優(yōu)解 步驟1 3是動態(tài)規(guī)劃算法的基本步驟 在只需要求出最優(yōu)值的情形 步驟4可以省略 步驟 3中記錄的信息也較少 若需要求出問題的一個最優(yōu)解 則必須執(zhí)行步驟4 步驟3中記錄 的信息必須足夠多以便構(gòu)造最優(yōu)解 二二 實驗實驗內(nèi)容內(nèi)容 1 編程實現(xiàn)多段圖的最短路徑問題的動態(tài)規(guī)劃算法 2 圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表 3 要求用文件裝入5個多段圖數(shù)據(jù) 編寫從文件到鄰接表的函數(shù) min 0 iji ji j s wuu u 4 驗證算法的時間復(fù)雜性 三三 程序算法程序算法 4 程序代程序代碼碼 五五 程序程序調(diào)試調(diào)試中的中的問題問題 六六 實驗結(jié)實驗結(jié)果果 算法設(shè)計與分析實驗報告四 實驗名稱 貪心算法實現(xiàn)背包問題 評分 實驗日期 2013 年 11 月 4 日 指導(dǎo)教師 姓名 專業(yè)班級 計算機 10 1 學(xué)號 201013 一一 實驗實驗要求要求 1 優(yōu)化問題 有n個輸入 而它的解就由這n個輸入滿足某些事先給定的約束條件的某個子集組 成 而把滿足約束條件的子集稱為該問題的可行解 可行解一般來說是不唯一的 那些 使目標(biāo)函數(shù)取極值 極大或極小 的可行解 稱為最優(yōu)解 2 貪心法求優(yōu)化問題 算法思想 在貪心算法中采用逐步構(gòu)造最優(yōu)解的方法 在每個階段 都作出一個看 上去最優(yōu)的決策 在一定的標(biāo)準(zhǔn)下 決策一旦作出 就不可再更改 作出貪心決策的 依據(jù)稱為貪心準(zhǔn)則 greedy criterion 3 一般方法 1 根據(jù)題意 選取一種量度標(biāo)準(zhǔn) 2 按這種量度標(biāo)準(zhǔn)對這n個輸入排序 3 依次選擇輸入量加入部分解中 如果當(dāng)前這個輸入量的加入 不滿足約束條件 則不把此輸入加到這部分解中 procedure GREEDY A n 貪心法一般控制流程 A 1 n 包含n個輸入 solutions 將解向量solution初始化為空 for i 1 to n do x SELECT A if FEASIBLE solution x then solutions UNION solution x endif repeat return solution end GREEDY 4 實現(xiàn)典型的貪心算法的編程與上機實驗 驗證算法的時間復(fù)雜性函數(shù) 二二 實驗實驗內(nèi)容內(nèi)容 1 編程實現(xiàn)背包問題貪心算法 通過具體算法理解如何通過局部最優(yōu)實現(xiàn)全局最優(yōu) 并驗證算法的時間復(fù)雜性 2 輸入5個的圖的鄰接矩陣 程序加入統(tǒng)計prim算法訪問圖的節(jié)點數(shù)和邊數(shù)的語句 3 將統(tǒng)計數(shù)與復(fù)雜性函數(shù)所計算的比較次數(shù)比較 用表格列出比較結(jié)果 給出文字分 析 三三 程序算法程序算法 從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo) 以盡可能快的地求得更好 的解 當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進時 算法停止 該算法存在問 題 1 不能保證求得的最后解是最佳的 2 不能用來求最大或最小解問題 3 只能求滿足某些約束條件的可行解的范圍 i 一種貪婪準(zhǔn)則為 從剩余的物品中 選出可以裝入背包的價值最大的物品 利用這種規(guī) 則 價值最大的物品首先被裝入 假設(shè)有足夠容量 然后是下一個價值最大的物品 如此 繼續(xù)下去 這種策略不能保證得到最優(yōu)解 例如 考慮 n 2 w 100 10 10 p 20 15 15 c 105 當(dāng)利用價值貪婪準(zhǔn)則時 獲得的解為 x 1 0 0 這種方案的總價值為 2 0 而最 優(yōu)解為 0 1 1 其總價值為 3 0 ii 另一種方案是重量貪婪準(zhǔn)則是 從剩下的物品中選擇可裝入背包的重量最小的物品 雖然這種規(guī)則對于前面的例子能產(chǎn)生最優(yōu)解 但在一般情況下則不一定能得到最優(yōu)解 考 慮 n 2 w 10 20 p 5 100 c 2 5 當(dāng)利用重量貪婪策略時 獲得的解為 x 1 0 比最優(yōu) 解 0 1 要差 iii 還有一種貪婪準(zhǔn)則 就是我們教材上提到的 認(rèn)為 每一項計算 yi vi si 即該項值和 大小的比 再按比值的降序來排序 從第一項開始裝背包 然后是第二項 依次類推 盡 可能的多放 直到裝滿背包 有的參考資料也稱為價值密度 pi wi 貪婪算法 這種策略也不能保證得到最優(yōu)解 利用此 策略試解 n 3 w 20 15 15 p 40 25 25 c 30 時的最優(yōu)解 雖然按 pi wi 非遞 增 減 的次序裝入物品不能保證得到最優(yōu)解 但它是一個直覺上近似的解 而且這是解決普通背包問題的最優(yōu)解 因為在選擇物品 i 裝入背包時 可以選擇物品 i 的 一部分 而不一定要全部裝入背包 1 i n 4 程序代程序代碼碼 include iostream using namespace std struct goodinfo float p 物品效益 float w 物品重量 float X 物品該放的數(shù)量 int flag 物品編號 物品信息結(jié)構(gòu)體 void Insertionsort goodinfo goods int n int j i for j 2 jgoods i p goods i 1 goods i i goods i 1 goods 0 按物品效益 重量比值做升序排列 void bag goodinfo goods float M int n float cu int i j for i 1 i n i goods i X 0 cu M 背包剩余容量 for i 1 icu 當(dāng)該物品重量大與剩余容量跳出 break goods i X 1 cu cu goods i w 確定背包新的剩余容量 if i n goods i X cu goods i w 該物品所要放的量 按物品編號做降序排列 for j