《算法設計與分析》實驗報告

《《算法設計與分析》實驗報告》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、華東理工大學（計12）算法設計與分析實驗報告（1）學號：X姓名：何意班級：計131成績：實驗名稱：算法概述實驗地點：所使用的工具軟件及環(huán)境：Win7,VisualC++/Java一、實驗目的：熟悉數據結構和基本的排序和搜索算法，熟悉編程語言的集成開發(fā)環(huán)境，掌握程序設計與實現的能力，分析算法的復雜度。二、實驗內容描述：（在該章題目庫中選擇5個題目，填寫題目內容及輸入輸出要求。）1、數列有序!Description有n(n<=100)個整數，已經按照從小到大順序排列好，現在另外給一個整數x，請將該數插入到序列中，并使新的序列仍然有序。Input輸入數據包含多個測試實例，每組

2、數據由兩行組成，第一行是n和m，第二行是已經有序的n個數的數列。n和m同時為0標示輸入數據的結束，本行不做處理。Output對于每個測試實例，輸出插入新的元素后的數列。SampleInput33 124 00SampleOutput12342、絕對值排序Description輸入n(n<=100)個整數，按照絕對值從大到小排序后輸出。題目保證對于每一個測試實例，所有的數的絕對值都不相等。Input輸入數據有多組，每組占一行，每行的第一個數字為n,接著是n個整數，n=0表示輸入數據的結束，不做處理。Output對于每個測試實例，輸出排序后的結果，兩個數之間用一個空格隔開。

3、每個測試實例占一行。SampleInput33-42 4012-3 0SampleOutput15華東理工大學（計12）算法設計與分析-432 -32103、查找最大元素Description對于輸入的每個字符串，查找其中的最大字母，在該字母后面插入字符串“(max)”。Input輸入數據包括多個測試實例，每個實例由一行長度不超過100的字符串組成，字符串僅由大小寫字母構成。Output對于每個測試實例輸出一行字符串，輸出的結果是插入字符串“(max)”后的結果，如果存在多個最大的字母，就在每一個最大字母后面都插入"(max)"。SampleInputabcdefgfe

4、dcba xxxxxSampleOutputabcdefg(max)fedcba x(max)x(max)x(max)x(max)x(max)4、數值統(tǒng)計Description統(tǒng)計給定的n個數中，負數、零和正數的個數。Input輸入數據有多組，每組占一行，每行的第一個數是整數n（n<100），表示需要統(tǒng)計的數值的個數，然后是n個實數；如果n=0，則表示輸入結束，該行不做處理。Output對于每組輸入數據，輸出一行a,b和c，分別表示給定的數據中負數、零和正數的個數。SampleInput60123-10 512340.5 0SampleOutput123 0055、手機

5、短號Description大家都知道，手機號是一個11位長的數字串，同時，作為學生，還可以申請加入校園網，如果加入成功，你將另外擁有一個短號。假設所有的短號都是是6+手機號的后5位，比如號碼為的手機，對應的短號就是?，F在，如果給你一個11位長的手機號碼，你能找出對應的短號嗎？Input輸入數據的第一行是一個N(N<=200)，表示有N個數據，接下來的N行每一行為一個11位的手機號碼。15華東理工大學（計12）算法設計與分析Output輸出應包括N行，每行包括一個對應的短號，輸出應與輸入的順序一致。SampleInput2 SampleOutput 三、程序運行結果（說

6、明設計思路，解釋使用的數據結構，顯示代碼，計算時間復雜度）1、數列有序!l設計思路：使用一個一維數組存放數列元素，依次比較數列元素與插入數字的大小，直到找到第一個比插入數字大的元素，記錄其所在的位置標號K，將要插入的數字插入第K個位置即可。l數據結構：用一維數組保存給定的有序數列。l本程序主要耗費的時間是用在尋找插入位置K的單層循環(huán)中，因此時間復雜度為O(n)。l代碼如下：#includeusingnamespacestd;intmain(){intdata[101];//data數組用來存放輸入的數列intn,m;inti,k;cin>>n>>m;

7、while(n!=0&&m!=0){for(i=0;i>data[i];for(i=0;i=m){k=i;break;}for(i=n;i>=k;i--)data[i]=data[i-1];//插入位置之后的數列順序后移一位data[k]=m;//將m插入for(i=0;i>n>>m;//輸入下一組n和m}