算法设计与分析软件.docx

算法设计与分析实验报告项目名称 分治算法实验 专业班级 软件工程1503 学 号 3903150333 姓 名 曾永豪 实验成绩：批阅教师：年 月 日实验1分治算法实验一、实验目的1. 了解分治策略算法思想2. 掌握快速排序、归并排序算法3. 了解其他分治问题典型算法二、实验内容1编写一个简单的程序，实现归并排序。2. 编写一段程序，实现快速排序。3. 编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 三、算法思想分析大问题分解为子问题，这些子问题相互独立且与原问题相同。分别求解子问题，合并解，自底向上逐步求出原来问题的解。四、实验过程分析 写在代码注释中5、 算法源代码及用户屏幕 1、归并排序：#include using namespace std; #define N 7 /待排序数据个数void merge(int array, int p, int q, int r);void merge_sort(int data, int p, int r);/void main()int data = 44, 12, 145, -123, -1, 0, 121; cout-array-endl; for(int i=0;iN;i+)coutdatai ; coutn-merge sort-n; merge_sort(data, 0, N-1); for(i=0;iN;i+)coutdatai ; coutendl; /void merge(int array, int p, int q, int r) int i,k; int begin1,end1,begin2,end2; int* temp = new int r-p+1; /申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 begin1= p; end1 = q; /设定两个指针，最初位置分别为两个已经排序序列的起始位置 begin2 = q+1; end2 = r; k = 0; while(begin1 = end1)&( begin2 = end2) /比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 if(arraybegin1arraybegin2) tempk = arraybegin1; begin1+; else tempk = arraybegin2; begin2+; k+; while(begin1=end1) /若第一个序列有剩余，直接拷贝出来粘到合并序列尾 tempk+ = arraybegin1+; while(begin2=end2) /若第二个序列有剩余，直接拷贝出来粘到合并序列尾 tempk+ = arraybegin2+; for (i = 0; i (r - p +1); i+) /将排序好的序列拷贝回数组中 arrayp+i = tempi; delete (temp); /void merge_sort(int data, int left, int right) if(left right) int mid = (left+ right) / 2; merge_sort(data, left, mid); cout0-left,mid:left,midendl; /观察语句，用来理解递归 merge_sort(data, mid+1, right); cout1-left,mid:left,midendl;/观察语句，用来理解递归 merge(data, left, mid, right); int i; for(i=left;i=right;i+) /观察语句，用来理解递归 coutdatai,; coutendl; 2、快速排序：#include #include #includeusing namespace std;#define MAX 10 #define SWAP(x,y) int t; t = x; x = y; y = t; int partition(int, int, int); void quicksort(int, int, int); void main() int numberMAX = 0; int i; srand(time(NULL); cout排序前：; for(i = 0; i MAX; i+) numberi = rand() % 100; coutsetw(6)numberi; quicksort(number, 0, MAX-1); coutn排序后：; for(i = 0; i MAX; i+) coutsetw(6)numberi; coutn; int partition(int number, int left, int right) int i, j, s; s = numberright; i = left-1 ; for(j = left; j right; j+) if(numberj = s) i+; SWAP(numberi, numberj); SWAP(numberi+1, numberright); return i+1; void quicksort(int number, int left, int right) int q; if(left right) q = partition(number, left, right); quicksort(number, left, q-1); quicksort(number, q+1, right); 3、循环赛日程表：#include #include using namespace std;#define MAXN 64#define MAX 32 int aMAXMAX; /日程表数组void Copy(int tox, int toy, int fromx, int fromy, int n) int i, j; for (i=0; in; i+) for (j=0; jn; j+) atox + itoy + j = afromx + ifromy + j; void Table(int k, int aMAX) int i, n = 1 k; int r; for (i=0; in; i+) a0i = i + 1; for (r=1; rn; r=1) for (i=0; in; i+=2*r) Copy(r, i + r, 0, i, r); Copy(r, i, 0, i + r, r); void Out(int aMAX, int n) int i, j; for (i=0; in; i+) for (j=0; jn; j+) coutsetw(3)aij; coutn; printf(n); void main() int i; for (i=0; i5; i+) int len=1 i; /len比赛队伍数,左移一位扩大2倍 Table(i, a); Out(a, len); 六、实验小结这次实验使得我们能把算法联系到实际并实现具体功能，使得我们对分治算法有更深地了解，深刻理解了分治算法“分而治之”的思想，锻炼了我们动手操作的能力。算法设计与分析实验报告项目名称 贪心算法实验 专业班级 软件工程1503 学 号 3903150333 姓 名 曾永豪 实验成绩：批阅教师：年 月 日实验2贪心算法实验1、 实验目的 1. 了解贪心算法思想 2. 掌握贪心法典型问题，如背包问题、作业调度问题等。2、 实验内容1. 编写一个简单的程序，实现单源最短路径问题。2. 编写一段程序，实现找零。【问题描述】当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）。3. 编写程序实现多机调度问题【问题描述】要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。3、 算法思想分析 Dijkstra算法等。四、实验过程分析 写在代码注释中5、 算法源代码及用户屏幕 1、单源最短路径问题：#includeusing namespace std;/ Graph.h#define maxPoint 100class CGraphpublic:CGraph(void);CGraph(void);bool SetGraph( double gmaxPointmaxPoint , int startPoint , int size );bool Dijkstra();void Display();int GetStartPoint();double GetBestWay( int dest , int path , int &pathLen );private:bool solved;/标志当前图是否已经求解double graphmaxPointmaxPoint;/当前图布局int size;/地图大小int startPoint;/起点double distmaxPoint;/当前图的解int prevmaxPoint;/ Graph.cppCGraph:CGraph(void)for( int i = 0 ; i maxPoint ; i+ ) for( int j = 0 ; j maxPoint ; j+ ) graphij = -1;startPoint = -1;size = -1;solved = false; /当前图还没有求解CGraph:CGraph(void)/bool CGraph:SetGraph( double gmaxPointmaxPoint , int startPoint , int size )for( int i = 0 ; i size ; i+ ) for( int j = 0 ; j startPoint = startPoint;this-size = size;solved = false;Dijkstra();return true;/bool CGraph:Dijkstra()bool smaxPoint;for( int j = 0 ; j size ; j+ ) distj = graphstartPointj; sj = false; if( distj 0 ) /disti0，表示没有路径连接 结点startPoint 与 结点j prevj = 0; else prevj = startPoint;/从起点出发diststartPoint = 0;sstartPoint = true;for( int i = 0 ; i size ; i+ ) double temp; int u = startPoint; bool flag = false; for( int j = 0 ; j 0 & distj temp ) u = j; temp = distj; else u = j; temp = distj; flag = true; su = true; for( j = 0 ; j 0 ) double newDist = distu + graphuj; if( distj 0 | newDist distj ) distj = newDist; prevj = u; solved = true;return true;/void CGraph:Display()printf( 当前地图的邻接矩阵n );for( int i = 0 ; i size ; i+ ) for( int j = 0 ; j size ; j+ ) printf( %5.f , graphij ); printf( n );/double CGraph:GetBestWay( int dest , int path , int &pathLen )int p = dest;int thewaymaxPoint;int len = 0;while( p != startPoint ) thewaylen = p; p = prevp; len+;thewaylen = startPoint;len+;for( int i = 0 , j = len - 1 ; i len ; i+ , j- ) pathi = thewayj;pathLen = len;return distdest;/int CGraph:GetStartPoint()return startPoint;/ Dijkstra.cpp : 定义控制台应用程序的入口点。void main()double graphmaxPoint = 0 , 10 , -1 , 30 , 100 , -1 , 0 , 50 , -1 , -1 , -1 , -1 , 0 , -1 , 10 , -1 , -1 , 20 , 0 , 60 , -1 , -1 , -1 , -1 , 0 ;int size = 5;int start = 0;int dest = 1;int pathlen;int pathmaxPoint;double dist;CGraph g;g.SetGraph( graph , start , size );g.Display();printf( -n );for( dest = 0 ; dest size ; dest+ ) dist = g.GetBestWay( dest , path , pathlen ); printf( 从 %d 到 %d 的最短路径长 %.fn , g.GetStartPoint() , dest , dist ); printf( 所经结点为:n ); for( int i = 0 ; i pathlen ; i+ ) printf( %3d , pathi ); printf( n-n );2、 找零问题：#includeusing namespace std;#define NUM 4void main() int mNUM=25,10,5,1; int n; /假设n=99 cinn; coutn的找钱方案为：; for(int i=0;i=mi&n0) coutmi ; n-=mi;3、 多机调度问题：#include using namespace std;#define N 10 /作业数#define M 3 / 机器数void sort(int t,int n);int set_work1(int t,int n);int max(int t,int num);int min(int t,int m);int set_work2(int t,int n);/S数组存储每台机器当前已分配任务总耗时static int timeN=2,8,18,32,50,72,98,128,182,200,sM=0,0,0;void main()sort(time,N); if(M=N) /作业数小于机器数 coutset_work1(time,N)endl; else coutset_work2(time,N)endl; void sort(int t,int n)for(int k=0;kn-1;k+) /用选择法将处理时间从大到小排序 int j=k; for (int i=k; itj) j=i; int temp=tj;tj=tk;tk=temp; int max(int t,int num) /max函数求解处理时间总和最长 int max=t0; for(int i=1;inum;i+) if(maxti) max=ti; return max;int min(int t,int m) int min=0; /min记录目前处理作业时间和最小的机器号 for(int i=1;isi) min=i; return min;int set_work1(int t,int n) int m=0; for(int i=0;in;i+) /分派作业 sm+=ti; return max(s,N);int set_work2(int t,int n) for(int i=0;in;i+) smin(s,M)+=ti; return max(s,M);算法设计与分析实验报告项目名称 动态规划算法实验 专业班级 软件工程1503 学 号 3903150333 姓 名 曾永豪 实验成绩：批阅教师：年 月 日实验3动态规划算法实验1、 实验目的1. 掌握动态规划方法贪心算法思想2. 掌握最优子结构原理3. 了解动态规划一般问题二、实验内容1. 编写一个简单的程序，解决0-1背包问题。设N=5，C=10，w=2，2，6，5，4,v=6,3,5,4,62. 合唱队形安排问题【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK， 则他们的身高满足T1.Ti+1TK(1=i=K)。已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。3、 算法思想分析 与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。四、实验过程分析 写在代码注释中5、 算法源代码及用户屏幕1、0-1背包问题：#define N 5#define C 10#include stdlib.hint i=0,j=0;void KnapSack(int v,int w,int c,int n,int m11)int jMax=min(wn-1,c);for (j=0;j=jMax;j+)/*m(n,j)=0 0=jwn*/mnj=0;for (j=wn;j=wn*/mnj=vn;for (i=n-1;i1;i-) int jMax=min(wi-1,c);for (j=0;j=jMax;j+)/*m(i,j)=m(i+1,j) 0=jwi*/ mij=mi+1j;for (j=wi;j=wn*/ mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c;if(c=w1)m1c=max(m1c,m2c-w1+v1);void traceback(int m11,int w,int c,int n,int x)for(i=1;i0 ? 1:0); main() int n=N,c=C,wN+1,vN+1; int mN+1C+1=0; int xN+1=0; clrscr(); printf(Please input w%dn,n); for(i=1;i=5;i+) scanf(%d,&wi); printf(Please input v%dn,n); for(i=1;i=5;i+) scanf(%d,&vi); KnapSack(v,w,c,n,m); traceback(m,w,c,n,x); printf(m110=%dn,m110); for(i=1;i=5;i+)printf(%2d,xi); /*实验数据2 2 6 5 4 6 3 5 4 6*/2、 合唱队形安排问题：#include #include using namespace std;#define MAXN 200void print_array();int N,aMAXN, bMAXN, cMAXN;void main()int i, j, max; do cinN; while(N=MAXN);for (i = 1; i ai;memset(b, 0, sizeof(a);memset(c, 0, sizeof(c);/*左侧的最长上升子序列*/b1 = 1;for (i = 2; i = 1; j-)if (aj max)max = bj;bi = max + 1;/*求左侧的最长上升子序列*/cN = 1;for (i = N - 1; i 0; i-)max = 0;for (j = i + 1; j = N; j+)if (aj max) max = cj;ci = max + 1;/*枚举求最长队形*/max = b1 + c1;for (i = 2; i max)max = bi + ci;cout出列人数:N - max + 1endl;print_array(); /输出数组a、b、cvoid print_array()int i;couti:; for(i=1;i=N;i+) coutsetw(5)i; coutendl; printf(ai:);for(i=1;i=N;i+) coutsetw(4)ai; coutendl; coutbi;for(i=1;i=N;i+) coutsetw(4)bi; coutendl; coutci;for(i=1;i=N;i+) coutsetw(4)ci; coutendl;六、实验小结这次实验使得我们能把算法联系到实际并实现具体功能，使得我们对动态规划算法有更深地了解，锻炼了我们动手操作的能力。算法设计与分析实验报告项目名称 回溯算法实验 专业班级 软件工程1503 学 号 3903150333 姓 名 曾永豪 实验成绩：批阅教师：年 月 日实验4回溯法实验1、 实验目的1. 掌握回溯算法思想2. 掌握回溯递归原理 3. 了解回溯法典型问题二、实验内容1. 编写一个简单的程序，解决8皇后问题。2. 批处理作业调度问题问题描述给定n个作业的集合J=(J1, J2, , Jn)。每一个作业Ji都有两项任务需要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji需要机器i的处理时间为tji，i=1,2, ,n; j=1,2。对于一个确定的作业调度，设Fji是作业i在机器i上完成处理的时间。则所有作业在机器2上完成处理的时间和成为该作业调度的完成时间和。 批处理作业调度问题要求对于给定的n个作业，制定一个最佳的作业调度方案，使其完成时间和达到最小。 要求输入： 1）作业数 2）每个作业完成时间表： 作业完成时间机器1机器2 作业121 作业231 作业323 要求输出： 1）最佳完成时间 2）最佳调度方案 提示：算法复杂度为O(n!),建议在测试的时候n值不要太大，可以考虑不要超过12。3. 数字全排列问题任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。注意：数字不能重复，N由键盘输入（N=9）。 3、 算法思想分析 回溯法是带优化的穷举法。回溯法的基本思想：在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程中逐步构造出状态空间树，即边搜索，边构造。四、实验过程分析 写在代码注释中5、 算法源代码及用户屏幕1、8皇后问题：/*N皇后问题*/#includeiostreamusing namespace std;#define N 8 /N为皇后个数int count=0;int MN=0,L2*N=0,R2*N=0; /M表示竖线，L左斜线，R右斜线int ANN=0,n; /初始化棋盘，Aij表示i行j列是否有皇后void print(); int mytry(int i); /void main() n=mytry(0); coutendlcount=nendl;/*输出*/void print() int i,j; for(i=0;iN;i+) for(j=0;jN;j+) cout Aij; coutendl; /*试探棋盘每一行皇后的位置函数*/int mytry(int i) int j; for(j=0;jN;j+) if(!Mj&!Li-j+N&!Ri+j) /*安全检查*/ Aij=i+1; /*放皇后*/ Mj=Li-j+N=Ri+j=1; if(i=N-1)print();coutendl;count+; else mytry(i+1); /*试探下一行*/ Aij=0; /*去皇后*/ Mj=Li-j+N=Ri+j=0; return count; /*/2、 批处理作业调度问题：import java.util.*;public class FlowShopstatic int n; /作业数static int f1; /机器1完成处理时间static int f; /完成时间和static int bestf; /当前最优值static int m; /各作业所需要的处理时间static int x; /当前作业调度static int bestx; /当前最优作业调度static int f2; /机器2完成处理时间public static void trackback(int i) if (i = n) for (int j = 0; j n; j+) bestxj = xj;bestf = f; else for (int j = i; j 0) f2i = (f2i - 1 f1) ? f2i - 1 : f1) + mxj1; else f2i = f1 + mxj1;f += f2i;if (f bestf) swap(x, i, j);trackback(i + 1);swap(x, i, j);f1 -= mxj0;f -= f2i;private static void swap(int x, int i, int j) int temp = xi;xi = xj;xj = temp;private static void test() n = 3;int testm = 2, 1, 3, 1, 2, 3;m = testm;int testx = 0, 1, 2;x = testx;bestx = new intn;f2 = new intn;f1 = 0;f = 0;bestf = Integer.MAX_VALUE;trackback(0);System.out.println(Arrays.toString(bestx);System.out.println(bestf);public static void main(String args) test();System.out.println(Hello World!);3、 数字全排列问题：#include stdio.h#include conio.hint num,cont=0;main() int i,n,a30; printf(enter N :); scanf(%d,&num); for(i=1;i=num;i+) ai=i; perm(a,1); printf(n%d,cont); getch();int perm(int b, int i)int k,j,temp; if(i=num) for(k=1;k=num;k+) printf(%d ,bk); printf(t); cont+; else for(j=i;j=num;j+) temp=bi;bi=bj,bj=temp; perm(b,i+1); temp=bi;bi=bj,bj=temp; return(0);算法设计与分析实验报告项目名称 算法综合实验 专业班级 软件工程1503 学 号 3903150333 姓 名 曾永豪 实验成绩：批阅教师：年 月 日实验5算法综合实验1、 实验目的1. 理解和复习所学各种算法的概念2. 掌握和复习所学各种算法的基本要素3. 掌握各种算法的优点和区别4. 通过应用范例掌握选择最佳算法的设计技巧与策略2、 实验内容1. 使用贪心算法、回溯法、