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

1、計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告目錄 TOC o 1-5 h z 實(shí)驗(yàn)一1實(shí)驗(yàn)題目1問(wèn)題描述1算法設(shè)計(jì)1算法分析1源代碼1運(yùn)行結(jié)果2實(shí)驗(yàn)二2實(shí)驗(yàn)題目2問(wèn)題描述2算法設(shè)計(jì)2算法分析2源代碼2運(yùn)行結(jié)果4實(shí)驗(yàn)三5實(shí)驗(yàn)題目5問(wèn)題描述5算法設(shè)計(jì)5算法分析5源代碼5運(yùn)行結(jié)果6實(shí)驗(yàn)一實(shí)驗(yàn)題目7集合劃分問(wèn)題問(wèn)題描述n個(gè)元素的集合1, 2,，n可以劃分為若干非空子集。例如，當(dāng)n=4時(shí)， 集合1，2, 3, 4可以劃分為15個(gè)不同的非空子集。算法設(shè)計(jì)給定正整數(shù)n，計(jì)算出n個(gè)元素的集合1，2，n可以劃分為多少個(gè)不同 的非空子集。算法分析本算法實(shí)現(xiàn)采用分治法思想，F(xiàn)(n,m)=F(n-1,m-1)+m*F(n-1,m)。

