算法设计与分析实验(共10页)

1、精选优质文档-倾情为你奉上本科实验报告课程名称： 算法设计与分析 实验项目：分治法合并排序、 贪心法作业调度、动态规划法求多段图问题、回溯法求n皇后问题实验地点： 行知楼c122 专业班级： 软件1310 学号： 学生姓名： 葛文卿 指导教师： 王幸民 2015年 03 月 28 日实验项目分治法合并排序一、 实验目的掌握合并排序的基本思想掌握合并排序的实现方法学会分析算法的时间复杂度学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境程序设计语言：c+编程工具：microsoft visual studio 2

2、010四、算法描述和程序代码#include <iostream> using namespace std; void merge(int *data, int p, int q, int r) int n1, n2, i, j, k; int *left=NULL, *right=NULL; n1 = q-p+1; n2 = r-q; left = (int *)malloc(sizeof(int)*(n1); right = (int *)malloc(sizeof(int)*(n2); for(i=0; i<n1; i+) /对左数组赋值 lefti = datap+i

3、; for(j=0; j<n2; j+) /对右数组赋值 rightj = dataq+1+j; i = j = 0; k = p; while(i<n1 && j<n2) /将数组元素值两两比较，并合并到data数组 if(lefti <= rightj) datak+ = lefti+; else datak+ = rightj+; for(; i<n1; i+) /如果左数组有元素剩余，则将剩余元素合并到data数组 datak+ = lefti; for(; j<n2; j+) /如果右数组有元素剩余，则将剩余元素合并到data数组

4、datak+ = rightj; void mergeSort(int *data, int p, int r) int q; if(p < r) /只有一个或无记录时不须排序 q = (int)(p+r)/2); /将data数组分成两半 mergeSort(data, p, q); /递归拆分左数组 mergeSort(data, q+1, r); /递归拆分右数组 merge(data, p, q, r); /合并数组 int main() int n,i; int* input = NULL; /输入数据 cout<<"请输入数组的长度: " ci

5、n>>n; input = (int *)malloc(sizeof(int)*(n); cout<<"请对数组赋值: " for(i=0; i<n; +i) cin>>inputi; /处理数据 mergeSort(input,0,n-1); /输出结果 for(i=0; i<n; +i) cout<<inputi<<" " cout<<endl; return 0; for(; i<n1; i+) /如果左数组有元素剩余，则将剩余元素合并到data数组 data

6、k+ = lefti; for(; j<n2; j+) /如果右数组有元素剩余，则将剩余元素合并到data数组 datak+ = rightj; void mergeSort(int *data, int p, int r) int q; if(p < r) /只有一个或无记录时不须排序 q = (int)(p+r)/2); /将data数组分成两半 mergeSort(data, p, q); /递归拆分左数组 mergeSort(data, q+1, r); /递归拆分右数组 merge(data, p, q, r); /合并数组 int main() int n,i; int

