試驗二貪心算法-最少活動會場安排問題

1、中原工學院計算機學院實驗報告實驗項目名稱 實驗二、最少活動會場安排問題課程名稱學生姓名學生學號201400824204所在班級網(wǎng)絡(luò)14卓越學科專業(yè)網(wǎng)絡(luò)工程任課教師吳志剛完成日期2016年月 日實驗二最少活動會場安排問題一、實驗?zāi)康? .掌握貪心算法的基本概念和兩個基本要素2,熟練掌握貪心算法解決問題的基本步驟。3.學會利用貪心算法解決實際問題。二、實驗內(nèi)容? 問題描述：? 題目一：假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可 能少的會場。設(shè)計一個有效的貪心算法來進行安排，試編程實現(xiàn)。? 題目二：一輛汽車加滿油后，可行使n千米。旅途中有若干個加油站。 若要使沿途加油次數(shù)最少，設(shè)計一個有效算

2、法，指出應(yīng)在哪些加油站停靠加 油。? 數(shù)據(jù)輸入：個人設(shè)定，由鍵盤輸入。? 要求：上述題目任選一做。上機前，完成程序代碼的編寫?yīng)毩⑼瓿蓪嶒灱皩嶒瀳蟾嫒?、實驗步驟、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計描述提示：題目一：參考教材活動安排問題；有關(guān)隊列操作參考數(shù)據(jù)結(jié)構(gòu)。void GreedySelector( int n, int *s, int *f, int *A) J/用集合A來存儲所選擇的活動A1 = TURE; /默認從第一次活動開始執(zhí)行int j = 1;/j記錄最近一次加入到 A中的活動for ( int i = 2; i = fj) Ai = TURE; /當Ai=TURE時，活動i在集合 A中j

3、 = i;else Ai = FALSE;、函數(shù)調(diào)用及主函數(shù)設(shè)計(可用函數(shù)的調(diào)用關(guān)系圖說明)快排選擇活動程序調(diào)試及運行結(jié)果分析實驗總結(jié)在做本實驗之前，自己看了課本上所列舉的貪心法解活動安排問題的代碼， 代碼很簡單，很容易理解，于是就按課本的代碼實現(xiàn)。通過幾個測試用例測試發(fā) 現(xiàn)結(jié)果不對，后來發(fā)現(xiàn)自己忘了進行貪心法的一個前提條件，事先沒有按各個活動結(jié)束時間對所有活動進行非遞減排序，所以才會導致結(jié)果錯誤。經(jīng)過修正后， 自己真正理解了貪心法解活動安排問題的原理。四、主要算法流程圖及程序清單1、主要算法流程圖：快速排序JX產(chǎn)生中間數(shù) J一1貪心算法實現(xiàn)活動安排一 主函數(shù)調(diào)用2、程序清單（程序過長，可附主

4、要部分）#include stdafx.h#include #include #include define N 50define TURE 1define FALSE 0int sN; /*開始時間*/int fN;/*結(jié)束時間*/int AN; /*用A存儲所有的*/void GreedySelector( int n, int *s, int *f, int *A); 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

5、+ix);if (i = j)break;else k = ai; ai = aj; aj = k; m = bi; bi = bj; bj = m;)ap = aj;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);/* 對右半段排序 */ /產(chǎn)生中間數(shù)int main() int n = 0, i;while (n 50) printf( n

6、);printf(請輸入活動的個數(shù)：);scanf s( %d, &n);if (n 50) printf( 請輸入小于 50 的數(shù)!);)printf( n請分別輸入開始時間si和結(jié)束時間fi:nn);for (i = 1; i = n; i+)( printf( s%d= , i, i); scanf s( %d”, &si); printf( f%d= , i, i); scanf_s( %d”, &fi); printf( n);)QuickSort(s, f, 1, n);/按結(jié)束時間非減序排列printf(按結(jié)束時間非減序排列如下:n ); /*輸出排序結(jié)果*/printf( n

7、序號t開始時間結(jié)束時間n);printf(n);for (i = 1; i = n; i+)printf( %dt %dt %dn, i, si, fi);printf(n);GreedySelector(n, s, f, A);/貪心算法實現(xiàn)活動安排printf(安排的活動序號依次為：)；for (i = 1; i = n; i+)(if (Ai) printf( n%d , i); printf( n);system( pause);return 0; /快速排序/產(chǎn)生中間數(shù)/貪心算法實現(xiàn)活動安排void GreedySelector( int n, int *s, int *f, int *A) /用集合A來存儲所選擇的活動A1 = TURE; /默認從第一次