2、假設(shè)將m個(gè) 元素分解到n個(gè)集合中，首先考慮將(m - (n - 1)個(gè)元素分到第一個(gè)集 合中，將余下的(n - 1)個(gè)元素分別分配到余下的(n - 1)個(gè)集合中，然后再 考慮將(m - (n - 2)個(gè)元素分配到第一個(gè)集合中，將余下的(n - 2)個(gè) 元素分別分配到余下的(n - 1)集合中，依此類推，直到后面的有一個(gè)集合中 的元素個(gè)數(shù)比第一個(gè)集合中的元素個(gè)數(shù)多為止。源代碼#include using namespace std;int compute_bell(int row,int position)if(row=1)return 1;if(row = 2 & position =1)re

3、turn 1;elseif(position = 1)return compute_bell(rowT,rowT);elsereturn compute_bell(row,position-1) + compute_bell(row-1,position-1);int main()int n=0;int m;coutplease input a number.n;m=compute_bell(n,n);coutthe resule is mendl;運(yùn)行結(jié)果I D:PQgran-i Files (xB6)DEV-C3Pworkspacesuanfiplease input a number t

4、he p-esziile is： 52請(qǐng)按任意鍵繼成-實(shí)驗(yàn)二實(shí)驗(yàn)題目1獨(dú)立任務(wù)最優(yōu)調(diào)度問(wèn)題問(wèn)題描述用2臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)。設(shè)第i個(gè)作業(yè)交給機(jī)器A處理時(shí)需要時(shí) 間ai，若由機(jī)器B來(lái)處理，則需要時(shí)間bi。由于各作業(yè)的特點(diǎn)和機(jī)器的性能關(guān) 系，很可能對(duì)于某些i,有aiNbi，而對(duì)于某些j,j尹i,有aj bj。既不能將 一個(gè)作業(yè)分開(kāi)由2臺(tái)機(jī)器處理，也沒(méi)有一臺(tái)機(jī)器能同時(shí)處理2個(gè)作業(yè)。設(shè)計(jì)一個(gè) 動(dòng)態(tài)規(guī)劃算法，使得這2臺(tái)機(jī)器處理完這n個(gè)作業(yè)的時(shí)間最短(從任何一臺(tái)機(jī)器 開(kāi)工到最后一臺(tái)機(jī)器停工的總時(shí)間)。研究一個(gè)實(shí)例：(a1,a2,a3,a4,a5,a6)= (2,5,7,10,5,2) ； (b1,b

5、2,b3,b4,b5,b6) = (3,8,4,11,3,4)。算法設(shè)計(jì)對(duì)于給定的2臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)，找出一個(gè)最優(yōu)調(diào)度方案，使2 臺(tái)機(jī)器處理完這n個(gè)作業(yè)的時(shí)間最短。算法分析當(dāng)完成k個(gè)作業(yè)，設(shè)機(jī)器A花費(fèi)了x時(shí)間，機(jī)器B所花費(fèi)時(shí)間的最小值肯定 是x的一個(gè)函數(shù)，設(shè)Fkx表示機(jī)器B所花費(fèi)時(shí)間的最小值。則 Fkx=Min( Fk-1x+bk, Fk-1x-ak ；其中 Fk-1x+bk表示 第k個(gè)作業(yè)由機(jī)器B來(lái)處理(完成k-1個(gè)作業(yè)時(shí)機(jī)器A花費(fèi)的時(shí)間仍是x)， Fk-1x-ak表示第k個(gè)作業(yè)由機(jī)器A處理(完成k-1個(gè)作業(yè)時(shí)機(jī)器A花費(fèi)的 時(shí)間是x-ak)。那么單個(gè)點(diǎn)對(duì)較大值Max(x, Fkx)

6、，表示此時(shí)(即機(jī)器A花費(fèi)x時(shí)間 的情況下)所需要的總時(shí)間。而機(jī)器A花費(fèi)的時(shí)間x是變化的，即x=0,1,2 x(max)，由此構(gòu)成了點(diǎn)對(duì)較大值序列。要求整體時(shí)間最短，取這些點(diǎn)對(duì)較大值序 列中最小的即可。源代碼#include#include#includeusing namespace std;const int SIZE=50;const int MAXINT=999;int main()(while(1)(int N,aSIZE,bSIZE,SumASIZE,SumBSIZE;int tempSumA,tempSumB,MinSum;int i=0,j,k;tempSumA二tempSumB

7、=0;int data;int oriDataSIZE;ifstream ifile;ifile.open(input.txt)；if(ifile.eof()(cerrFail to open the file input.txtdata)(oriDatai+=data;N=(int)oriData0;for (i=1;i=N;i+)(ai=oriDatai;tempSumA+=ai;SumAi=tempSumA;for (i=1,j=N+1;j=2*N;j+,i+)(bi=oriDataj;tempSumB+=bi;SumBi=tempSumB;coutInput.txt Data:endl

8、;coutoriData0endl;for (i=1;i=2*N;)(coutoriDatai;i+;coutoriDataiendl;i+;couttempSumA)?tempSumA:tempSumB;int *MaxTime二new int MinSum+1;int *F=new int*N+1;for(i=0;iN+1;i+)Fi=new int MinSum+1;SumB0=0;for(i=0;i=N;i+)(Fi0=SumBi;for(j=1;j=MinSum;j+)Fij=0;int temp;for(k=1;kSumBk)?SumBk:SumAk;for(i=1;i=ak)Fk

9、i = (Fk-1i+bkFk-1i-ak)?Fk-1i+bk:Fk-1i-ak ;else Fki=Fk-1i+bk;temp=MAXINT;for(i=0;iFNi)?i:FNi;if(tempMaxTimei)temp=MaxTimei;ofstream ofile;ofile.open(output.txt)；ofiletempendl;ofile.close();coutthe best time is tempPogram Files (k35 iDEV-CDPworkspacemaInput_txt Data: 2004288028the best time is 8實(shí)驗(yàn)三實(shí)驗(yàn)題

10、目9汽車加油問(wèn)題問(wèn)題描述一輛汽車加滿油后可行駛nkm。旅途中有若干加油站。設(shè)計(jì)一個(gè)有效算法， 指出應(yīng)在那些加油站?？考佑?，使沿途加油次數(shù)最少。并證明算法能產(chǎn)生一個(gè)最 優(yōu)解。算法設(shè)計(jì)對(duì)于給定的n和k個(gè)加油站位置，計(jì)算最少加油次數(shù)。算法分析將一輛汽車在出發(fā)地加滿油，每次加滿可行駛nkm，利用相鄰加油站之間距 離d是否可行駛的距離，并利用貪心算法計(jì)算最優(yōu)解。源代碼#include void Greedy(int d,int n,int k) (int sum = 0;int i=0;int j=0;for( i = 0;i n) (printf(No Solutionn)；return;for( i

11、 = 0,j = 0;i n) (sum+;j = di;printf(min refuel time:%dn,sum);int main() (int i,n,k;int d100;printf(input the length:n)；scanf(%d,&n);printf(input the number of stations:n)； scanf(d，&k);printf(input the length of two station:n)；for(i = 0;i k+1;i+)scanf(d，&di);Greedy(d,n,k+1 );return 0;運(yùn)行結(jié)果I D:Program

12、Files (EV-CPPu.orpatzeXnnain.input： the Length：2input the nunber of stat ions：:iinput the length of tifD stat ion:12in in pef uel t ime: 1請(qǐng)按任意鍵繼續(xù).實(shí)驗(yàn)四實(shí)驗(yàn)題目最短加法鏈問(wèn)題問(wèn)題描述最優(yōu)求幕問(wèn)題：給定一個(gè)正整數(shù)n和一個(gè)實(shí)數(shù)x,如何用最少的乘法次數(shù) 計(jì)算出xn。例如，可以用6次乘法逐步計(jì)算x23如下：x,x2 , x3, x5, x10, x20, x23?？梢宰C明，計(jì)算x23的幕序列中各幕次組成正整數(shù)n的一個(gè)加法鏈: 1=a0 al a2 ar=na

13、r= aj+ ak,k=jI,i=1,2,，r上述最優(yōu)求幕問(wèn)題相應(yīng)于正整數(shù)n的最短加法鏈問(wèn)題，即求n的一個(gè)加法 鏈?zhǔn)蛊溟L(zhǎng)度r達(dá)到最小。正整數(shù)n的最短加法鏈長(zhǎng)度記為l(n)。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第1行有1個(gè)正整數(shù)n。結(jié)果輸出：將計(jì)算的最短加法鏈長(zhǎng)度l(n)和相應(yīng)的最短加法鏈輸出到文件 output.txt。算法設(shè)計(jì)對(duì)于給定的正整數(shù)n,計(jì)算相應(yīng)于正整數(shù)n的最短加法鏈。算法分析問(wèn)題的解空間是一棵排列數(shù)，元素的孩子數(shù)目是其祖先和自己的一個(gè)全排列。利 用迭代回溯遍歷每個(gè)活結(jié)點(diǎn)，求出每個(gè)加法鏈的長(zhǎng)度并進(jìn)行比較，記錄最小值進(jìn) 行輸出。源代碼#include #include #i

14、nclude#include#includeusing namespace std;int minStep = INT_MAX;int a1000;int chain20;int n;迭代回溯法求解int backtrack(int step) ( if(astep = n) (if(step minStep) ( minStep = step;for(int i=1; i=1; i-) ( if(2*ai astep)for(int j=i; j=1; j-) int k = ai + aj; astep+1 = k;if(kastep & k n;in.close();求解問(wèn)題a1 = 1

15、;backtrack(1);輸出數(shù)據(jù)ofstream out(output.txt)；out minStep endl;for(int i=1; iminStep; i+) ( outchaini;/最后一個(gè)元素out chainminStep;out.close();system(PAUSE)；return EXIT_SUCCESS;實(shí)驗(yàn)截圖：輸入：| input.txt -記聿本文件(5 靠鼻日 悟式存 M 將動(dòng)而輸出： Lltput.txt -此序本文件舊釜事正）格式。亙看熟址H）412 4 5實(shí)驗(yàn)五：實(shí)驗(yàn)題目旅行售貨員問(wèn)題問(wèn)題描述某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或

16、旅費(fèi)）。他要選擇一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍，最后回到駐地的路線，使總的路程（或總旅費(fèi)）最小。算法設(shè)計(jì)對(duì)于給定的鄰接矩陣圖，計(jì)算花費(fèi)最少的周游路。算法分析數(shù)據(jù)輸入：由input.txt文件提供輸入，第一行n表示城市數(shù)目，之后為n行n列表示城市的鄰接矩陣，-1表示兩個(gè)城市直接沒(méi)有路。數(shù)據(jù)輸出：將最小花費(fèi)輸出到output.txt。本算法采用最小值堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列。其優(yōu)先級(jí)是節(jié)點(diǎn)當(dāng)前費(fèi)用。堆的數(shù)據(jù)結(jié) 構(gòu)不再贅述。對(duì)排列數(shù)的解空間進(jìn)行廣度優(yōu)先遍歷，每次將活結(jié)點(diǎn)入堆，從堆頂取出結(jié)點(diǎn)并展開(kāi)，記錄最小花費(fèi)，當(dāng)堆中元素為空時(shí)輸出結(jié)果到output.txt。#include#include#include

17、#includetypedef struct point(int x,y;point;double get_distance(const point* a, const point* b);int cmp_point(const void* a, const void* b)(point* p_a = (point*)a;point* p_b = (point*)b;return p_a-x - p_b-x;int point_size;point* points = NULL;double* distances;double* results = NULL;void read_in()(in

18、t i,j;scanf(d，&point_size);points = (point*)malloc(sizeof(point) * point_size);for(i = 0; i point_size; i+)(scanf(%d%d,&(pointsi.x),&(pointsi.y);distances = (double*)malloc(sizeof(double*) * point_size);for(i = 0; i point_size; i+)(distancesi = (double*)malloc(sizeof(double) * point_size);distancesi

19、i = 0;for(j = i + 1; j x;int y1 = a-y;int x2 = b-x;int y2 = b-y;return sqrt(x2-x1) * (x2-x1) + (y2-y1) * (y2-y1);double get_min()(int i,k,j;for(i = 2; i point_size; i+)(resultsi = INT_MAX;for(k = 1; k i; k+)double sum_distance = 0.0;double k_distance = distancesk-1k;double k_i_distance = distancesk-

20、1i;for(j = k; j resultsk + sum_distance + k_i_distance-k_distance)(resultsi = resultsk + sum_distance + k_i_distance -k_distance;return resultspoint_size - 1;int main(int argc,char*argv)(read_in();printf(%.2lfn,get_min();destory();return 0;/*70 6 TOC o 1-5 h z 034152*/運(yùn)行結(jié)果如下：亍售的可題 7H 5i aE 35 4E 17

21、5 0 2 E5.58C：MJseis fldininistiatDr時(shí)間復(fù)雜度：O(n3),空間復(fù)雜度是O (n2).旅行售貨員回溯法#include#include#include#include#define N 1000double minCost = DBL_MAX;double costNN;int nodeNumber;double curCost;int recordN;int minRecordN;void readInfo()(scanf(d，&nodeNumber);int count;scanf(d,&count);int i,j;for(i = 0; i nodeNu

22、mber; i+)(for(j = 0; j nodeNumber;j+)(costij = 0;while(count-)(int left,right;scanf(d%d，&left,&right);scanf(lf,&(costleftright);costrightleft = costleftright; for(i = 0; i nodeNumber; i+)(recordi = i;void swap(int* a, int* b)(int temp = *a;*a = *b;*b = temp;/初始值depth為1,而不為0.void Backtrack(int depth)

23、(if(depth = nodeNumber)(if(costrecorddepth-10)(if(costrecorddepth-10 + curCost minCost)(minCost = costrecorddepth-10 + curCost; int i;for(i = 0; i nodeNumber; i+)(minRecordi = recordi;return;int i;for(i = depth; i nodeNumber; i+)(if(costrecorddepth-1i)(swap(record + i, record + depth);/添加該節(jié)點(diǎn).curCost

24、 += costrecorddepth-1i;int j;for(j = 0; j = i; j+)(printf(%dt, recordj);printf(n)；Backtrack(depth + 1);curCost -= costrecorddepth-1i;swap(record + i, record + depth);void writeInfo()(printf(minCost:%lfn,minCost); int i;for(i = 0; i nodeNumber; i+)(printf(%dt,minRecordi);printf(0);printf(n);int main(

25、int argc,char*argv)(readInfo();Backtrack(1);writeInfo();/*460 1 1.60 2 1.10 3 1.21 2 1.43 1.53 1.7 */截圖顯示:4 0 1 1. 0 2 1.1 B 3 1.2 1 2 1.4 TOC o 1-5 h z 3 1.53 1.71I1232I213121I32321in Cost ：5 閾閾。 |1230旅行售貨員問(wèn)題：分支限界法顯示: 使用了最小優(yōu)先級(jí)隊(duì)列： minPriority:頭文件： miqueue.h#ifndef _MINQUEUE_H#define _MINQUEUE_H #inc

26、ludetravel.h extern struct element queueN;/隊(duì)列的大小.extern int elementSize;void add_queue(struct element e);查看最小.int peel(struct element* first);刪除最小，如果說(shuō)返回NULL,標(biāo)明peek為空. int peek(struct element* first);#endifDiver.h:#ifndef _H_TRAVEL#define _H_TRAVEL#define N 1000struct element(int visitedN; /當(dāng)前節(jié)點(diǎn)是否被訪問(wèn)

27、.double cost; /當(dāng)前的花費(fèi).int visitedNumber;/當(dāng)前訪問(wèn)的節(jié)點(diǎn)的數(shù)目，當(dāng)?shù)扔趎odeNumber的時(shí)候， 說(shuō)明了訪問(wèn)結(jié)束，同時(shí)cost加上它到其實(shí)節(jié)點(diǎn)的花費(fèi)就可以得到總的花費(fèi).int lastNode; /最后被訪問(wèn)的節(jié)點(diǎn).;/最小花費(fèi).extern double minCost;兩個(gè)節(jié)點(diǎn)的花費(fèi).extern double costNN;#endifMinqueue.c:#includeminqueue.hstruct element queueN;int elementSize = 0;static void keepQueueInUp();static vo

28、id keepQueueInDown();static double cmpElement();void add_queue(struct element e)(queueelementSize = e;elementSize+;keepQueueInUp();查看最小.int peel(struct element* first)(if(elementSize = 0)(return 0;*first = queue0;return 1;刪除最小，如果說(shuō)返回NULL,標(biāo)明peek為空.int peek(struct element* first)(if(elementSize = 0)(re

29、turn 0;elementSize-;*first = queue0;queue0 = queueelementSize;keepQueueInDown(0);return 1;void keepQueueInUp()(/最后一個(gè)值可能不滿足堆的性質(zhì).int tempIndex = elementSize -1;while(tempIndex != 0)(/滿足堆性質(zhì).if(cmpElement(queue + (tempIndex - 1)/2, queue + tempIndex) =0.0) break;/進(jìn)行交換.struct element temp = queuetempInde

30、x;queuetempIndex = queue(tempIndex-1)/2;queue(tempIndex-1)/2 = temp;/繼續(xù)向上.tempIndex = (tempIndex-1)/2;void keepQueueInDown(int parent)(int left = parent * 2 + 1;int right = parent * 2 + 2;int min = parent;if(left 0.0)(min = left;if(right 0.0)(min = right;if(min != parent)(struct element temp = queueparent;queueparent = queuemin;queuemin = temp;keepQueueInDown(min);double cmpElement(struct element* a, struct element* b)(retur