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

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

2、假設(shè)將m個 元素分解到n個集合中，首先考慮將(m - (n - 1)個元素分到第一個集 合中，將余下的(n - 1)個元素分別分配到余下的(n - 1)個集合中，然后再 考慮將(m - (n - 2)個元素分配到第一個集合中，將余下的(n - 2)個 元素分別分配到余下的(n - 1)集合中，依此類推，直到后面的有一個集合中 的元素個數(shù)比第一個集合中的元素個數(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;運行結(jié)果I D:PQgran-i Files (xB6)DEV-C3Pworkspacesuanfiplease input a number t

4、he p-esziile is： 52請按任意鍵繼成-實驗二實驗題目1獨立任務(wù)最優(yōu)調(diào)度問題問題描述用2臺處理機A和B處理n個作業(yè)。設(shè)第i個作業(yè)交給機器A處理時需要時 間ai，若由機器B來處理，則需要時間bi。由于各作業(yè)的特點和機器的性能關(guān) 系，很可能對于某些i,有aiNbi，而對于某些j,j尹i,有aj bj。既不能將 一個作業(yè)分開由2臺機器處理，也沒有一臺機器能同時處理2個作業(yè)。設(shè)計一個 動態(tài)規(guī)劃算法，使得這2臺機器處理完這n個作業(yè)的時間最短(從任何一臺機器 開工到最后一臺機器停工的總時間)。研究一個實例：(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è)計對于給定的2臺處理機A和B處理n個作業(yè)，找出一個最優(yōu)調(diào)度方案，使2 臺機器處理完這n個作業(yè)的時間最短。算法分析當(dāng)完成k個作業(yè)，設(shè)機器A花費了x時間，機器B所花費時間的最小值肯定 是x的一個函數(shù)，設(shè)Fkx表示機器B所花費時間的最小值。則 Fkx=Min( Fk-1x+bk, Fk-1x-ak ；其中 Fk-1x+bk表示 第k個作業(yè)由機器B來處理(完成k-1個作業(yè)時機器A花費的時間仍是x)， Fk-1x-ak表示第k個作業(yè)由機器A處理(完成k-1個作業(yè)時機器A花費的 時間是x-ak)。那么單個點對較大值Max(x, Fkx)

6、，表示此時(即機器A花費x時間 的情況下)所需要的總時間。而機器A花費的時間x是變化的，即x=0,1,2 x(max)，由此構(gòu)成了點對較大值序列。要求整體時間最短，取這些點對較大值序 列中最小的即可。源代碼#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實驗三實驗題

10、目9汽車加油問題問題描述一輛汽車加滿油后可行駛nkm。旅途中有若干加油站。設(shè)計一個有效算法， 指出應(yīng)在那些加油站停靠加油，使沿途加油次數(shù)最少。并證明算法能產(chǎn)生一個最 優(yōu)解。算法設(shè)計對于給定的n和k個加油站位置，計算最少加油次數(shù)。算法分析將一輛汽車在出發(fā)地加滿油，每次加滿可行駛nkm，利用相鄰加油站之間距 離d是否可行駛的距離，并利用貪心算法計算最優(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;運行結(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請按任意鍵繼續(xù).實驗四實驗題目最短加法鏈問題問題描述最優(yōu)求幕問題：給定一個正整數(shù)n和一個實數(shù)x,如何用最少的乘法次數(shù) 計算出xn。例如，可以用6次乘法逐步計算x23如下：x,x2 , x3, x5, x10, x20, x23?？梢宰C明，計算x23的幕序列中各幕次組成正整數(shù)n的一個加法鏈: 1=a0 al a2 ar=na

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

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

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

21、5 0 2 E5.58C：MJseis fldininistiatDr時間復(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é)點.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旅行售貨員問題：分支限界法顯示: 使用了最小優(yōu)先級隊列： minPriority:頭文件： miqueue.h#ifndef _MINQUEUE_H#define _MINQUEUE_H #inc

26、ludetravel.h extern struct element queueN;/隊列的大小.extern int elementSize;void add_queue(struct element e);查看最小.int peel(struct element* first);刪除最小，如果說返回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é)點是否被訪問

27、.double cost; /當(dāng)前的花費.int visitedNumber;/當(dāng)前訪問的節(jié)點的數(shù)目，當(dāng)?shù)扔趎odeNumber的時候， 說明了訪問結(jié)束，同時cost加上它到其實節(jié)點的花費就可以得到總的花費.int lastNode; /最后被訪問的節(jié)點.;/最小花費.extern double minCost;兩個節(jié)點的花費.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;刪除最小，如果說返回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()(/最后一個值可能不滿足堆的性質(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