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

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