JL21505110-计算机32(算法设计与分析).doc

算法设计与分析实验报告 班级：计算机32班 姓名：杨红 学号：JL21505109 日期：2015年12月20日一.动态规划实验报告一、实验要求利用动态规划方法设计汽车加油行驶问题算法，掌握动态规划法的基本思想和算法设计的基本步骤。要求：设计加油问题的动态规划算法，要求输出最优行驶路线所需的费用，即最小费用中,第1行中的数是最小费用值。利用c语言（c+语言）实现算法，给出程序的正确运行结果。2、 实验题目 给定一个N*N 的方形网格，设其左上角为起点，坐标为（1，1），X轴向右为正，Y轴向下为正，每个方格边长为1。一辆汽车从起点出发驶向右下角终点，其坐标为（N，N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：（1）汽车只能沿网格边行驶，装满油后能行驶K条网格边。出发时汽车已装满油，在起点与终点处不设油库。（2）当汽车行驶经过一条网格边时，若其X坐标或Y坐标减小，则应付费用B，否则免付费用。（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。（4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。（5）(1)(4)中的各数N、K、A、B、C均为正整数。求汽车从起点出发到达终点的一条所付费用最少的行驶路线。 3、 源码#include stdafx.h#include#includeint N,K,A,B,C;int noDrived=100000; /表示该点汽车还未行驶过int Drive10010012;int Map100100; /记录网格点是否设有加油站int Towards43=-1,0,0,0,-1,0,1,0,0,0,1,0;/表示汽车在（x,y）点的前一时刻位置相对于(x,y)的可能方向void readFile(char* fileName)/读取文件并初始化各数值FILE *fp;fp=fopen(fileName,r); fscanf(fp,%d %d %d %d %d,&N,&K,&A,&B,&C);Towards22=B; Towards32=B;int i,j;for(i=0;iN;i+)for(j=0;jN;j+)/初始化网格点的信息fscanf(fp,%d,&Mapij); for( i=0;iN;i+)for(j=0;jN;j+)for(int p=0;p=K+1;p+) /p表示汽车行驶到网格点(i,j)时剩余的油量/初始化网格点，表示汽车尚未行驶过Driveijp=noDrived;fclose(fp);void drive_Car(int n,int aa,int c,int k)int i,j,p,q,r,min; /(x,y,g)=(i+1,j+1,p):g表示行驶至(x,y)处剩余的油量for(i=0;i0)/递归取最小费用r=0;for(i=0;in;i+)for(j=0;jn;j+)if(i!=0|j!=0) /排除(1,1)点的特殊情况for(p=0;p=k;p+) /p表示剩余的油量min=noDrived;for(q=0;q4;q+) /在网格有4种边界，各有不同的限定走法,防止穿越边界if(i=0&q=0) continue;if(j=0&q=1) continue;if(i=N-1&q=2) continue;if(j=N-1&q=3) continue;if(Drivei+Towardsq0j+Towardsq1p+1+Towardsq2min+Mapij*aa)r+;Driveijp=min;if(Mapij=1)/有加油站，且加满油Driveijp+=aa;for(q=1;q=k;q+)Driveijq=Driveijp;break; else if(Driveijp=noDrived)/网点没有加油站，汽车需要加油Driveijp=Driveij0+c+aa;for(q=p+1;q=k;q+)Driveijq=Driveijp;break; void writeFile(char *fileName)FILE *fp;fp=fopen(fileName,w); fprintf(fp,%d,DriveN-1N-10);fclose(fp);int main() readFile(input.txt); drive_Car(N,A,C,K); writeFile(output.txt); return 0;4、 运行结果输入实例：结果显示： 5、 心得体会 在本次实验中，使自己对解决一个动态规划问题有了进一步的认识。即当算法考虑的原问题的每一个子问题，算法都需要计算一个最优解。换句话说，所有算法生成的表项表示算法考虑的子问题的最优解。这时候用动态规范把每一个最优解求出来（利用递归公式），就能够保证最后求得的一定是最优解。二.贪心算法实验报告一、实验要求利用贪心算法设计最有合并问题算法，掌握贪心算法的基本思想和算法设计的基本步骤。要求：设计最优合并问题的贪心算法算法，要求将编程计算出的最多比较次数和最少比较次数输出到文件output.txt。给出程序的正确运行结果。二、实验题目题目描述：给定k 个排好序的序列s1,s2,.,sk用2 路合并算法将这k 个序列合并成一个序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。 三源码 #include stdafx.h#include#include#includeint getMin(int,int);/找最小int getMax(int,int);/找最大void quick_sort(int *,int,int);/将读入的数值进行排序int main() int data100,n,i,min,max; FILE *fp,*fp2; if(fp=fopen(input.txt,r)=NULL) printf(FILE OPEN ERROR!n); getch( ); exit(1); Else fscanf(fp,%d,&n); for(i=1;i=n;i+) fscanf(fp,%d,&datai); fclose(fp); quick_sort(data,1,n); min = getMin(data,n); max = getMax(data,n); if(fp2=fopen(output.txt,wt)=NULL) printf(Cant file the output.txt!n); getch(); exit(1); else fprintf(fp2,%d %d,max,min); fclose(fp2); system(pause); return 0;int getMin(int data100,int n) int i,amount,sum; int dataM200,markQ,markH,curp; /对新建立的markData数组进行初始化 for(i=1;i=n;i+) dataMi = datai; for(i=n+1;i200;i+) dataMi = -1;/-1表示未存数 if(n=1) return data1; else dataMn+1 = dataM1+dataM2; sum = dataM1+dataM2-1; markQ = 3; markH = n+1; curp = n+1; for(i=3;in)/当前标准已经知道n之后则取后标志初的两位 sum = sum+dataMmarkH+dataMmarkH+1-1; dataM+curp = dataMmarkH+dataMmarkH+1; markH+=2; else if(markQ=n)/当前标准位已经到n if(dataMndataMmarkH+1|i=n)/选择前标志位和后标志 sum = sum+dataMmarkH+dataMn-1; dataM+curp = dataMmarkH+dataMn; markH+; markQ+; else/均选择后标志位 sum = sum+dataMmarkH+dataMmarkH+1-1; dataM+curp = dataMmarkH+dataMmarkH+1; markH = markH + 2; else if(dataMmarkQ+1后 sum = sum+dataMmarkQ+dataMmarkQ+1-1; dataM+curp = dataMmarkQ+dataMmarkQ+1; markQ+=2; else if(dataMmarkH+1=-1|dataMmarkQ=dataMmarkH) /后只有一个值后者或前小于后+1且前大于后时，选择一前一后 sum = sum+dataMmarkQ+dataMmarkH-1; dataM+curp = dataMmarkQ+dataMmarkH; markQ+; markH+; else if(dataMmarkQ=dataMmarkH&dataMmarkH后并且前=1;i-) sum += amount+datai-1; amount +=datai; return sum;void quick_sort(int *num,int begin,int end) int i,j,temp; if(beginend) i=begin; j=end; temp=numbegin; while(ij while(itemp) j-; if(ij) numi=numj; i+; /向前移位 while(ij&numitemp) i+; if(ij) numj=numi; j-; /向后移位 numi=temp; /基准点赋值 quick_sort(num,begin,i-1); /从基准点的左右位置分别递归开始排序 quick_sort(num,i+1,end); 四、 运行结果 输入input.txt记事本实例：输出input.txt记事本实例： 五、 心得体会在本次实验中，使自己对解决一个贪心算法的问题有了进一步的认识。在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。同时，对于自己的逻辑思维更系统化。即考虑问题要全面，虽然有时候会将问题复杂化但是至少思考过程能学到很多东西，这样会使逻辑越来越严谨。三.分支限界算法实验报告一、 实验要求用分支限界法实现最小重量机器设计问题，掌握分支限界算法的基本思想和算法设计的基本步骤。要求：对于给定的机器部件重量和机器部件价格，设计一个优先级队列分支限界法，计算总价值不超过d的最小重量机器设计。二、 实验题目设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。设计一个优先级队列分支限界法，给出总价格不超过d的最小重量机器设计。三、 实验源代码#include#includeusingnamespacestd;intn,m,d;intMinWeight;intMinValue;int*c=NULL;int*w=NULL;structNodeintweight;intval;intsource; /哪个供货商intlevel; /第几层Node*father;/优化的优先级设定booloperator(Nodea,Nodeb) /level按照减序if(a.weight=b.weight)returna.levelb.weight;Node*MinLeaf;voidMinWeightMachine()inti,j;MinValue=INT_MAX;MinWeight=INT_MAX;Nodeintital;intital.father=NULL;intital.level=0;intital.source=0;intital.val=0;intital.weight=0;priority_queueheap;/用优先队列，建立一个最小堆。加入进去就会自动排好序的。heap.push(intital);while(!heap.empty()Node*fartherNode=newNode(heap.top();heap.pop();if(fartherNode-level=n)/最开始给MinWeight 赋一个较大的值if(fartherNode-weightweight;MinValue=fartherNode-val;MinLeaf=fartherNode; /记录是最后是哪个结点数据elseintmin_w=INT_MAX,min_c=INT_MAX;/min_w分别代表当前的质量加上剩余的最小质量的和，min_c代表当前价值加上剩余的最小价值的和min_c=fartherNode-val;min_w=fartherNode-weight;for(i=fartherNode-level+1;i=n ;i+)/选出剩余的部件在售货商中购买的最小质量,就是选择每一层最小的质量 inttemp_min_w=INT_MAX,temp_min_c=INT_MAX;for(j=1;j=m;j+) /,temp_min记录当前这一层的最小的质量temp_min_w=temp_min_wwij?temp_min_w:wij;temp_min_c=temp_min_ccij?temp_min_c:cij;min_w+=temp_min_w;min_c+=temp_min_c;if(min_wMinWeight|min_cd)continue;for(i=1;ival+cfartherNode-level+1iweight+wfartherNode-level+1ilevel=fartherNode-level+1;newNode-father=fartherNode;newNode-source=i;newNode-val=fartherNode-val+cnewNode-leveli;newNode-weight=fartherNode-weight+wnewNode-leveli;heap.push(*newNode);intmain()inti,j;cout请分别输入，部件个数，供应商个数，及最大的总价格：nmd;w=newint*n+1;c=newint*n+1;for(i=1;i=n ;i+)wi=newintm+1;ci=newintm+1;MinLeaf=NULL;cout请依次输入各个部件在各个供应商处购买的价格:endl;for(i=1;i=n ;i+)for(j=1;jcij;cout请依次输入各个部件在各个供应商处购买的重量:endl;for(i=1;i=n;i+)for(j=1;jwij;MinWeightMachine();cout最小质量为:MinWeight=1;i-)resulti=MinLeaf-source;MinLeaf=MinLeaf-father;cout各个部件的来源分别为:endl;for(i=1;i=n;i+)coutresulti ;coutendl；四、 运行结果输入-输出实例：五、 实验心得通过本次实验，加深了对分支限界算法思想的理解，并把理论学到的知识用实际的程序来表示出来，解决实际的问题。学以致用，增加了自己的学习乐趣，还锻炼了自己的实际编程能力。四.随机化算法实验报告一、 实验要求利用随机化算法实现皇后控制问题，理解随机化算法的基本思想并利用程序设计加以实现。要求：设计一个拉斯维加斯算法，对于给定的自然数n（1=n=100）计算在n*n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格，且放置的皇后互不攻击。二、 实验题目在n*n个方格组成的棋盘上的任一方格中放置一个皇后，该皇后可以控制其所在的行、列及对角线上的所有方格。对于给定的自然数，在n*n个方格组成的棋盘上最少要放置多少个皇后才能控制整个棋盘，且放置的皇后互不攻击。三、 实验源代码#include using namespace std; class Queen friend bool nQueen(int); private: bool Place(int k); /测试皇后K置于xk列的合法性 bool Backtrack(int t); /解n后问题的回溯法 bool QueenLV(int stopVegas); /随机放置n个皇后的拉斯维加斯算法 int n,*x,*y; ; bool Queen:Place(int k) for(int j=1;jn)/存放皇后放置的位置 for(int i=1;i=n;i+) yi=xi; return true; else for(int i=1;i=n;i+) xt=i;/t皇后放在第i列 if(Place(t)&Backtrack(t+1) return true; return false; bool Queen:QueenLV(int stopVegas) /随机放置n个皇后的拉斯维加斯算法 int k=1;/随机数产生器 int count=1; /1=stopVagas=n表示允许随机放置的皇后数 while(k0) count=0; for(int i=1;i0) /如果能放置，则在这么多个能放置第k个皇后的位置中选择一个位置 xk+=yrand()%count; return(count0);/count0表示放置成功 bool nQueen(int n) /与回溯法相结合的接n后问题的拉斯维加斯算法 Queen X; X.n=n; int *p=new intn+1; int *q=new intn+1; for(int i=0;i15) stop=n-15; bool found=false; while(!X.QueenLV(stop);/直到能放置 /算法的回溯搜索部分 if(X.Backtrack(stop+1) for(int i=1;i=n;i+) coutpi ; found=true; coutendl; delete p; delete q; return found; int main() int n; coutn; if(!nQueen(n) cout无解endl; return 0; 四、 实验结果输入文件示例：输出文件示例：五、 实验心得通过本次的实验，实践中实现了拉斯维加斯算法实现的N皇后问题，通过一个STOP 的数据设置，这个算法比纯粹的拉斯维加斯算法更加现实，比回溯法更加理想，体会到了随机化算法的实际应用。五.线性规划问题的单纯形法实现实验报告一、 实验要求通过这一次的线性方程的求解实验，理解单纯形法的算法思想，学会算法的基本步骤，并实现一组线性方程组的求解。二、 实验题目利用单纯形法解下列方程组：Z=12X1+8X2+5X33X1+2X2+X3=2012X1+4X2+X3=48X1+X2+X3=0三、 实验源代码#include stdafx.h#include #include using namespace std;#define M 10000 /全局变量大M float juzhen1131;/核心矩阵表 int m=0,n=0,t=0;/m:结构向量的个数 /n:约束不等式个数 /t:目标函数类型：1代表求求最小值，1代表求最大值 void input() /输入接口函数 int i,j; cout单纯形法的参 数 输 入m; coutendln; for (i=0;i=n+1;i+) for (j=0;j=m+n+n;j+) juzhen ij=0; /初始化矩阵，所有元素均为0 /读入约束条件 coutendl=）:endlendl cin= for= i=1;i=m;i+) j=1;jjuzhen ij; for (i=1;i=n;i+) juzhen i0=juzhen im+2; juzhen im+2=0; /读入目标条件 coutendlendl := cin= for= i=1;ijuzhen 0i; cint; /矩阵调整 if(t=-1) for(i=1;i=m;i+) juzhen 0i=(-1)*juzhen 0i; for(i=1;i=n;i+) juzhen im+i=juzhen im+1; if(i!=1) juzhen im+1=0; /算法函数 void comput() int i,j,flag,temp1,temp2,h,k=0,temp310; float a,b11,temp,temp411,temp511,f=0,aa,d,c; /初始化 for(i=1;i=n;i+) temp3i=0; for(i=0;i11;i+) temp4i=0; temp5i=0; for(i=1;i=n;i+) if(juzhen im+i=-1) juzhen im+n+i=1; juzhen 0m+n+i=M; temp3i=m+n+i; else temp3i=m+i; for(i=1;i=n;i+) temp4i=juzhen 0temp3i; /循环求解 do for(i=1;i=m+n+n;i+) a=0; for(j=1;j=n;j+) a+=juzhen ji*temp4j; juzhen n+1i=juzhen 0i-a; for(i=1;i=0) flag=1; else flag=-1; break; if(flag=1) for(i=1;i=n;i+) if(temp3i=m+n) temp1=1; else temp1=-1; break; /输出结果 coutendlendl; aa=juzhen c=100000; code= d=juzhen else=f=fendlendl; flag=-1) h=i; i=k) int= j=0;j/endl/endlendl/endlendl/endl/endl四、 实验结果五、 实验心得通过本次实验，将学到的单纯形法掌握的更加熟练，将手工计算用计算机实现，体现出了我们学习编程的价值与目标。加深了对编程学习的乐趣，还有算法的巧妙性，为将来研究算法打下了一定的基础。六.回溯法实验报告一、 实验要求通过实验，理解回溯法的基本思想并学会回溯法的基本编程。要求：对于给定的罗密欧与朱丽叶的迷宫，计算罗密欧通向朱丽叶的所有最少转弯道路。二、 实验题目罗密欧与朱丽叶身处一个m*n的迷宫中。每一个方格表示迷宫中的一个房间。这m*n个房间有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿着8个方向进入未封闭的房间。罗密欧位于迷宫的（p，q）方格中，他必须找出一条朱丽叶所在的（r，s）方格的路。在抵达朱丽叶房间之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数最少。每改变一次前进方向算做转弯一次。请设计一个算法帮助罗密欧找出这样的一条道路。DDDDD为阻塞的房间。三、 实验源代码#include#includeusing namespace std;const int MAX = 10;int n, m, k;int boardMAXMAX;int bestMAXMAX;int dirs = 0; /转弯次数int min = 100000; /最少转弯次数int count = 0; /不同的最少转弯道路数struct Point int x, y; ;Point luo;Point ye;int dx8 = 1, 0, -1, 0, 1, 1, -1, -1; /八个