贪心算法解活动安排实验报告.doc

实验3贪心算法解活动安排问题一、实验要求要求按贪心法求解问题;要求读文本文件输入活动安排时间区间数据;要求显示结果。二、实验仪器和软件平台仪器:带usb接口微机软件平台:WIN-XP+VC++、源程序#include""#include<>#include<>#include<algorithm>#defineN50#URE1#defineFALSE0ints[N];/*开始时间*/intf[N];/*结束时间*/intA[N];/*用A存储所有的*/intPartition(int*b,int*a,intp,intr);voidQuickSort(int*b,int*a,intp,intr);voidGreedySelector(intn,int*s,int*f,int*A);intmain(){ intn=0,i; while(n<=0||n>50) { printf("\n"); printf("请输入活动的个数,n="); scanf("%d",&n); if(n<=0)printf("请输入大于零的数!"); elseif(n>50)printf("请输入小于50的数!");} printf("\n请分别输入开始时间s[i]和结束时间f[i]:\n\n"); for(i=1;i<=n;i++) { printf("s[%d]=",i,i);scanf("%d",&s[i]); printf("f[%d]=",i,i);scanf("%d",&f[i]); printf("\n"); }QuickSort(s,f,1,n);//按结束时间非减序排列printf("按结束时间非减序排列如下:\n");/*输出排序结果*/printf("\n序号\t开始时间结束时间\n"); printf("-------------------------\n"); for(i=1;i<=n;i++) printf("%d\t%d\t%d\n",i,s[i],f[i]); printf("-------------------------\n"); GreedySelector(n,s,f,A);//贪心算法实现活动安排 printf("安排的活动序号依次为:"); for(i=1;i<=n;i++) { if(A[i]) printf("\n%d%d-->%d",i,s[i],f[i]);} printf("\n");system("pause");return0;}//快速排序voidQuickSort(int*b,int*a,intp,intr){ intq;if(p<r) { q=Partition(b,a,p,r);QuickSort(b,a,p,q-1);/*对左半段排序*/QuickSort(b,a,q+1,r);/*对右半段排序*/ }}//产生中间数intPartition(int*b,int*a,intp,intr){intk,m,y,i=p,j=r+1;intx=a[p];y=b[p];while(1) { while(a[++i]<x); whil