《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告

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