算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告一(簡(jiǎn)單算法設(shè)計(jì))

1、實(shí)驗(yàn)報(bào)告一課程 C+ 實(shí)驗(yàn)名稱 簡(jiǎn)單算法設(shè)計(jì) 第 1 頁(yè) 專業(yè) _數(shù)學(xué)與應(yīng)用數(shù)學(xué)_ _ 班級(jí)_ 雙師一班 學(xué)號(hào) 105012011056 姓名 陳萌 實(shí)驗(yàn)日期：2013 年 3 月 9 日 報(bào)告退發(fā) (訂正 、 重做) 一、實(shí)驗(yàn)?zāi)康?. 理解算法設(shè)計(jì)與分析的基本概念，理解解決問題的算法設(shè)計(jì)與實(shí)現(xiàn)過(guò)程；2. 掌握簡(jiǎn)單問題的算法設(shè)計(jì)與分析，能設(shè)計(jì)比較高效的算法；3. 熟悉C/C+語(yǔ)言等的集成開發(fā)環(huán)境，掌握簡(jiǎn)單程序設(shè)計(jì)與實(shí)現(xiàn)的能力。 二、實(shí)驗(yàn)內(nèi)容(一) 相等元素問題1.問題描述元素唯一性問題：給出一個(gè)整數(shù)集合，假定這些整數(shù)存儲(chǔ)在數(shù)組A1n中，確定它們中是否存在兩個(gè)相等的元素。請(qǐng)?jiān)O(shè)計(jì)出一個(gè)有效算法來(lái)解

2、決這個(gè)問題，你的算法的時(shí)間復(fù)雜性是多少？ 2. 具體要求（若在ACM平臺(tái)上提交程序，必須按此要求）平臺(tái)上1767題輸入：輸入的第一行是一個(gè)正整數(shù)m，表示測(cè)試?yán)齻€(gè)數(shù)。接下來(lái)幾行是m個(gè)測(cè)試?yán)臄?shù)據(jù)，每個(gè)測(cè)試?yán)臄?shù)據(jù)由兩行組成，其中第一行為一個(gè)正整數(shù)n (n=500)，表示整數(shù)序列的長(zhǎng)度，第二行給出整數(shù)序列，整數(shù)之間用一個(gè)空格隔開。輸出：對(duì)于每個(gè)測(cè)試?yán)敵鲆恍校粼摻M測(cè)試?yán)写嬖趦蓚€(gè)相等的元素則輸出”Yes”，否則，輸出”No”。每個(gè)測(cè)試?yán)妮敵鰯?shù)據(jù)用一行表示。3. 測(cè)試數(shù)據(jù)輸入：3 10 9 71 25 64 38 52 5 31 19 45 16 26 35 17 92 53 24 6 57 2

3、1 12 34 2 17 86 75 33 20 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91輸出：No Yes No (二) 整數(shù)集合分解1.問題描述 設(shè)計(jì)算法把一個(gè)n個(gè)元素的整數(shù)集合（n為偶數(shù)）分成兩個(gè)子集S1和S2，使得：每個(gè)新的集合中含有n/2個(gè)元素，且S1中的所有元素的和與S2中的所有元素的和的差最大。 2. 具體要求（若在ACM平臺(tái)上提交程序，必須按此要求）平臺(tái)上1768題輸入的第一行是一個(gè)正整數(shù)m，表示測(cè)試?yán)齻€(gè)數(shù)。接下來(lái)幾行是m個(gè)測(cè)試?yán)臄?shù)據(jù)，每個(gè)測(cè)試?yán)臄?shù)據(jù)由兩行組成，其中第一行為一個(gè)正整數(shù)n (n為偶數(shù)，且n

4、=500)，表示原整數(shù)集合的長(zhǎng)度，第二行給出這n個(gè)整數(shù)序列，整數(shù)之間用一個(gè)空格隔開。輸出：對(duì)于每個(gè)測(cè)試?yán)敵鰞尚?，分別表示新生成的整數(shù)集合。其中，第一行是元素和比較小的整數(shù)集合，第二行是元素和比較大的整數(shù)集合，整數(shù)之間用一個(gè)空格隔開。兩個(gè)測(cè)試?yán)妮敵鰯?shù)據(jù)之間用一個(gè)空行隔開，最后一個(gè)測(cè)試?yán)鬅o(wú)空行3. 測(cè)試數(shù)據(jù)輸入： 22268 25 34 16 2 37 3 95 76 57 21 13 4 78 29 6 17 39 51 20 43 12 2628 3 48 59 14 32 47 51 42 61 9 24 52 78 65 2 37 78 51 73 29 7 26 95 37 2輸出

5、： 2 3 4 6 12 13 16 17 20 21 25 29 34 37 39 43 51 57 68 76 78 95 2 2 3 7 9 14 24 26 28 29 32 37 37 42 47 48 51 51 52 59 61 62 65 73 78 95三、實(shí)驗(yàn)步驟1.程序如下：#include#define N 500int main()int i,j,m,n,t,k=0;int aN;printf(請(qǐng)輸入測(cè)試的數(shù)的個(gè)數(shù):n);scanf(%d,&m);for(t=0;tm;t+)printf(請(qǐng)輸入序列的長(zhǎng)度:n); scanf(%d,&n); printf(請(qǐng)輸入序列的

6、數(shù)字:n); for(i=0;in;i+)scanf(%d,&ai); for(i=0;in;i+) for(j=i+1;jn;j+) if(ai=aj) k=1; if(k=1) printf(yesn); else printf(NOn); return 0;2. 程序如下： #include#define N 500int main()int aN;int n,k,t,j,i,b,m; printf(請(qǐng)輸入示例的個(gè)數(shù):n);scanf(%d,&m);for(b=0;bm;b+)printf(請(qǐng)輸入數(shù)的個(gè)數(shù):n); scanf(%d,&n); printf(請(qǐng)輸入該組數(shù):n); for(i=0;in;i+)scanf(%d,&ai); for(i=0;in;i+) k=i; for(j=i+1;jaj) k=j;if(i!=k) t=ai; ai=ak; ak=t; for(i=0;in/2;i+) printf(%3d,ai); printf(n); for( ;in;i+) printf(%3d,ai); printf(n); re