贪心算法解活动安排试验报告

1、实验 3 贪心算法解活动安排问题一 、实验要求1要求按贪心法求解问题； 2要求读文本文件输入活动安排时间区间数据； 3要求显示结果。二 、实验仪器和软件平台 仪器 ：带 usb 接口微机 软件平台： WIN-XP + VC+6.0三 、源程序#include stdafx.h#include#include#include#define N 50#define TURE 1#define FALSE 0int sN;/* 开始时间 */int fN;/* 结束时间 */int AN;/* 用 A 存储所有的 */int Partition(int *b,int *a,int p,int r);

2、void QuickSort(int *b,int *a,int p,int r);void GreedySelector(int n,int *s,int *f,int *A);int main()int n=0,i;while(n50)printf(n);printf( 请输入活动的个数 ,n=); scanf(%d,&n);if(n50) printf( 请输入小于 50 的数 !);printf(n 请分别输入开始时间 si 和结束时间 fi:nn); for(i=1;i=n;i+) printf(s%d=,i,i); scanf(%d,&si);printf(f%d=,i,i);sc

3、anf(%d,&fi);printf(n);QuickSort(s,f,1,n); / 按结束时间非减序排列 printf( 按结束时间非减序排列如下 :n); /* 输出排序结果 */ printf(n 序号 t 开始时间 结束时间 n);printf(n);for(i=1;i=n;i+)printf( %dt %dt %dn,i,si,fi); printf(n);GreedySelector(n,s,f,A);/ 贪心算法实现活动安排 printf( 安排的活动序号依次为： );for(i=1;i%d,i,si,fi);printf(n);system(pause);return 0;/

4、快速排序void QuickSort(int *b,int *a,int p,int r)int q;if(pr)q=Partition(b,a,p,r);QuickSort(b,a,p,q-1);/* 对左半段排序 */QuickSort(b,a,q+1,r);/* 对右半段排序 */产生中间数int Partition(int *b,int *a,int p,int r)int k,m,y,i=p,j=r+1;int x=ap;y=bp;while(1)while(a+ix);if(i=j)break;else k=ai;ai=aj;aj=k; m=bi;bi=bj;bj=m;ap=aj;

5、bp=bj;aj=x;bj=y;return j;/贪心算法实现活动安排void GreedySelector(int n,int *s,int *f,int *A)/用集合 A 来存储所选择的活动 A1=TURE; / 默认从第一次活动开始执行 int j=1; /j 记录最近一次加入到 A 中的活动 for(int i=2;i=fj)Ai=TURE; / 当 Ai=TURE 时，活动 i 在集合 A 中 j=i;else Ai=FALSE;四 、运行结果五 、实验小结贪心算法总是做出在当前看来最好的选择， 也就是说贪心算法并不从整体最 优考虑，它所作出的选择只是在某种意义上的局部最优选择。 活动安排问题就是 要在所给的活动集合中