實驗內容

（1）活動安排問題

????設有n個活動的集合E={1, 2, …, n}，其中每個活動都要求使用同一資源，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi，且si?<fi?。如果選擇了活動i，則它在半開時間區間[si, fi)內占用資源。若區間[si, fi)與區間[sj, fj)不相交，則稱活動i與活動j是相容的。?隨機生成n個任務（n=8,16,32…）,用貪心法求解，分析算法的時間復雜度，做出圖像，橫坐標為活動個數，縱坐標為執行時間。

（2）線段覆蓋

問題描述：在一維空間中隨機生成N（N=8,16,32…）條線段的起始坐標與終止坐標，要求求出這些線段一共覆蓋了多大的長度（重疊區域只算一次）。分析算法的時間復雜度，畫出算法的執行時間隨N變化的曲線圖。

實驗結果

（1）活動安排問題

運行時間與n輸入大小的曲線圖

算法中將各個活動按照結束時間從小到大排序，時間復雜度為O（nlogn）,依次考察每個活動，時間復雜度為O（n），算法的時間復雜度為O（nlogn）

（2）線段覆蓋

運行時間由于輸入個數的曲線圖

算法中對線段進行按起點排序的時間復雜度是O（nlogn），依次對剩余線段進行判斷時的時間復雜度時O（n），整個算法的時間復雜度應為O（nlogn）

源代碼

活動安排問題

#include<iostream>
#include<time.h>
using namespace std;
void sort(int n, int s[], int f[])//按照結束時間非遞減排序
{int a, b, i, j;for (i = 0; i < n; i++)for (j = i + 1; j < n; j++)if (f[i] > f[j]){a = f[i]; f[i] = f[j]; f[j] = a;b = s[i]; s[i] = s[j]; s[j] = b;}
}
int Greedy(int n, int s[], int f[], bool B[])
{B[1] = true;//將第一個活動先安排int j = 1, count = 1; //count為被安排的節目個數for (int i = 2; i <= n; i++){if (s[i] >= f[j])//活動i與集合B中最后結束的活動相容{B[i] = 1;//安排活動ij = i;count++;}elseB[i] = 0;}return count;//返回已安排的活動個數
}
int main()
{srand((unsigned int)time(NULL));int a, b, n, i;bool B[2048];int s[2048], f[2048];clock_t start, end;cout << "輸入n的大小：";cin >> n;for (i = 0; i < n; i++){a = rand() % 1000 + 1;b = rand() % 1000 + 1;if (a > b){f[i] = a;s[i] = b;}else{s[i] = a;f[i] = b;}}start = clock();for (i = 0; i < n; i++)sort(n, s, f);int g=Greedy(n, s, f, B);cout << "活動安排的個數是：" << g << endl;for (i = 1; i <= n; i++)cout << B[i] << " ";end = clock();cout << endl;cout << "安排活動耗時：" << double(end - start)*1000 / CLOCKS_PER_SEC<<" ms";return 0;
}

線段覆蓋

#include<iostream>
#include<time.h>
using namespace std;
struct line//線段結構體
{int start;int end;
};
void sort(line l[], int n)//將線段按照大小排序
{int i, j;line temp, temp1;for (i = 0; i < n; i++)for (j = 0; j < n - i - 1; j++){if (l[j].start > l[j + 1].start){//起點小的在前面temp = l[j];l[j] = l[j + 1];l[j + 1] = temp;}if (l[j].start == l[j + 1].start && l[j].end > l[j + 1].end){//起點相同則終點小的在前面temp1 = l[j];l[j] = l[j + 1];l[j + 1] = temp1;}}
}
int cover(line l[], int n, int length)
{int i, len = length;if (n == 1)//只有一個線段直接返回長度return len;for (i = 1; i < n; i++){if (l[i].start >= l[i - 1].start && l[i].start <= l[i - 1].end && l[i].end >= l[i - 1].end)len += l[i].end - l[i - 1].end;//線段長度增加兩終點之差else if (l[i].start >= l[i - 1].end)len += l[i].end - l[i].start;//線段長度增加當前線段的長度else if (l[i].start >= l[i - 1].start && l[i].end <= l[i - 1].end)l[i].end = l[i - 1].end;//線段長度不增加}return len;
}
int main()
{line l[16384];int n, i, ln, length;clock_t cstart, cend;srand((unsigned)time(NULL));cout << "輸入線段的個數：";cin >> n;cstart = clock();for (i = 0; i < n; i++){l[i].start = rand() % 100 + 1;l[i].end = rand() % 100 + 1;}sort(l, n);//對所有線段進行排序ln = l[0].end - l[0].start;length = cover(l, n, ln);//求線段覆蓋的長度cend = clock();cout <<"線段覆蓋長度："<< length << endl;cout << "耗時" << double(cend - cstart) * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}

感謝大家的觀看