《《算法設(shè)計與分析》實驗報告》由會員分享,可在線閱讀,更多相關(guān)《《算法設(shè)計與分析》實驗報告(15頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、華東理工大學(xué)(計12) 算法設(shè)計與分析 實 驗 報 告 ( 1 )學(xué)號: X2014002 姓名: 何意 班級: 計131 成績:實驗名稱:算法概述實驗地點:所使用的工具軟件及環(huán)境:Win7, Visual C+/Java 一、實驗?zāi)康模菏煜?shù)據(jù)結(jié)構(gòu)和基本的排序和搜索算法,熟悉編程語言的集成開發(fā)環(huán)境,掌握程序設(shè)計與實現(xiàn)的能力,分析算法的復(fù)雜度。 2、 實驗內(nèi)容描述:(在該章題目庫中選擇5個題目,填寫題目內(nèi)容及輸入輸出要求。)1、數(shù)列有序!Description有n(n=100)個整數(shù),已經(jīng)按照從小到大順序排列好,現(xiàn)在另外給一個整數(shù)x,請將該數(shù)插入到序列中,并使新的序列仍然有序。Input輸入數(shù)
2、據(jù)包含多個測試實例,每組數(shù)據(jù)由兩行組成,第一行是n和m,第二行是已經(jīng)有序的n個數(shù)的數(shù)列。n和m同時為0標示輸入數(shù)據(jù)的結(jié)束,本行不做處理。Output對于每個測試實例,輸出插入新的元素后的數(shù)列。SampleInput3 31 2 40 0SampleOutput1 2 3 42、絕對值排序Description輸入n(n=100)個整數(shù),按照絕對值從大到小排序后輸出。題目保證對于每一個測試實例,所有的數(shù)的絕對值都不相等。Input輸入數(shù)據(jù)有多組,每組占一行,每行的第一個數(shù)字為n,接著是n個整數(shù),n=0表示輸入數(shù)據(jù)的結(jié)束,不做處理。 Output對于每個測試實例,輸出排序后的結(jié)果,兩個數(shù)之間用一個
3、空格隔開。每個測試實例占一行。SampleInput3 3 -4 24 0 1 2 -30SampleOutput-4 3 2-3 2 1 03、查找最大元素Description對于輸入的每個字符串,查找其中的最大字母,在該字母后面插入字符串“(max)”。Input輸入數(shù)據(jù)包括多個測試實例,每個實例由一行長度不超過100的字符串組成,字符串僅由大小寫字母構(gòu)成。Output對于每個測試實例輸出一行字符串,輸出的結(jié)果是插入字符串“(max)”后的結(jié)果,如果存在多個最大的字母,就在每一個最大字母后面都插入(max)。SampleInputabcdefgfedcbaxxxxxSampleOutpu
4、tabcdefg(max)fedcbax(max)x(max)x(max)x(max)x(max)4、數(shù)值統(tǒng)計Description統(tǒng)計給定的n個數(shù)中,負數(shù)、零和正數(shù)的個數(shù)。Input輸入數(shù)據(jù)有多組,每組占一行,每行的第一個數(shù)是整數(shù)n(n100),表示需要統(tǒng)計的數(shù)值的個數(shù),然后是n個實數(shù);如果n=0,則表示輸入結(jié)束,該行不做處理。Output對于每組輸入數(shù)據(jù),輸出一行a,b和c,分別表示給定的數(shù)據(jù)中負數(shù)、零和正數(shù)的個數(shù)。SampleInput6 0 1 2 3 -1 05 1 2 3 4 0.50 SampleOutput1 2 30 0 55、手機短號Description大家都知道,手機號
5、是一個11位長的數(shù)字串,同時,作為學(xué)生,還可以申請加入校園網(wǎng),如果加入成功,你將另外擁有一個短號。假設(shè)所有的短號都是是 6+手機號的后5位,比如號碼為13512345678的手機,對應(yīng)的短號就是645678?,F(xiàn)在,如果給你一個11位長的手機號碼,你能找出對應(yīng)的短號嗎?Input輸入數(shù)據(jù)的第一行是一個N(N = 200),表示有N個數(shù)據(jù),接下來的N行每一行為一個11位的手機號碼。Output輸出應(yīng)包括N行,每行包括一個對應(yīng)的短號,輸出應(yīng)與輸入的順序一致。SampleInput21351234567813787654321SampleOutput645678654321三、程序運行結(jié)果(說明設(shè)計思
6、路,解釋使用的數(shù)據(jù)結(jié)構(gòu),顯示代碼,計算時間復(fù)雜度) 1、 數(shù)列有序!l 設(shè)計思路:使用一個一維數(shù)組存放數(shù)列元素,依次比較數(shù)列元素與插入數(shù)字的大小,直到找到第一個比插入數(shù)字大的元素,記錄其所在的位置標號K,將要插入的數(shù)字插入第K個位置即可。l 數(shù)據(jù)結(jié)構(gòu):用一維數(shù)組保存給定的有序數(shù)列。l 本程序主要耗費的時間是用在尋找插入位置K的單層循環(huán)中,因此時間復(fù)雜度為O(n)。l 代碼如下:#include using namespace std;int main()int data101;/data數(shù)組用來存放輸入的數(shù)列int n,m;int i,k;cinnm;while(n!=0 & m!=0)for
7、(i=0;idatai;for(i=0;i=m)k=i;break;for(i=n;i=k;i-)datai=datai-1;/插入位置之后的數(shù)列順序后移一位datak=m;/將m插入for(i=0;in;i+)/保存結(jié)果 coutdatai” ”; coutdatannm;/輸入下一組n和mreturn 0;2、絕對值排序3、查找最大元素4、數(shù)值統(tǒng)計5、手機短號 任課教師簽名: 2014年 月 日實 驗 報 告 ( 2 )學(xué)號: 姓名: 班級: 成績:實驗名稱:遞歸與分治算法實驗地點:所使用的工具軟件及環(huán)境:Win7, Visual C+/Java 一、實驗?zāi)康模和ㄟ^上機實驗,要求掌握遞歸與
8、分治法算法的問題描述、算法設(shè)計思想、程序設(shè)計和算法復(fù)雜性分析等。 二、實驗內(nèi)容描述:(在該章題目庫中選擇題目,填寫題目內(nèi)容及輸入輸出要求)三、程序運行結(jié)果(說明設(shè)計思路,解釋使用的數(shù)據(jù)結(jié)構(gòu),顯示代碼,計算時間復(fù)雜度) 任課教師簽名: 2014年 月 日實 驗 報 告 ( 3 )學(xué)號: 姓名: 班級: 成績:實驗名稱:動態(tài)規(guī)劃實驗地點:所使用的工具軟件及環(huán)境:Win7, Visual C+/Java 一、實驗?zāi)康模豪斫鈩討B(tài)規(guī)劃法的設(shè)計思想,分析是否滿足最優(yōu)子結(jié)構(gòu)性質(zhì),刻畫其結(jié)構(gòu)特征,遞歸地定義最優(yōu)值(動態(tài)規(guī)劃方程),以自底向上的方式計算出最優(yōu)值,構(gòu)造最優(yōu)解。掌握動態(tài)規(guī)劃的算法框架和設(shè)計策略。 二
9、、實驗內(nèi)容描述:(在該章題目庫中選擇題目,填寫題目內(nèi)容及輸入輸出要求)三、程序運行結(jié)果(說明設(shè)計思路,解釋使用的數(shù)據(jù)結(jié)構(gòu),顯示代碼,計算時間復(fù)雜度) 任課教師簽名: 2014年 月 日實 驗 報 告 ( 4 )學(xué)號: 姓名: 班級: 成績:實驗名稱:貪心算法實驗地點:所使用的工具軟件及環(huán)境:Win7, Visual C+/Java 一、實驗?zāi)康模豪斫庳澬乃惴ǖ脑O(shè)計思想,掌握貪心算法的算法框架和設(shè)計策略,選取度量標準,逐步構(gòu)造最優(yōu)解。 二、實驗內(nèi)容描述:(在該章題目庫中選擇題目,填寫題目內(nèi)容及輸入輸出要求)三、程序運行結(jié)果(說明設(shè)計思路,解釋使用的數(shù)據(jù)結(jié)構(gòu),顯示代碼,計算時間復(fù)雜度) 任課教師簽
10、名: 2014年 月 日實 驗 報 告 ( 5 )學(xué)號: 姓名: 班級: 成績:實驗名稱:回溯法實驗地點:所使用的工具軟件及環(huán)境:Win7, Visual C+/Java 一、實驗?zāi)康模豪斫饣厮莘ǖ脑O(shè)計思想,回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。掌握從包含問題的所有解的解空間樹中,按照深度優(yōu)先的策略,從根結(jié)點出發(fā)搜索解空間樹的過程。掌握回溯法的算法框架和設(shè)計策略。 二、實驗內(nèi)容描述:(在該章題目庫中選擇題目,填寫題目內(nèi)容及輸入輸出要求)三、程序運行結(jié)果(說明設(shè)計思路,解釋使用的數(shù)據(jù)結(jié)構(gòu),顯示代碼,計算時間復(fù)雜度) 任課教師簽名: 2014年 月 日實 驗 報 告 ( 6 )學(xué)號: 姓名: 班級: 成績:實驗名稱:分支限界法實驗地點:所使用的工具軟件及環(huán)境:Win7, Visual C+/Java 一、實驗?zāi)康模豪斫夥种藿绶ǖ脑O(shè)計思想,掌握分支限界法的算法框架和設(shè)計策略。 二、實驗內(nèi)容描述:(在該章題目庫中選擇題目,填寫題目內(nèi)容及輸入輸出要求)三、程序運行結(jié)果(說明設(shè)計思路,解釋使用的數(shù)據(jù)結(jié)構(gòu),顯示代碼,計算時間復(fù)雜度) 任課教師簽名: 2014年 月 日15