2019-06-21 50页 doc 91KB 49阅读
is_447713
暂无简介
mid then for k←j to high do //处理剩余的元素// B(i) ←A(k);i←i+1 repeat else for k←h to mid do B(i) ←A(k);i←i+1 repeat endif 将已归并的集合复制到A end MERGE 2. 快速排序算法 QuickSort(p,q) //将数组A[1:n]中的元素 A[p], A[p+1], , A[q]按不降次序排列, 并假定A[n+1]是一个确定的、且大于 A[1:n]中所有的数。// int p,q; global n, A[1:n]; if p#include#include #include #define M 11 typedef int KeyType; typedef int ElemType; struct rec{ KeyType key; ElemType data; }; typedef rec sqlist[M]; class guibing{ public: guibing(sqlist b) { for(int i=0;i b[j].key) k=j; if(k!=i) { rec temp=b[k]; b[k]=b[i]; b[i]=temp; } } } void merge(int l,int m,int h,sqlist r2) { xuanze(r,l,m); xuanze(r,m,h); output(r,M); int i,j,k; k=i=l; for(j=m;i #include #include #include #define MAXI 10 typedef int KeyType; typedef int ElemType; struct rec{ KeyType key; ElemType data; }; typedef rec sqlist[MAXI]; class kuaisu { public: kuaisu(sqlist a,int m):n(m) { for(int i=0;i =p.key)j--; b[i]=b[j]; while(i 的成本。 P(1:k)是最小成本路径。// real COST(n),integerD(n一1),P(k),r,j,k,n COST(n)← 0 for j←n-1to 1by-1do //计算COST(j)// 设r是一个这样的结点,(j,r)E且使c(j,r)+COST(r)取最小值 COST(j)←c(j,r)+COST(r) D(j)←r repeat //向前对j-1进行决策// P(1)←1;P(k)←n; for j←2 to k-1 do //找路径上的第j个节点// P(j)←D ( P(j-1) ) repeat end FGRAPH 四.程序代码 多段图问题 #include #include #include #define MAX_VERTEX_NUM 50 typedef struct ArcNode { int adjvex; //该弧所指向的顶点的位置 int value; //该结点与邻接结点间的代价 struct ArcNode *nextarc; //指向下一条弧的指针 }ArcNode, *node; typedef struct VNode { int data; //顶点信息 ArcNode *firstArc; //指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct Graph { AdjList vertices; int vexnum,arcnum; //图的当前顶点数和弧数 }*ALGraph; int build_adList(ALGraph G,int n,int a) { //建立邻接表 int v, m, i, t, h; node p, q; if(n < 0) return printf("ERROR"); G->vexnum = n; //图的顶点数 if(a < 0) return printf("ERROR"); G->arcnum = a; //图的弧数 for(m = 0; m < n; m++) { G->vertices[m].data = m; G->vertices[m].firstArc = NULL; } for(m = 1; m <= a; m++) { i = 1; printf("输入第%d条弧:", m); scanf("%d,%d,%d",&t,&h,&v); p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = h; p->value = v; p->nextarc = NULL; while(G->vertices[i].data != t) i++; //转到下一个结点 if(!G->vertices[i].firstArc) //终点 G->vertices[i].firstArc = p; else { //若当前结点有后继节点则后移 for(q = G->vertices[i].firstArc; q->nextarc; q = q->nextarc); q->nextarc = p; //新开辟结点 } } return v; } void print_Graph(ALGraph G) { //打印邻接表 ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode)); int i; for(i = 1; i < G->vexnum; i++) { p = G->vertices[i].firstArc; printf("[%d]",i); while(p) { printf("->%d,%d",p->adjvex,p->value);//第i个结点的邻接结点信息 p = p->nextarc; } printf("\n"); } } void fgraph(ALGraph G ,int k,int n) { //多段图ALGraph G,n为结点数,k为图的段数 //输入是按段的顺序给结点编号 int cost[100]; int d[100]; int path[100]; int j, r, i, min, w, value; node p; cost[n] = 0; for(j = n - 1; j >= 1; j--) //向前处理结点 { p = G->vertices[j].firstArc; min = p->value+cost[p->adjvex]; //初始化路径最小代价 r = p->adjvex; value = p->value; while(p != NULL) { //r是一个的这样的结点,权值c(j,r)+cost[r]取最小值 if((p->value + cost[p->adjvex]) < min) { min = p->value + cost[p->adjvex]; //p->value=c(j,r) r = p->adjvex; value = p->value; } p = p->nextarc; } cost[j] = value + cost[r]; //当前节点的代价值 d[j] = r; //决策阶段,各结点到终点最小代价路径上前方顶点的编号 } path[1] = 1; path[k] = n; for(i = 2; i <= k - 1; i++) //找出最小代价路径上的结点 path[i] = d[path[i - 1]]; printf("最小成本为:%d\n",cost[1]); printf("最小成本路径为: "); for(w = 1; w <= k; w++) printf("%d->", path[w]); } void main() { ALGraph g; int n,a,k; g = (ALGraph)malloc(sizeof(ALGraph)); printf("请输入多段图节点数目:"); scanf("%d", &n); printf("请输入多段图边的数目:"); scanf("%d", &a); printf("请输入多段图的段数:"); scanf("%d", &k); printf("输入多段图的弧的信息(弧头,弧尾,权值)\n"); build_adList(g, n, a); printf("多段图的邻接表为:\n"); print_Graph(g); fgraph(g, k, n); getch(); } 五.实验结果 多段图问题 算法设计与分析实验报告四 实验名称 贪心算法实现背包问题 评分 实验日期 年 月 日 指导教师 刘长松 姓名 刘飞初 专业班级 计算机0901 学号 10 一.实验要求 1. 优化问题 有n个输入,而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组 成,而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解,称为最优解。 2.贪心法求优化问题 算法思想:在贪心算法中采用逐步构造最优解的方法。在每个阶段,都作出一个看上去最优的决策(在一定的下)。决策一旦作出,就不可再更改。作出贪心决策的依据称为贪心准则(greedy criterion)。 3.一般方法 1)根据题意,选取一种量度标准。 2)按这种量度标准对这n个输入排序 3)依次选择输入量加入部分解中。如果当前这个输入量的加入,不满足约束条件,则不把此输入加到这部分解中。 procedure GREEDY(A,n) /*贪心法一般控制流程*/ //A(1:n)包含n个输入// solutions←φ //将解向量solution初始化为空/ for i←1 to n do x←SELECT(A) if FEASIBLE(solution,x) then solutions←UNION(solution,x) endif repeat return(solution) end GREEDY 4. 实现典型的贪心算法的编程与上机实验,验证算法的时间复杂性函数。 二.实验内容 1. 编程实现背包问题贪心算法。通过具体算法理解如何通过局部最优实现全局最优,并验证算法的时间复杂性。 2.输入5个的图的邻接矩阵,程序加入统计prim算法访问图的节点数和边数的语句。 3.将统计数与复杂性函数所计算的比较次数比较,用表格列出比较结果,给出文字分析。 三.程序算法 1. 背包问题的贪心算法 procedure KNAPSACK(P,W,M,X,n) //P(1:n)和W(1;n)分别含有按 P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值 和重量。M是背包的容量大小,而x(1:n)是解向量 real P(1:n),W(1:n),X(1:n),M,cu; integer i,n; X←0 //将解向量初始化为零 cu←M //cu是背包剩余容量 for i←1 to n do if W(i)>cu then exit endif X(i) ←1 cu←cu-W(i) repeat if i≤n then X(i) ←cu/ W(i) endif end GREEDY-KNAPSACK procedure prim(G,) status←“unseen” // T为空 status[1]←“tree node” // 将1放入T for each edge(1,w) do status[w]←“fringe” // 找到T的邻接点 dad[w] ←1; //w通过1与T建立联系 dist[w] ←weight(1,w) //w到T的距离 repeat while status[t]≠ “tree node” do pick a fringe u with min dist[w] // 选取到T最近的节点 status[u]←“tree node” for each edge(u,w) do 修改w和T的关系 repeat repeat 2. Prim算法 PrimMST(G,T,r){ //求图G的以r为根的MST,结果放在T=(U,TE)中 InitCandidateSet(…);//初始化:设置初始的轻边候选集,并置T=({r},¢) for(k=0;k struct goodinfo { float p; //物品效益 float w; //物品重量 float X; //物品该放的数量 int flag; //物品编号 };//物品信息结构体 void Insertionsort(goodinfo goods[],int n) { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; } }//按物品效益,重量比值做升序排列 void bag(goodinfo goods[],float M,int n) { float cu; int i,j; for(i=1;i<=n;i++) goods[i].X=0; cu=M; //背包剩余容量 for(i=1;i cu)//当该物品重量大与剩余容量跳出 break; goods[i].X=1; cu=cu-goods[i].w;//确定背包新的剩余容量 } if(i<=n) goods[i].X=cu/goods[i].w;//该物品所要放的量 for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].flag >n; goods=new struct goodinfo [n+1];// cout<<"请输入背包的最大容量:"; cin>>M; cout< >goods[i].w; cout<<"请输入第"<>goods[i].p; goods[i].p=goods[i].p/goods[i].w;//得出物品的效益,重量比 cout< to run agian"< to exit"< >j; } } 2. Prim算法 #include #include #include #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef int VRType; typedef int InfoType; typedef char VerTexType; typedef struct ArcCell { VRType adj; InfoType *info; }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VerTexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum, arcnum; }MGraph; typedef struct { VerTexType adjvex; VRType lowcost; }closedge[MAX_VERTEX_NUM]; void CreateGraph(MGraph &G); void MiniSpanTree_PRIM(MGraph G, VerTexType u); int LocateVex(MGraph G, VerTexType u); int minimum(closedge close); void main( void ) { int i, j; MGraph G; CreateGraph(G); for(i = 0; i < G.vexnum; i++) { for(j = 0; j < G.vexnum; j++) { cout< >G.vexnum>>G.arcnum; for(i = 0; i < G.vexnum; i++) { for(j = 0; j < G.vexnum; j++) G.arcs[i][j].adj = 88; } cout< >G.vexs[i]; cout< >hand; cin>>tide; cin>>weigh; while (hand != G.vexs[j]) j++; while (tide != G.vexs[k]) k++; G.arcs[j][k].adj = weigh; G.arcs[k][j].adj = weigh; j = 0; k = 0; cout< "; cout< close[j1].lowcost && close[j1].lowcost != 0) { client = close[j1].lowcost; j2 = j1; } j1++; } return j2; } 五.实验结果 1. 背包问题贪心算法