算法与程序设计上机报告

上机实验一一、实验题目用分治法进行归并分类算法介绍将A(1),......,A(n)均分成两个集合，在对每个集合单独分类，然后将已分类的两个序列归并成一个含n个元素的分好类的序列；merge（）函数负责把两个已分类集合归并在一起，mergesort（）函数通过使用递归和调用merge（）函数完成该处理过程三、程序流程图：说明：A[N]、B[N]是全程数组，A[]存放待分类的元素，B[]是辅助数组归并分类算法mergesort（递归算法）的具体扩展：说明：入口参数：待分类集合A(low:high)的头和尾元素位置low、highmerge函数的具体扩展：//使用辅助数组归并两个已分类的集合说明：入口参数：集合A(low:high)的头和尾元素位置low、high及该集合的分割点（二分）四、源程序及实验结果程序代码如下：#include<stdio.h>#include<math.h>#defineN1024intA[N],B[N];//A[N]、B[N]是全程数组，A[]存放待分类的元素，B[]是辅助数组voidmerge(intlow,intmid,inthigh)//使用辅助数组归并两个已分类的集合/*数组A（low：high）包含两个放在A(low:mid)和A(mid+1:high)中的已分类的子集合*此函数是使用一个辅助数组B（low：high）将这两个已分类的集合归并成一个集合，并存放到A（low：high）中*/{inth,k,i,j;h=low;i=low;j=mid+1;while(h<=mid&&j<=high)//当两个集合都没取尽时{if(A[h]<=A[j]){B[i]=A[h];h++;}else{B[i]=A[j];j++;}i++;}//处理剩余的元素if(h>mid)/*A(low:mid)数组取完时，将A(mid+1:high)中剩余元素依次复制到数组B(low：high)尾部*/{for(k=j;k<=high;k++){B[i]=A[k];i++;}}elsefor(k=h;k<=mid;k++)/*A(mid+1:high)数组取完时，将A(low:mid)中剩余元素依次复制到数组B(low：high)尾部*/{B[i]=A[k];i++;}for(k=low;k<=high;k++)//将已归并的集合复制到A中{A[k]=B[k];}}voidmergesort(intlow,inthigh)//归并分类/*将本集合二分为两个集合，再递归调用merge（）函数对每个集合单独分类并将已分类的*两个序列归并为一个分好类的序列*/{intmid;if(low<high){mid=(int)floor((low+high)/2);//求这个集合的分割点mergesort(low,mid);//将一个子集合分类mergesort(mid+1,high);//将另一个子集合分类merge(low,mid,high);//归并两个已分类的子集合}}voidmain(){inti=1,cx;//cx中存放待排序元素的个数printf("inputdata'snumber:");//显示提示信息scanf("%d",&cx);//输入待排序元素的个数printf("inputdatas:\n");for(i=1;i<=cx;i++)//输入待排序的各个元素的值，并存放到集合A中{scanf("%d",&A[i]);}mergesort(1,i-1);//调用归并分类算法对数组A（1：i-1）进行归并排序printf("outputdatas:\n");for(i=1;i<=cx;i++)//输出进行归并排序后的集合A{printf("%d,",A[i]);}getch();}运行结果如下图：(运行结果与理论结果一致)五、结果分析运行源程序后，先输入待排序元素的个数，回车。再分别输入打乱的元素的值序列，回车，显示按升序排列的元素值序列。最坏情况：输入数据按非增次序排列,每次内层while循环执行j次（j=2,3,…,n)。则有，Ω(n(n+1)/2-1)=Ω(n2);最好情况：输入数据已按非降序排列，不进入while循环，则最好情况下计算时间为Ω(n)。上机实验二一、实验题目用分治法进行快速分类二、算法介绍在集合A(1:n)中选一元素t=A[s]，然后将其它元素重新排列，使A(1:n)中所有在t以前出现的元素都小于或等于t，而在t后出现的元素都不小于t,元素t为划分元素，快速分类就是通过反复对产生的集合进行划分来实现的。三、程序流程图说明：A[1024]是全程数组，其中存放待分类的元素快速分类算法quicksort（递归算法）的具体扩展如下：说明：入口参数:集合A（p:q）的p、qpartition函数的具体扩展如下：说明：入口参数:集合A（m:q）的头m和尾后一个位置q出口参数：划分元素A[m]在集合A排序后的集合中的位置四、源程序及实验结果程序代码如下：#include<stdio.h>intA[1024];//A[1024]是全程数组，其中存放待分类的元素voidinterchange(inti,intj)//将A[i]与A[j]换位{intt;t=A[i];A[i]=A[j];A[j]=t;}intpartition(intm,intp)//用划分元素A[m]划分集合A(m:p-1),并返回划分元素定位后的位置//划分元素定位后其左边的元素不大于它，其右边的元素不小于它{inti,v;v=A[m];//记下划分元素的值i=m;//记下划分元素的起始位置while(1)//查找划分元素在排序后的集合中的位置{do//由左向右查找不小于划分元素的元素A[i]{i++;}while(A[i]<v);do//由右向左查找不大于划分元素的元素A[p]{p--;}while(A[p]>v);if(i<p)//若A[i]在A[p]的左边，则将它们换位；否则结束循环{interchange(i,p);}elsebreak;}A[m]=A[p];//划分元素最终定位在集合A中p处A[p]=v;returnp;}voidquicksort(intp,intq)//快速分类（本算法为递归算法）/*将全局数组A(1:n)中的元素A[p],.....,A[q]按递增的方式分类，认为A[n+1]已被定义，且不小于A(p:q)的所有元素，即A[n+1]为正无穷大（在主函数令正无穷大为1000）*/{intj;if(p<q){j=q+1;//此时j为划分元素的起始位置j=partition(p,j);//此时j存放的是划分元素应在排序后的集合中的位置//依次对由划分元素划分出的两个子集合进行快速分类quicksort(p,j-1);quicksort(j+1,q);}}voidmain(){inti,n;//n中存放待排序元素的个数printf("inputdata'snumber:");scanf("%d",&n);//输入待排序元素的个数printf("inputdatas:\n");for(i=1;i<=n;i++)//输入待排序的各个元素的值，并存放到集合A中scanf("%d",&A[i]);A[n+1]=1000;quicksort(1,n);//调用快速分类算法对数组A（1：n）进行归并排序for(i=1;i<=n;i++)//输出进行快速排序后的集合Aprintf("%d,",A[i]);getch();}运行结果如下图：(运行结果与理论结果一致)五、结果分析运行源程序后，先输入待排序元素的个数，回车。再分别输入元素的值序列，回车，就会显示按升序排列的元素值序列。不难看出，运行结果与理论结果一致。记最坏情况下的元素比较次数是Cw(n)；PARTITION一次调用中的元素比较数是p-m+1，故每级递归调用上，元素的比较次数等于该级所处理的待分类元素数。最坏情况下，每级递归调用的元素总数仅比上一级少1，故Cw(n)是r由n到2的累加和。即：Cw(n)=Ο(n2)上机实验三实验题目贪心算法求背包问题二、算法介绍1、将若干物品装入背包，装入情况有三种：部分装入、全部装入和未装入；2、量度标准：物品效益集合和容量集合分别按单位容量的效益增量的降序排列3、排序方法：快速排序三、程序流程图说明：存放物品的数目的变量n，数组A[1024]存放待分类元素，数组X[1024]存放解向量，数组W[1024]存放各物品的容量，数组P[1024]存放各物品的效益，以上变量均是全局变量。贪心算法greedy-knapsa的具体扩展如下：说明：入口参数:背包容量m四、源程序及实验结果程序代码如下：#include<stdio.h>intn;//n用于存放物品的数目floatA[1024];//数组A[]存放待分类元素（在本问题中是指物品的单位容量增量）floatX[1024];//数组X[]存放解向量，即各个物品在背包中的存放情况，0=<X[i]<=1intW[1024];//数组W[]存放各物品的容量intP[1024];//数组P[]存放各物品的效益voidinterchange(inti,intj)//交换两浮点数的位置{floatt;t=A[i];A[i]=A[j];A[j]=t;}voidinterchangeP(inti,intj)//交换两整型效益的位置{intt;t=P[i];P[i]=P[j];P[j]=t;}voidinterchangeW(inti,intj)//交换两整型容量的位置{intt;t=W[i];W[i]=W[j];W[j]=t;}intpartition(intm,intp)//用划分元素A[m]划分集合A(m:p-1),并返回划分元素定位后的位置{inti;floatv;v=A[m];i=m;while(1){do{i++;}while(A[i]>v);do{p--;}while(A[p]<v);if(i<p){interchange(i,p);//将A[i]与A[j]换位interchangeP(i,p);//将P[i]与P[j]换位interchangeW(i,p);//将W[i]与W[j]换位}elsebreak;}A[m]=A[p];A[p]=v;interchangeP(m,p);interchangeW(m,p);returnp;}voidquicksort(intp,intq)//快速分类（本算法为递归算法）//将全局数组A(1:n)中的元素A[p],.....,A[q]按递减的方式分类{intj;if(p<q){j=q+1;j=partition(p,j);quicksort(p,j-1);quicksort(j+1,q);}}voidgreedy_knapsa(intm)//背包问题的贪心算法/*P(1:n)和W(1:n)分别含有按P[i]/W[i]>=P[i+1]/W[i+1]排序的n件物品的效益值和容量。X(1:n)是解向量，m存放背包的容量，物品存放入背包有三种情况：未放、部分放入和全部放入*/{intcu,i;//cu用于存放背包的剩余容量for(i=1;i<=n;i++)//将解向量初始化为0X[n]=0;cu=m;for(i=1;i<=n;i++)//存放物品{if(W[i]>cu)break;X[i]=1;cu-=W[i];}if(i<=n)X[i]=(float)cu/W[i];}voidmain(){inti,M;printf("inputn:");scanf("%d",&n);//输入物品数目printf("inputM:");scanf("%d",&M);//输入背包容量printf("inputP:");for(i=1;i<=n;i++)//输入各物品的效益值scanf("%d",&P[i]);printf("inputW:");for(i=1;i<=n;i++)//输入各物品的容量scanf("%d",&W[i]);for(i=1;i<=n;i++)//A[i]存放第i个物品的单位容量的效益增量A[i]=(float)P[i]/W[i];quicksort(1,n);//将效益集合和容量集合按物品单位容量的效益增量降序进行排序greedy_knapsa(M);//执行贪心算法求出解向量printf("output:");for(i=1;i<=n;i++)//输出解向量printf("%f,",X[i]);printf("\n");}运行结果如下图所示：(运行结果与理论结果一致)五、结果分析运行源程序后，先输入物品的数量，回车，再输入背包的容量，回车，然后依次输入各物品的效益值，回车，最后对应输入各物品的容量，回车，就会得到解向量（各物品存放情况，此时物品的顺序不一定与初始时一样）。不难看出，运行结果与理论值一致。将物体事先按Pi/Wi的非增次序分好类，若物品分类的时间不算在内，则此算法所用时间为O（n）。上机实验四一、实验题目贪心方法求带有限期的作业排序二、算法介绍度量标准的选择以目标函数作为量度。量度标准：下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下得到最大增加的作业。处理规则：按pi的非增次序来考虑这些作业。三、程序流程图四、源程序及实验结果#include<stdio.h>#defineN8typedefstruct{ intp; intd;}job;jobj1[N]={{0,0},{35,4},{30,2},{25,4},{20,3},{15,4},{10,8},{5,3}};voidback(job*ps,intm,intn){ inti; for(i=n;i>=m;i--) { ps[i+1].p=ps[i].p; ps[i+1].d=ps[i].d; }}voidmain(){ intt,t1,i,m;//t为所用时间,t1为预计时间 jobj[N];printf("输出待处理的作业：效益值,截止期限"); printf("\n"); for(i=1;i<N;i++) { printf("\t\t%8d,\t%d",j1[i].p,j1[i].d); printf("\n"); } //初始化 j[0].p=j1[0].p; j[0].d=j1[0].d;j[1].p=j1[1].p; j[1].d=j1[1].d; t=1; for(i=2;i<N;i++) { t1=t+1; if(j1[i].d>=t1||j[i-1].d>=t1) { m=1; while(m<=t) { if(j1[i].d<j[m].d) { back(j,m,t); j[m].p=j1[i].p; j[m].d=j1[i].d; break; }elsem++; } if(m>t) { j[t1].p=j1[i].p; j[t1].d=j1[i].d; } t=t1; }elset1--; } printf("输出得到的结果：效益值,截止期限"); printf("\n"); for(i=1;i<=t;i++) { printf("\t\t%d,\t%d",j[i].p,j[i].d); printf("\n"); }}运行结果如下图所示：(运行结果与理论结果一致)五、结果分析将待作业的信息直接放入程序中，并显示。运行源程序后，直接得到可行解的效益值与截止期限。不难看出，运行结果与理论值一致。设s是最终计入J中的作业数，则算法JS所需要的总时间是O(sn)。s≤n，故最坏情况：TJS=О(n2)，特例情况：pi=di=n-i+1,1≤i≤n；最好情况：TJS=О(n)，特例情况：di=i,1≤i≤n。上机实验五一、实验题目贪心方法求单源点的最短路径问题二、算法介绍限定有向图中所有的权都是正的；逐条构造所求最短路径，量度标准是使用迄今已生成的所有路径长度之和，单独的每一条路径都必须具有最小长度，按照路径长度的非降次序生成从源点（起始结点）到所有其它结点的最短路径。三、程序流程图说明：集合S表示对其已经生成了最短路径的那些结点（包括起始结点V0）的集合；cost[][]（是全局变量）中存放各结点之间的直接距离并规定无穷大为1024，表示两结点之间不可直达，cost[i][i]表示结点Vi与Vi的距离，规定其值为0。四、源程序及实验结果程序代码如下：#include<stdio.h>#include<string.h>/*二维数组cost[6][6]存放的是一个有向图中各个结点的直接距离，其中从i到j不能直接到达时它们的距离为无穷大，用1024表示*/intcost[6][6]={{0,50,10,1024,45,1024},{1024,0,15,1024,10,1024},{20,1024,0,15,1024,1024},{1024,20,1024,0,35,1024},{1024,1024,1024,30,0,1024},{1024,1024,1024,3,1024,0}};intmin(inta,intb)//求a与b的最小值并返回该值{if(a>b)a=b;returna;}voidshortest_paths(intv){intu,num,i,w,tmin;intdist[6];//数组dist[i]中存放的是起始节点v与结点Vi的路径长度intS[6];//S[i]是结点Vi加入集合S的情况，不在S中时为0，在时为1intn=6;for(i=0;i<n;i++)//为集合S和dist赋初值{S[i]=0;dist[i]=cost[v][i];}printf("输出v到所有结点的直接距离：\n");for(i=0;i<n;i++)//打印v到所有结点的路径长度{printf("%d,",dist[i]);}S[v]=1;//将起始结点v加入集合S中dist[v]=0;//结点v到v的路径长度为0for(num=1;num<=n-1;num++)//确定由结点v出发的n-1条路{i=0;while(S[i]==1)//找到一个不在集合S中的结点{i++;}tmin=i;//tmin存放的是dist[i]值最小的结点下标i,默认初值为前面找到的不在集合S中的结点的下标for(i=0;i<n;i++)//搜索不在集合S中且dist[i]值最小的结点Vi{if(S[i]==1)continue;elseif(dist[i]<dist[tmin])tmin=i;}u=tmin;//将不在集合S中且dist[i]值最小的结点的下标记入u中S[u]=1;//将结点Vtmin记入集合S中for(w=0;w<n;w++)//修改v到所有未加入集合S中的结点的路径长度{if(S[w]==0)dist[w]=min(dist[w],dist[u]+cost[u][w]);}}printf("\n输出所有结点加入集合S[]的情况:\n");for(i=0;i<n;i++){printf("%d",S[i]);}printf("\n分别输出v与各结点的最短路径长度:\n");for(i=0;i<n;i++){printf("%d,",dist[i]);}printf("\n");}voidmain(){intv;charc;do{c=getchar();//输入起始结点的下标值v=c-'0';if(v>=0&&v<6)//当所输下标合法时求从该结点到所有结点（包括该结点）的路径长度{shortest_paths(v);c=getchar();}elsebreak;//当所输下标不合法时结束}while(c=='\n');}运行结果如下：(运行结果与理论结果一致)五、结果分析运行源程序后，输入起始结点v的下标，回车，就会输出v到所有结点的直接距离，以及各结点加入集合S的情况，和v到各结点的最短路径长度。不难看出，运行结果与理论值一致。由于任何一条边都有可能是最短路径中的边，所以求任何最短路径的算法都必须至少检查图中的每条边一次，所以这样的算法的最小时间是О(e)。上机实验六一、实验题目动态规划求有向图最短路径二、算法介绍考察i到j的最短路径：首先确定哪个节点是该路径上具有最大编号的中间结点k，计算由i、j分别到k的最短路径，这2条路径都不可能有比k-1还大的中间节点。求解递推；用Ak（i，j）表示从i到j且不经过比k还大的结点的最短路径长度，由于G中不存在比n还大的结点，因此A（i，j）=An（i，j），即由i到j的最短路径上不通过比n标号还大的结点。这条路径可能通过结点n也可能不通过节点n，如果通过结点n则An（i，j）=An-1（i，n）+An-1（n，j），如果不通过结点n，则An（i，j）=An-1（i，j）。组合起来得到An（i，j）=min{An-1（i，j），An-1（i，n）+An-1（n，j）}同理Ak（i，j）=min{Ak-1（i，j），Ak-1（i，k）+Ak-1（k，j）}，k》1.简单的描述最短路径算法如下：=1\*ROMANI从某一点k开始，根据cost[n][n]（比较A(i,j)与A(i,k)+A(k,j)的大小）修改从i到j的最短路径值，若A(i,k)+A(k,j)<A(i,j)，A(i,j)=A(i,k)+A(k,j).=2\*ROMANII.重复1直到所有点均考虑完。三、程序流程图四、源程序及实验结果#include<stdio.h>#defineN10#defineINIFITY1000struct{ intvexnum;//结点个数 intarcs[N][N];//邻接矩阵}G;//图voidoutput(inta[N][N]){ inti,j;//循环参数 for(i=1;i<G.vexnum+1;++i) { for(j=1;j<G.vexnum+1;++j) { if(a[i][j]>900) { printf("+~~\t");//输出无穷大标记 } else { printf("%d\t",a[i][j]);//依次输出邻接矩阵 } } printf("\n"); } printf("\n-------------------------------------------------------\n");}voidinitialize(){ FILE*fp;//文件指针 inti,j;//循环参数 fp=fopen("数据.txt",