《算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告題目：最大子段和問(wèn)題院〔系〕：信息科學(xué)與工程學(xué)院專(zhuān)業(yè)班級(jí)：軟件工程1201班學(xué)生姓名：李婉秋學(xué)號(hào)：20121611035指導(dǎo)教師：彭文藝2014年12月29日至2015華中科技大學(xué)武昌分校制算法設(shè)計(jì)與分析課程設(shè)計(jì)任務(wù)書(shū)一、設(shè)計(jì)題目最大子段和問(wèn)題問(wèn)題描述：給定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)對(duì)各種算法的時(shí)間復(fù)雜度進(jìn)行分析和比擬。設(shè)計(jì)出相應(yīng)的菜單，通過(guò)菜單的選擇實(shí)現(xiàn)各個(gè)功能三、原始資料無(wú)四、要求的設(shè)計(jì)成果(1)實(shí)現(xiàn)該系統(tǒng)功能的程序代碼(2)撰寫(xiě)符合標(biāo)準(zhǔn)要求的課程設(shè)計(jì)報(bào)告五、進(jìn)程安排序號(hào)課程設(shè)計(jì)內(nèi)容學(xué)時(shí)分配備注1選題與搜集資料1天2分析與設(shè)計(jì)1天3模塊實(shí)現(xiàn)4天4系統(tǒng)調(diào)試與測(cè)試2天5撰寫(xiě)課程設(shè)計(jì)報(bào)告2天合計(jì)10天六、主要參考資料[1]呂國(guó)英．算法設(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問(wèn)題分析與算法設(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測(cè)試和分析134.1蠻力算法測(cè)試134.2蠻力算法時(shí)間復(fù)雜度的分析154.3分治算法測(cè)試154.4分治算法時(shí)間復(fù)雜度的分析174.5動(dòng)態(tài)規(guī)劃算法測(cè)試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問(wèn)題分析與算法設(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測(cè)試和分析4.1蠻力算法測(cè)試4.2蠻力算法時(shí)間復(fù)雜度的分析4.3分治算法測(cè)試4.4分治算法時(shí)間復(fù)雜度的分析4.5動(dòng)態(tài)規(guī)劃算法測(cè)試4.6動(dòng)態(tài)規(guī)劃算法時(shí)間復(fù)雜度的分析4.7三種算法的比擬5總結(jié)參考文獻(xiàn)[1]呂國(guó)英．算法設(shè)計(jì)與分析．第2版．北京：清華大學(xué)出版社，2011．[2]王曉東．算法設(shè)計(jì)與分析．北京，清華大學(xué)出版社，2009．附錄課程設(shè)計(jì)成績(jī)?cè)u(píng)定表成績(jī)?cè)u(píng)定項(xiàng)目比例得分平時(shí)成績(jī)〔百分制記分〕30%業(yè)