貪心算法解活動(dòng)安排實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn) 3 貪心算法解活動(dòng)安排問題一 、實(shí)驗(yàn)要求1要求按貪心法求解問題； 2要求讀文本文件輸入活動(dòng)安排時(shí)間區(qū)間數(shù)據(jù)； 3要求顯示結(jié)果。二 、實(shí)驗(yàn)儀器和軟件平臺(tái)儀器 ：帶 usb 接口微機(jī) 軟件平臺(tái)： WIN-XP + VC+三 、源程序#include ""#include<>#include<> #include<algorithm> #define N 50#define TURE 1#define FALSE 0int sN;/* 開始時(shí)間 */int fN;/* 結(jié)束時(shí)間 */ int AN;/* 用 A 存儲(chǔ)所有的 */ int

2、Partition(int *b,int *a,int p,int r); 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(n<=0|n>50)printf("n");printf(" 請(qǐng)輸入活動(dòng)的個(gè)數(shù) ,n="); scanf("%d",&n);if(n<=0) printf(" 請(qǐng)輸入大于零的數(shù) !")

3、; else if(n>50) printf(" 請(qǐng)輸入小于 50 的數(shù) !");printf("n 請(qǐng)分別輸入開始時(shí)間 si 和結(jié)束時(shí)間 fi:nn"); for(i=1;i<=n;i+) printf("s%d=",i,i); scanf("%d",&si);printf("f%d=",i,i);scanf("%d",&fi);printf("n");QuickSort(s,f,1,n); / 按結(jié)束時(shí)間非減序排列 prin

4、tf(" 按結(jié)束時(shí)間非減序排列如下 :n"); /* 輸出排序結(jié)果 */ printf("n 序號(hào) t 開始時(shí)間 結(jié)束時(shí)間 n");printf("n");for(i=1;i<=n;i+)printf(" %dt %dt %dn",i,si,fi); printf("n");GreedySelector(n,s,f,A);/ 貪心算法實(shí)現(xiàn)活動(dòng)安排 printf(" 安排的活動(dòng)序號(hào)依次為： ");for(i=1;i<=n;i+)if(Ai)printf("

5、n%d %d->%d",i,si,fi);printf("n");system("pause");return 0;/快速排序void QuickSort(int *b,int *a,int p,int r)int q;if(p<r)q=Partition(b,a,p,r);QuickSort(b,a,p,q-1);/* 對(duì)左半段排序 */QuickSort(b,a,q+1,r);/* 對(duì)右半段排序 */產(chǎn)生中間數(shù)int Partition(int *b,int *a,int p,int r)int k,m,y,i=p,j=r+1;

6、int x=ap;y=bp;while(1)while(a+i<x);while(a-j>x);if(i>=j)break;else k=ai;ai=aj;aj=k; m=bi;bi=bj;bj=m;ap=aj;bp=bj;aj=x;bj=y;return j;/貪心算法實(shí)現(xiàn)活動(dòng)安排void GreedySelector(int n,int *s,int *f,int *A)/用集合 A 來存儲(chǔ)所選擇的活動(dòng) A1=TURE; / 默認(rèn)從第一次活動(dòng)開始執(zhí)行 int j=1; /j 記錄最近一次加入到 A 中的活動(dòng) for(int i=2;i<=n;i+)/fj 為當(dāng)前集合

7、 A 中所有活動(dòng)的最大結(jié)束時(shí)間/活動(dòng) i 的開始時(shí)間不早于最近加入到集合A 中的 j 的時(shí)間 fjif(si>=fj)Ai=TURE; / 當(dāng) Ai=TURE 時(shí)，活動(dòng) i 在集合 A 中 j=i;else Ai=FALSE;四 、運(yùn)行結(jié)果IT”下心貝機(jī)算泛-呂令棲、冶譏法解注殆去楷伺謬-wm公常&丈採活曲寺ii肓分別輸入開始時(shí)伺工“利結(jié)車時(shí)閆 w；hn i-iIf n i =4sEJJ-S f131-7= M3-0LlC4J-6f C53-10c ILb J £ fEG-9H?J=Jrcvi-8k I n 1 =1 ?Ircsi-ti五、實(shí)驗(yàn)小結(jié)貪心算法總是做出在當(dāng)前看來最好的選擇， 也就是說貪心算法并不從整體最 優(yōu)考慮，它所作出的選擇只是