算法分析与设计实验报告

1、计算机算法设计与分析实验报告目录 TOC o 1-5 h z 实验一1实验题目1问题描述1算法设计1算法分析1源代码1运行结果2实验二2实验题目2问题描述2算法设计2算法分析2源代码2运行结果4实验三5实验题目5问题描述5算法设计5算法分析5源代码5运行结果6实验一实验题目7集合划分问题问题描述n个元素的集合1, 2,，n可以划分为若干非空子集。例如，当n=4时， 集合1，2, 3, 4可以划分为15个不同的非空子集。算法设计给定正整数n，计算出n个元素的集合1，2，n可以划分为多少个不同 的非空子集。算法分析本算法实现采用分治法思想，F(n,m)=F(n-1,m-1)+m*F(n-1,m)。

2、假设将m个 元素分解到n个集合中，首先考虑将(m - (n - 1)个元素分到第一个集 合中，将余下的(n - 1)个元素分别分配到余下的(n - 1)个集合中，然后再 考虑将(m - (n - 2)个元素分配到第一个集合中，将余下的(n - 2)个 元素分别分配到余下的(n - 1)集合中，依此类推，直到后面的有一个集合中 的元素个数比第一个集合中的元素个数多为止。源代码#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;运行结果I D:PQgran-i Files (xB6)DEV-C3Pworkspacesuanfiplease input a number t

4、he p-esziile is： 52请按任意键继成-实验二实验题目1独立任务最优调度问题问题描述用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时 间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关 系，很可能对于某些i,有aiNbi，而对于某些j,j尹i,有aj bj。既不能将 一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个 动态规划算法，使得这2台机器处理完这n个作业的时间最短(从任何一台机器 开工到最后一台机器停工的总时间)。研究一个实例：(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)。算法设计对于给定的2台处理机A和B处理n个作业，找出一个最优调度方案，使2 台机器处理完这n个作业的时间最短。算法分析当完成k个作业，设机器A花费了x时间，机器B所花费时间的最小值肯定 是x的一个函数，设Fkx表示机器B所花费时间的最小值。则 Fkx=Min( Fk-1x+bk, Fk-1x-ak ；其中 Fk-1x+bk表示 第k个作业由机器B来处理(完成k-1个作业时机器A花费的时间仍是x)， Fk-1x-ak表示第k个作业由机器A处理(完成k-1个作业时机器A花费的 时间是x-ak)。那么单个点对较大值Max(x, Fkx)

6、，表示此时(即机器A花费x时间 的情况下)所需要的总时间。而机器A花费的时间x是变化的，即x=0,1,2 x(max)，由此构成了点对较大值序列。要求整体时间最短，取这些点对较大值序 列中最小的即可。源代码#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。旅途中有若干加油站。设计一个有效算法， 指出应在那些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最 优解。算法设计对于给定的n和k个加油站位置，计算最少加油次数。算法分析将一辆汽车在出发地加满油，每次加满可行驶nkm，利用相邻加油站之间距 离d是否可行驶的距离，并利用贪心算法计算最优解。源代码#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;运行结果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请按任意键继续.实验四实验题目最短加法链问题问题描述最优求幕问题：给定一个正整数n和一个实数x,如何用最少的乘法次数 计算出xn。例如，可以用6次乘法逐步计算x23如下：x,x2 , x3, x5, x10, x20, x23。可以证明，计算x23的幕序列中各幕次组成正整数n的一个加法链: 1=a0 al a2 ar=na

13、r= aj+ ak,k=jI,i=1,2,，r上述最优求幕问题相应于正整数n的最短加法链问题，即求n的一个加法 链使其长度r达到最小。正整数n的最短加法链长度记为l(n)。数据输入：由文件input.txt给出输入数据。第1行有1个正整数n。结果输出：将计算的最短加法链长度l(n)和相应的最短加法链输出到文件 output.txt。算法设计对于给定的正整数n,计算相应于正整数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);输出数据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、旅费）。他要选择一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。算法设计对于给定的邻接矩阵图，计算花费最少的周游路。算法分析数据输入：由input.txt文件提供输入，第一行n表示城市数目，之后为n行n列表示城市的邻接矩阵，-1表示两个城市直接没有路。数据输出：将最小花费输出到output.txt。本算法采用最小值堆来实现优先队列。其优先级是节点当前费用。堆的数据结 构不再赘述。对排列数的解空间进行广度优先遍历，每次将活结点入堆，从堆顶取出结点并展开，记录最小花费，当堆中元素为空时输出结果到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*/运行结果如下：亍售的可题 7H 5i aE 35 4E 17

21、5 0 2 E5.58C：MJseis fldininistiatDr时间复杂度：O(n3),空间复杂度是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);/添加该节点.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旅行售货员问题：分支限界法显示: 使用了最小优先级队列： 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,标明peek为空. int peek(struct element* first);#endifDiver.h:#ifndef _H_TRAVEL#define _H_TRAVEL#define N 1000struct element(int visitedN; /当前节点是否被访问

27、.double cost; /当前的花费.int visitedNumber;/当前访问的节点的数目，当等于nodeNumber的时候， 说明了访问结束，同时cost加上它到其实节点的花费就可以得到总的花费.int lastNode; /最后被访问的节点.;/最小花费.extern double minCost;两个节点的花费.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,标明peek为空.int peek(struct element* first)(if(elementSize = 0)(re

29、turn 0;elementSize-;*first = queue0;queue0 = queueelementSize;keepQueueInDown(0);return 1;void keepQueueInUp()(/最后一个值可能不满足堆的性质.int tempIndex = elementSize -1;while(tempIndex != 0)(/满足堆性质.if(cmpElement(queue + (tempIndex - 1)/2, queue + tempIndex) =0.0) break;/进行交换.struct element temp = queuetempInde

30、x;queuetempIndex = queue(tempIndex-1)/2;queue(tempIndex-1)/2 = temp;/继续向上.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