分治法求最大子段和问题.doc

。分治法求最大子段和问题共有四种方法：算法一； 算法二；算法三、Divide and Conquer算法四源代码、On-line Algorithm算法一源代码： /*Given (possibly negative) integers A1, A2, , AN, find the maximum value. 找最大子段和*/#include#include #include int MaxSubsequenceSum(int A,int N);main() int i,N,*A,MaxSum,judge; LARGE_INTEGER begin,end,frequency; /代表64位有符号整数，记录程序运行时间 QueryPerformanceFrequency(&frequency);/可以获得当前的处理器的频率 printf(输入整数的个数：); scanf(%d,&N); A=(int *)malloc(N*sizeof(int); /用数组给数据动态分配空间 printf(自行输入数据请按1，随机产生数据请按2n); scanf(%d,&judge); if(judge=1) /自行输入数据 printf(输入%d个整数：,N); for(i=0;iN;i+) scanf(%d,&Ai); else printf(随机产生的%d个整数为:n,N); /用随机种子随机产生N个0-999的整数 srand(time(0); for (i=0;iN;i+) if(rand()%2=0) /利用随机数奇偶性的等概率使得正负数约各占一半 Ai=rand()%1000; else Ai=(-1)*rand()%1000; printf(%dt,Ai); QueryPerformanceCounter(&begin);/记录算法1开始时间 MaxSum=MaxSubsequenceSum(A,N); QueryPerformanceCounter(&end); /记录算法1终止时间 printf(n最大子段和为：%dn,MaxSum); printf(算法1运行时间为:%f secondsn,(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart);/终止时间-开始时间=算法1运行时间 system(pause); int MaxSubsequenceSum(int A,int N) int ThisSum,MaxSum=0,i,j,k; /对最大值初始化 for(i=0;iN;i+) /从Ai开始 for(j=i;jN;j+) /以Aj结束 ThisSum=0; for(k=i;kMaxSum) MaxSum=ThisSum; /更新最大值 return MaxSum;算法2源代码：/*Given (possibly negative) integers A1, A2, , AN, find the maximum value. 找最大子段和*/#include#include #include int MaxSubsequenceSum(int A,int N);main() int i,N,*A,MaxSum,judge; LARGE_INTEGER begin,end,frequency; /代表64位有符号整数，记录程序运行时间 QueryPerformanceFrequency(&frequency);/可以获得当前的处理器的频率 printf(输入整数的个数：); scanf(%d,&N); A=(int *)malloc(N*sizeof(int); /用数组给数据动态分配空间 printf(自行输入数据请按1，随机产生数据请按2n); scanf(%d,&judge); if(judge=1) /自行输入数据 printf(输入%d个整数：,N); for(i=0;iN;i+) scanf(%d,&Ai); else printf(随机产生的%d个整数为:n,N); /用随机种子随机产生N个0-999的整数 srand(time(0); for (i=0;iN;i+) if(rand()%2=0) /利用随机数奇偶性的等概率使得正负数约各占一半 Ai=rand()%1000; else Ai=(-1)*rand()%1000; printf(%dt,Ai); QueryPerformanceCounter(&begin); /记录算法2开始时间 MaxSum=MaxSubsequenceSum(A,N); QueryPerformanceCounter(&end); /记录算法2终止时间 printf(n最大子段和为：%dn,MaxSum); printf(算法2运行时间为:%f secondsn,(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart); /终止时间-开始时间=算法2运行时间 system(pause); int MaxSubsequenceSum(int A,int N) int ThisSum,MaxSum=0,i,j; /对最大值初始化 for(i=0;iN;i+) /从Ai开始 ThisSum=0; for(j=i;jMaxSum) MaxSum=ThisSum; /更新最大值 return MaxSum;算法三源代码：分治法/*Given (possibly negative) integers A1, A2, , AN, find the maximum value. 找最大子段和*/#include#include #include int Divide_Conquer(int a,int left,int right);main() int i,N,*A,MaxSum,judge; LARGE_INTEGER begin,end,frequency; /代表64位有符号整数，记录程序运行时间 QueryPerformanceFrequency(&frequency);/可以获得当前的处理器的频率 printf(输入整数的个数：); scanf(%d,&N); A=(int *)malloc(N*sizeof(int); /用数组给数据动态分配空间 printf(自行输入数据请按1，随机产生数据请按2n); scanf(%d,&judge); if(judge=1) /自行输入数据 printf(输入%d个整数：,N); for(i=0;iN;i+) scanf(%d,&Ai); else printf(随机产生的%d个整数为:n,N); /用随机种子随机产生N个0-999的整数 srand(time(0); for (i=0;i0)sum=aleft;elsesum=0;elsecenter=(left+right)/2; /将数据一分为2 leftsum=Divide_Conquer(a,left,center); /递归求左边区间的数据的最大子段 rightsum=Divide_Conquer(a,center+1,right); /递归求右边区间的数据的最大子段 int s1=0,lefts=0;for(i=center;i=left;i-) / 求左边区间的数据的最大子段lefts+=ai;if(lefts=s1) s1=lefts; int s2=0,rights=0;for(i=center+1;i=s2) s2=rights; sum=s1+s2; if(sumleftsum) /最大值更新 sum=leftsum;if(sumrightsum) sum=rightsum;return sum;算法四源代码：On-line Algorithm/*Given (possibly negative) integers A1, A2, , AN, find the maximum value. 找最大子段和*/#include#include #include int MaxSubsequenceSum(int A,int N);main() int i,N,*A,MaxSum,judge; LARGE_INTEGER begin,end,frequency; /代表64位有符号整数，记录程序运行时间 QueryPerformanceFrequency(&frequency);/可以获得当前的处理器的频率 printf(输入整数的个数：); scanf(%d,&N); A=(int *)malloc(N*sizeof(int); /用数组给数据动态分配空间 printf(自行输入数据请按1，随机产生数据请按2n); scanf(%d,&judge); if(judge=1) /自行输入数据 printf(输入%d个整数：,N); for(i=0;iN;i+) scanf(%d,&Ai); else printf(随机产生的%d个整数为:n,N); /用随机种子随机产生N个0-999的整数 srand(time(0); for (i=0;iN;i+) if(rand()%2=0) /利用随机数奇偶性的等概率使得正负数约各占一半 Ai=rand()%1000; else Ai=(-1)*rand()%1000; printf(%dt,Ai); QueryPerformanceCounter(&begin); /记录算法4开始时间 MaxSum=MaxSubsequenceSum(A,N); QueryPerformanceCounter(&end); /记录算法4终止时间 printf(n最大子段和为：%dn,MaxSum); printf(算法4运行时间为:%f secondsn,(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart);/终止时间-开始时间=算法1运行时间 system(pause); int MaxSubsequen