《算法設(shè)計與分析》實驗報告.doc

福建師范大學(xué)協(xié)和學(xué)院本科實驗報告課程名稱： 算法設(shè)計與分析 學(xué)院（系）： 專 業(yè)： 班 級： 學(xué) 號： 學(xué)生姓名： 學(xué) 號： 學(xué)生姓名： 學(xué) 號： 學(xué)生姓名： 實驗項目實驗序號項目序號實驗項目名稱實驗成績一1快速排序2合并排序3* 尋找主元素二4遞歸求排列5* 分治找K大元素三6平面最近點對7* 分治法求棋盤覆蓋問題四8貪婪法求解普通背包問題9單源最短路徑的dijstra算法五10多段圖最短路徑（動態(tài)規(guī)劃）11* 最優(yōu)資源分配（動態(tài)規(guī)劃）六12* KMP模式串匹配130/背包問題七14* 回溯法求解巡游問題15回溯法求解0/1背包問題總分標題前加*號的實驗題目為設(shè)計實驗算法設(shè)計與分析實驗報告填寫要求一、本課程共需完成七次實驗，由十五個實驗項目組成。每一次實驗需在備選項目中選擇一個項目完成并提交一份實驗報告，批改后下發(fā)的實驗報告請保存起來，期末上交。二、實驗報告書寫要求：1. 實驗?zāi)康暮鸵螅好鞔_實驗的內(nèi)容和具體任務(wù)；2. 列出源程序，備注說明程序的基本結(jié)構(gòu)，包括程序中各部分的功能。 3. 說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并給出計算過程。4. 實驗結(jié)果與分析：給出不少于3組數(shù)據(jù)測試算法，并將每組測試數(shù)據(jù)的運行結(jié)果列出，并對調(diào)試源程序的結(jié)果進行分析，杜絕只羅列不分析；5. 討論、建議、質(zhì)疑：針對實驗中碰到的問題進行組內(nèi)以及組外討論，遇到不能解決的問題時向指導(dǎo)老師請教，并將問題的提出以及解決的過程寫入實驗報告，以作為以后學(xué)習(xí)的參考。問題要具體描述，避免抽象地羅列、籠統(tǒng)地討論；6. 全部文字敘述內(nèi)容要求簡明扼要，思路清楚；7. 實驗日期、同組員姓名寫清楚。 三、要求實驗報告字跡工整、文字簡練、數(shù)據(jù)齊全、計算正確，分析充分、具體、定量。對于抄襲實驗報告和編篡原始數(shù)據(jù)的行為，一經(jīng)發(fā)現(xiàn)，以零分處理，并根據(jù)相關(guān)條例給予處分。福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 一 遞歸與分治算法實驗（一）l 項目一 快速排序 （驗證實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及程序中各部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、 程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題試想想，這樣的排序算法有什么優(yōu)勢？能對所有的數(shù)據(jù)測試用例都使用這種算法嗎？福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 一 遞歸與分治算法實驗（一）l 項目二 合并排序 （驗證實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、 程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題為什么合并排序是思想是基于比較類排序里面最快的，它成功的地方在哪兒？福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 一 遞歸與分治算法實驗（一）l 項目三 尋找主元素 （設(shè)計實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及各部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、 程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 二 遞歸與分治算法實驗（二）l 項目四 遞歸求排列 （驗證實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及程序中各部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題試想想，遞歸思想有什么樣的優(yōu)缺點，在調(diào)試過程中，隨著數(shù)據(jù)量的增大，調(diào)試過程與結(jié)果有沒有變化？為什么？福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 二 遞歸與分治算法實驗（二）l 項目五 分治求K大元素 （設(shè)計實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題這種求K大元素與前面學(xué)過的合并排序有無關(guān)聯(lián)？仔細想一想他們的本質(zhì)。福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 三 遞歸與分治算法實驗（三）l 項目六 分治法求平面最近點對（驗證實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及程序中各部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題為什么用分治法求平面最近點對時間效率會高些，這樣的思想還能用于解決什么樣的實際問題？試舉出23個實例說明一下。福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 三 遞歸與分治算法實驗（三）l 項目七 分治求棋盤覆蓋問題 （設(shè)計實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題如果參賽隊伍數(shù)量不是2的整數(shù)冪，該如何調(diào)整算法。福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 四 貪婪算法實驗l 項目八 普通背包問題（驗證實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及程序中各部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題如果背包內(nèi)物體不能分割，這樣的方法還行得通嗎？為什么？你能從中找出什么樣的啟發(fā)？福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 四 貪婪算法實驗l 項目九 單源最短路徑問題 （驗證實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題：為什么這種方法求下來的路徑一定是最短？試分析一下它的正確性。福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 五 動態(tài)規(guī)劃算法實驗（一）l 項目十 動態(tài)規(guī)劃求解多段圖最短路徑問題（驗證試驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及程序中各部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題如果最短路徑不唯一，該如何輸出全部符合要求的路徑呢？福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 五 動態(tài)規(guī)劃算法實驗（一）項目十一 最優(yōu)資源分配方案設(shè)計 （設(shè)計實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題什么是多段圖？為什么這種方法只能用于多段圖？普通圖能不能用動態(tài)規(guī)劃來求解，為什么？福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 六 動態(tài)規(guī)劃算法實驗（二）l 項目十二 設(shè)計動態(tài)規(guī)劃算法解決模式串匹配的問題（設(shè)計實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及程序中各部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 六 動態(tài)規(guī)劃算法實驗（二）項目十三 0/1背包問題 （驗證實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題：這種方法能解決所有的0/1背包問題嗎？想想有什么條件限制沒有？舉例說明！福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期： 年 月 日 星期 組員姓名： 成績： 實 驗 七 回溯算法實驗l 項目十四 利用回溯思想設(shè)計一算法解決馬步遍歷問題（設(shè)計實驗）一、 重要的程序說明（說明程序的基本結(jié)構(gòu)以及程序中各部分的功能，以偽代碼和圖的形式說明）二、 算法復(fù)雜性分析與計算（說明程序中各部分所用的算法或原理，計算出算法時間和空間復(fù)雜性，并寫出計算過程）三、程序運行測試結(jié)果分析：四、程序調(diào)試過程中遇到的錯誤，如何討論、有何建議與質(zhì)疑五、思考題：用回溯方法求解問題時候最大的缺點是什么？這樣的問題有沒有解決的辦法，如果有，應(yīng)該從哪方面考慮去實現(xiàn)？福建師范大學(xué)協(xié)和學(xué)院實驗報告實驗日期