计算机算法设计与分析期末考试复习资料.doc

一、算法设计实例 快速排序（分治法） int partition(float a[], int p, int r) { int i= p, j=r+1; float x = a[p]; while(1) { while(a[++i] x); while(a[--j] x); if(i = j) break; swap (a[i], a[j]); } a[p] = a[j]; a[j] = x; return j; } void Quicksort(float a[], int p, int r) { //快速排序 if(p r) { int q = partition(a, p, r); Quicksort(a, p, q-1); Quicksort(a, p+1, r); } } 归并排序（分治法） void mergesort (Type a[], int left, int right) { if (left rigth) { int mid = (left + right)/2; //取中点 mergesort (a, left, mid); mergesort (a, mid+1, right); mergesort (a, b, left, right);//合并到数组b mergesort (a, b, left, right);//复制到数组a } } 背包问题（贪心算法） void knapsack (int n, float m ,float v[], float w[], float x[]) { sort(n, v, w) //非递增排序 int i; for (i=1 ; i=n; i++) x[i] = 0; float c = m; for (i= 1; i=n; i++) { if (w[i] c) break; x[i] = 1; c -= w[i]; } if (i = n) x[i] = c/w[i] ; } 活动安排问题（贪心算法） void Greadyselector (int n, Type s[], Type f[], bool A[]) { //s[i] 为活动结束时间， f[j]为j活动开始时间 A[i] = true; int j= 1; for (i=2; i=n; i++) { if (s[i] = f[j]) { A[i] = true; j=i; } else A[i] = false; } } 喷水装置问题（贪心算法） void knansack (int w, int d, float r[], int n) { //w为草坪长度 d为草坪宽度 r[]为喷水装置的喷水半径， //n为n种喷水装置 ， 喷水装置的喷水半径 = d/2 sort (r[], n); //降序排序 count = 0; //记录装置数 for (i=1; i=n; i++) x[i] = 0; //初始时， 所有喷水装置没有安装 x[i]=0 for (i=1; w = 0; i++) { x[i] = 1; count ++; w = w - 2*sqart(r[i]*r[i] - 1); } count 装置数: count end1; for (i=1; i= n; i++) count 喷水装置半径： r[i] end1; } 最优服务问题（贪心算法） double greedy (rectorint x, int s) { rector int st(s+1, 0); rector int su(s+1 ,0); int n=x.size(); //st[] 是服务数组， st[j]为第j个队列上的某一个顾客的等待时间 //su[] 是求和数组， su[j]为第j个队列上所有顾客的等待时间 sort(x.begin(), x.end()); //每个顾客所需要的服务时间升序排列