《算法設(shè)計與分析》課程設(shè)計報告-最大子段和問題

.精選.精選《算法設(shè)計與分析》課程設(shè)計報告題目：最大子段和問題院（系）：信息科學與工程學院專業(yè)班級：軟件工程1201班學生姓名：學號：指導教師：2014年12月29日至2015年1月9日華中科技大學武昌分校制算法設(shè)計與分析課程設(shè)計任務書一、設(shè)計題目最大子段和問題問題描述：給定n個整數(shù)（可能有負整數(shù)）a1，a2，…，an。求形如ai，ai+1，…aji=1，2，…n，j=1，2，…n，i≤j，求出ai，ai+1，…aj子段和的最大值。當所有整數(shù)均為負值時定義其最大子段還和為0。例如：當(a1，a2，a3，a4，a5，a6)=(-2，11，-4，13，-5，2)時，最大子段和為(a2，a3，a4)=20即=20i=2，j=4二、設(shè)計主要內(nèi)容具體要求如下：使用蠻力算法實現(xiàn)使用分治策略算法實現(xiàn)使用動態(tài)規(guī)劃算法實現(xiàn)對各種算法的時間復雜度進行分析和比較。設(shè)計出相應的菜單，通過菜單的選擇實現(xiàn)各個功能三、原始資料無四、要求的設(shè)計成果(1)實現(xiàn)該系統(tǒng)功能的程序代碼(2)撰寫符合規(guī)范要求的課程設(shè)計報告五、進程安排序號課程設(shè)計內(nèi)容學時分配備注1選題與搜集資料1天2分析與設(shè)計1天3模塊實現(xiàn)4天4系統(tǒng)調(diào)試與測試2天5撰寫課程設(shè)計報告2天合計10天六、主要參考資料[1]呂國英．算法設(shè)計與分析．第2版．北京：清華大學出版社，2011．[2]王曉東．算法設(shè)計與分析．北京，清華大學出版社，2009．[3]徐士良．計算機常用算法．第2版．北京，清華大學出版社出版，2010．指導教師（簽名）：20年月日1常用算法 61.1蠻力算法 61.2分治算法 71.3動態(tài)規(guī)劃算法 82問題分析與算法設(shè)計 92.1蠻力算法的設(shè)計 92.2分治算法的設(shè)計 92.3動態(tài)規(guī)劃算法的設(shè)計 103算法實現(xiàn) 103.2蠻力算法的實現(xiàn) 103.2分治算法的實現(xiàn) 113.3動態(tài)規(guī)劃算法的實現(xiàn) 134測試和分析 134.1蠻力算法測試 134.2蠻力算法時間復雜度的分析 154.3分治算法測試 154.4分治算法時間復雜度的分析 174.5動態(tài)規(guī)劃算法測試 174.6動態(tài)規(guī)劃算法時間復雜度的分析 194.7三種算法的比較 205總結(jié) 20參考文獻 20附錄 201常用算法1.1蠻力算法1.2分治算法1.3動態(tài)規(guī)劃算法2問題分析與算法設(shè)計2.1蠻力算法的設(shè)計2.2分治算法的設(shè)計2.3動態(tài)規(guī)劃算法的設(shè)計3算法實現(xiàn)3.2蠻力算法的實現(xiàn)3.2分治算法的實現(xiàn)3.3動態(tài)規(guī)劃算法的實現(xiàn)4測試和分析4.1蠻力算法測試4.2蠻力算法時間復雜度的分析4.3分治算法測試4.4分治算法時間復雜度的分析4.5動態(tài)規(guī)劃算法測試4.6動態(tài)規(guī)劃算法時間復雜度的分析4.7三種算法的比較5總結(jié)參考文獻[1]呂國英．算法設(shè)計與分析．第2版．北京：清華大學出版社，2011．[2]王曉東．算法設(shè)計與分析．北京，清華大學出版社，2009．附錄課程設(shè)計成績評定表成績評定項目比例得分平時成績（百分制記分