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

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標(biāo)示輸入數(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ù)中，負(fù)數(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ù)中負(fù)數(shù)、零和正數(shù)的個數(shù)。sampleinput6 0 1 2 3 -1 05 1 2 3 4 0.50 sampleoutput1 2 30 0 55、手機(jī)短號description大家都知道，手機(jī)號

5、是一個11位長的數(shù)字串，同時，作為學(xué)生，還可以申請加入校園網(wǎng)，如果加入成功，你將另外擁有一個短號。假設(shè)所有的短號都是是 6+手機(jī)號的后5位，比如號碼手機(jī)，對應(yīng)的短號就是645678?，F(xiàn)在，如果給你一個11位長的手機(jī)號碼，你能找出對應(yīng)的短號嗎？input輸入數(shù)據(jù)的第一行是一個n(n = 200)，表示有n個數(shù)據(jù)，接下來的n行每一行為一個11位的手機(jī)號碼。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ù)字大的元素，記錄其所在的位置標(biāo)號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、手機(jī)短號 任課教師簽名： 2014年 月 日實 驗 報 告 （ 2 ）學(xué)號： 姓名： 班級： 成績：實驗名稱：遞歸與分治算法實驗地點：所使用的工具軟件及環(huán)境：win7, visual c+/java 一、實驗?zāi)康模和ㄟ^上機(jī)實驗，要求掌握遞歸與

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è)計策略，選取度量標(biāo)準(zhǔn)，逐步構(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é)號： 姓名： 班級： 成績：實驗名稱：分支限界法實驗地點：所使用的工具軟件