2023年贪心算法解活动安排实验报告.docx

《2023年贪心算法解活动安排实验报告.docx》由会员分享，可在线阅读，更多相关《2023年贪心算法解活动安排实验报告.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验3贪心算法解活动安排问题一、实验规定1 .规定按贪心法求解问题；2 .规定读文本文献输入活动安排时间区间数据；3 .规定显示结果。二、实验仪器和软件平台仪器：带usb接口微机软件平台：WIN-XP + VC+6. 0三、源程序# includ e s td a fx.hi n c 1 ude# i n clud e inc 1 u d e# dcf i ne N 50de f i ne TURE 1# def i ne FALSE 0int sN;/*开始时间*/in t f IN； /*结束时间*/intANl； /*用A存储所有的*/int Par t iti o n(int * b

2、, i n t *a,int p,i n t r);voi d QuickSort( i nt * b,inl *a, int p ,i n t r );vo i d Gre e dyS e le c to r ( i nt n, i n t *s,in t *f,i n t *A);int m a in() i nt n=O,i；wh i 1 e(n50)|o-pri n tf( n);。pr i n t f(请输入活动的个数，n=);。scanf(% d 成n);。i f( n 50) p r i n t f (请输入小于 5 0 的数！ );I叩rintf( n请分别输入开始时间si和结

3、束时间f i:n n)；。f o r (i=l;i=n； i +)P rintf( s%d= i,i)；s canf(%d,&si);prin t f (f%d= , i ,i);scanf(%d,&f i 1);pri n tf(M n 0 );Q uickS ort( s ,f, l,n); 按结束时间非减序排列prinlfC按结束时间非减序排列如下:输出排序结果*/pri n tf(n序号t开始时间 结束时间n”)；p rin t f-n );fbr(i = 1 ； i=n； i+)print f ( %dt %d t %d n ,i,s i , f i);oprintf( -n);oG

4、ree d ySe 1 ector( n ,s, f,A) ;/ /贪心算法实现活动安排叩r i nt f (安排的活动序号依次为:)；afor(i=l ； i %d,i,si, fi);)叩rintf(n )；sys t em (paus e )；r e turn 0：)快速排序v oid Q u ic k S ort(in t * b ,int *a,int p Jnt r )(int q；if(pVr)(。 q=P a r t i t i o n (b,a,p,r);QuickSor t (b，2p,q-l);/* 对左半段排序 */Qui ckSort (b,a,q+ 1 ,r)； /

5、*对右半段排序 */产生中间数int Parti t ion(int *b, i nl * a j n t p,i n t r)(int k ,m, y , i= p , j=r+l;int x=ap ;y=b p 1;whi lc(l)whi 1 e(a + i x);0 if(i=j)brea k ；e 1 se。 (8ok=a i ;a i =a j ； a j = k;， m=b ij;bi=b j ; b I j =m;0 11a P =a(j;bp=bj;aj = x;bj=y;r e tur n j：)/贪心算法实现活动安排void Gre e dySele c tor(in t

6、 n, i n t *s, i nt *f, i nt *A)(/用集合A来存储所选择的活动A l=TURE;默认从第一次活动开始执行int j=l; /j记录最近一次加入到A中的活动for (int i=2; i = f j)。A i =TURE； / / 当 A i =TURE时，活动 i 在集合 A 中j = i；。)elseAiJ=FALSE;四、运营结果计算机算法设计与分析贪心法解活动安排问题,Debu八贪心法解活动安日回国请分别输入开始时间si和结束时间f li)：sU=lf 1=4s 2)-3fL2 3-5s3=5f3=7s4=0f4=6stSJ-6FE5J-10sC6=5H61=9s7=3f7J=8sr8J=1281-14sL9=2f9=13s10=810)=12sCll=8 旬 下时 如束 例结 序同 减项间开 时害节 结序 提0 12 456789111安排的活动序号依次为:1 1 44 578 81111 1214请按任意键继续.五、实验小结贪心算法总是做出在当前看来最佳的选择，也就是说贪心算法并不从整体最 优考虑，它所作出的选择只是在某种意义上的局部最优选择。活动安排问题就是 要在所给的活动集合中选出最大的相容活动子集合。该问题规定高效地安排一系 列争用某一公共资源的活动。贪心算法提供了一个简朴、美丽的方法使得尽也许 多的活动能兼容地使用公共资源。