算法分析實(shí)驗(yàn)報告--分治策略

1、算法設(shè)計(jì)與分析實(shí)驗(yàn)報告分治策略姓名：XXX專業(yè)班級：XXX學(xué)號XXX指導(dǎo)教師：XXX完成日期：XXX一、試驗(yàn)名稱：分治策略( 1) 寫出源程序，并編譯運(yùn)行( 2) 詳細(xì)記錄程序調(diào)試及運(yùn)行結(jié)果二、實(shí)驗(yàn)?zāi)康?1) 了解分治策略算法思想(2) 掌握快速排序、歸并排序算法(3) 了解其他分治問題典型算法三、實(shí)驗(yàn)內(nèi)容(1) 編寫一個簡單的程序，實(shí)現(xiàn)歸并排序。(2) 編寫一段程序，實(shí)現(xiàn)快速排序。(3) 編寫程序?qū)崿F(xiàn)循環(huán)賽日程表。設(shè)有 n=2k 個運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽?，F(xiàn) 要設(shè)計(jì)一個滿足以下要求的比賽日程表： (1)每個選手必須與其它 n-1 個選手各賽一次( 2)每個選手一天只能賽一場( 3)循環(huán)賽進(jìn)行

2、 n-1 天四、算法思想分析(1) 編寫一個簡單的程序，實(shí)現(xiàn)歸并排序。將待排序元素分成大小大致相同的 2 個子集合，分別對 2 個子集合進(jìn)行 排序，最終將排好序的子集合合并成為所要求的排好序的集合。(2) 編寫一段程序，實(shí)現(xiàn)快速排序。通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù) 變成有序序列。(3) 編寫程序?qū)崿F(xiàn)循環(huán)日賽表。按分治策略，將所有的選手分為兩組， n 個選手的比賽日程表就可以通 過為 n/2 個選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對選手進(jìn)行分

3、割， 直到只剩下 2 個選手時，比賽日程表的制定就變得很簡單。這時只要讓 這 2 個選手進(jìn)行比賽就可以了。五、算法源代碼及用戶程序(1) 編寫一個簡單的程序，實(shí)現(xiàn)歸并排序。#include#include#define MAX 10using namespace std;void merge(int array,int p,int q,int r)int i,k;int begin1,end1,begin2,end2;int* temp = new intr-p+1;begin1 = p;end1 = q;begin2 = q+1;end2 = r;k = 0;while(begin1 = e

4、nd1)&(begin2 = end2)if(arraybegin1 arraybegin2)tempk = arraybegin1;begin1+;elsetempk = arraybegin2;begin2+;k+;while(begin1 = end1) tempk+ = arraybegin1+;while(begin2 = end2)tempk+ = arraybegin2+;for(i = 0;i (r-p+1);i+)arrayp+i = tempi;delete(temp);void merge_sort(int data,int left,int right)if(left

5、right)int mid = (left + right)/2;merge_sort(data,left,mid);merge_sort(data,mid + 1,right); merge(data,left,mid,right);void main()int numberMAX = 0;srand(time(NULL);printf( 排序前： );for(int i = 0; i MAX; i+) numberi = rand() % 100; printf(%d , numberi);coutendl;merge_sort(number,0,9);printf( 排序后： );for

6、(int j = 0; j MAX; j+) printf(%d , numberj);(2) 編寫一段程序，實(shí)現(xiàn)快速排序。#include#include#define MAX 10#define SWAP(x,y) int t; t = x; x = y; y = t; using namespace std;void quicksort(int number,int left,int right)int i,j,s;if(left right)s = number(left + right)/2;i = left - 1;j = right + 1;while(1)while(numbe

7、r+i s); if(i=j) break;SWAP(numberi,numberj); quicksort(number,left,i-1); quicksort(number,j+1,right);void main()int numberMAX = 0; srand(time(NULL);printf( 排序前： );for(int i = 0; i MAX; i+) numberi = rand() % 100; printf(%d , numberi);coutendl;quicksort(number,0,9);printf( 排序后： );for(int j = 0; j MAX

8、; j+) printf(%d , numberj);(3) 編寫程序?qū)崿F(xiàn)循環(huán)賽日程表。#define MAXN 64/* 日程表數(shù)組 */#include #include #define MAX 32int aMAXMAX;void Copy(int tox, int toy, int fromx, int fromy, int n) int i, j;for (i=0; in; i+)+ ifromy for (j=0; jn; j+) atox + itoy + j = afromx + j;void Table(int k, int aMAX) int i, n = 1 k; int r;for (i=0; in; i+)a0i = i + 1;for (r=1; rn; r=1) for (i=0; in; i+=2*r) Copy(r, i + r, 0, i, r);Copy(r, i, 0, i + r, r);void Out(int aMAX, int n) int i, j;for (i=0; in; i+) for (j=0; jn; j+) printf(%3d, aij); printf(n);printf(n);getch();int main(