7、* input = NULL; /输入数据 cout<<"请输入数组的长度: " cin>>n; input = (int *)malloc(sizeof(int)*(n); cout<<"请对数组赋值: " for(i=0; i<n; +i) cin>>inputi; /处理数据 mergeSort(input,0,n-1); /输出结果 for(i=0; i<n; +i) cout<<inputi<<" " cout<<endl; re

8、turn 0; 五、实验结果截图六、实验总结掌握了合并排序的基本思想，并实现了合并排序。实验项目贪心法作业调度一、实验目的掌握贪心算法的基本思想掌握贪心算法的典型问题求解进一步多级调度的基本思想和算法设计方法学会用贪心法分析和解决实际问题二、实验内容设计贪心算法实现作业调度，要求按作业调度顺序输出作业序列。如已知n=8，效益p=(35, 30, 25, 20, 15, 10, 5, 1)，时间期限 d=(4, 2, 4, 5, 6, 4, 5, 

9、7)，求该条件下的最大效益。三、实验环境程序设计语言：c+编程工具：microsoft visual studio 2010四、算法描述和程序代码#include<iostream>using namespace std;#define N 6/作业数#define M 3/机器数int t7,b,p7,s47,d4,c;void zuoye(int s47,int d4,int p7,int t7)int f;int n=2;for 

10、;(int i=1;i<=M;i+)si1=pi;di=ti;for (int l=M+1;l<=N;l+)if(d1<d2)f=1;elsef=2;if(df>d3)f=3;sfn=pl;n+;df=df+tl;for(int w=1;w<=3;w+)for(int r=1;r<=6;r+)if(swr!=0)     cout<<swr<<" " cout<<endl;void m

11、ain()cout<<"共有三台机器，请输入六个作业工作时间："    for(int i=1;i<=6;i+)cin>>ti;for(int e=1;e<=6;e+)pe=e;for(int j=1;j<=6;j+)for(int q=j+1;q<=6;q+)   /冒泡算法没问题     if(tq>tj)c=pq;pq=pj;pj=c;b=tq;tq=tj;

12、tj=b;zuoye( s, d, p, t);五、实验结果截图六、实验总结掌了贪心算法的基本思想学会了用贪心算法求解典型问题实验项目动态规划法求多段图问题一、 实验目的掌握动态规划算法的基本思想掌握多段图的动态规划算法选择邻接表或邻接矩阵方式来存储图分析算法求解的复杂度。二、实验内容设G=(V,E)是一个带权有向图，其顶点的集合V被划分成k>2个不相交的子集Vi，1<i<=k，其中V1和Vk分别只有一个顶点s（源）和一个顶点t（汇）。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考讲义p136图5

13、-24中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、实验环境程序设计语言：c+编程工具：microsoft visual studio 2010四、算法描述和程序代码#include <stdio.h>#include <stdlib.h>#define N 12 #define K 5 #define MAX 23767int costNN; int pathK; typedef struct nodeint v;int w;struct node *next;node;node LN; void init(node *L) int i, j;n

14、ode *p, *q; for (i = 0; i < N; i+) for (j = 0; j < N; j+) costij = MAX; cost01 = 9;cost02 = 7;cost03 = 3;cost04 = 2;cost15 = 4;cost16 = 2;cost17 = 1;cost25 = 2;cost26 = 7;cost37 = 11;cost46 = 11;cost47 = 8;cost58 = 6;cost59 = 5;cost68 = 4;cost69 = 3;cost79 = 5;cost710 = 6;cost811 = 4;cost911 =

15、 2;cost1011 = 5;/*生成邻接表*/ for (i = 0; i < N; i+)Li = (node *)malloc(sizeof(node);for (i = 0; i < N; i+)q = Li;for (j = 0; j < N; j+)if (costij > 0 && costij < MAX)p = (node *)malloc(sizeof(node);p->v = j;p->w = costij;q->next = p;q = p;q->next = NULL;void Method1()

16、 /*使用邻接矩阵存储*/ int i, j, maxlen, temp, vN, dN; for (i = 0; i < N; i+) vi = 0; for (i = N - 2; i >= 0; i-) for (maxlen = MAX, j = i + 1; j <= N - 1; j+) if (costij > 0 && costij + vj < maxlen) maxlen = costij + vj; temp = j; vi = maxlen; di = temp; path0 = 0; pathK-1 = N - 1;for

17、 (i = 1; i <= K - 2; i+) pathi = dpathi-1;void Method2(node *L) /*使用邻接表存储*/ int i, j, maxlen, temp, vN, dN;node *p;for (i = 0; i < N; i+) vi = 0; for (i = N - 2; i >= 0; i-) p = Li->next;maxlen = MAX; while (p)if (p->w + vp->v < maxlen) maxlen = p->w + vp->v; temp = p->

18、v;p = p->next; vi = maxlen; di = temp; path0 = 0; pathK-1 = N - 1;for (i = 1; i <= K - 2; i+) pathi = dpathi-1;void print() int i; for (i = 0; i < K; i+) printf("%d ", pathi + 1); printf("n");int main()init(&L); printf("最短路径:n "); Method1(); print(); printf("最短路径:n"); Method2(&L); print(); system("pause"); return 0;五、实验结果截图六、实验总结掌握了动态规划算法的基本思想掌握了多段图的动态规划算法实验项目回溯法求n皇后问题一、实验目的掌握回溯算法的基本思想通过n皇后问题求解熟悉回溯法使用蒙特卡洛方法分析算法的复杂度二、实验内容要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。三、实验环境程序设计语言：c+