#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int maxIntervalSum_1(int array[],int len)//穷举法,三层循环
{
int max=0;
for(int i=0;i<len;i++)
{
for(int j=i;j<len;j++)
{
int sum=0;
for(int k=i;k<=j;k++)
{
sum+=array[k];
}
if(sum>max) max=sum;
}
}
return max;
}
int maxIntervalSum_2(int array[],int len)//改进穷举法,两层循环
{
int max=0;
for(int i=0;i<len;i++)
{
int sum=0;
for(int j=i;j<len;j++)
{
sum+=array[j];
}
if(sum>max) max=sum;
}
return max;
}
int maxIntervalSum_3(int array[],int begin,int end)//分治法
{
int mmax=0;
if(begin=end) return array[begin]>0?array[begin]:0;
int mid=begin+(end-begin)/2;
int lmax=maxIntervalSum_3(array,begin,mid);//左半区间最大值
int rmax=maxIntervalSum_3(array,mid+1,end);//右半区间最大值
//中间区间最大值
int sum=0;
int left_max=0;
for(int i=mid;i>=begin;i--)
{
sum+=array[i];
if(sum>left_max) left_max=sum;
}
sum=0;
int right_max=0;
for(int i=mid+1;i<=end;i++)
{
sum+=array[i];
if(sum>right_max) right_max=sum;
}
mmax=left_max+right_max;
int max=(lmax>rmax)?(lmax>mmax?lmax:mmax):(rmax>mmax?rmax:mmax);
return max;
}
int maxIntervalSum_4(int array[],int len)//动态规则
{
int max=0;
int sum=0;
for(int i=0;i<len;i++)
{
sum+=array[i];
if(sum<0) sum=0;
if(sum>max) max=sum;
}
return max;
}
int main(int argc,char* argv[])
{
char* f_name=argv[1];//文件名
int n=atoi(argv[2]);//字符串转整数
int repeat_time=atoi(argv[3]);//重复次数
//读取数据到数组
FILE *pf;
int* data=(int*)malloc(n*sizeof(int));
if((pf=fopen("C:\\text_datum.txt","r"))==NULL)
{
printf("Error\n");
system("PAUSE");
exit(1);
}
//读取文件内容到数列
for(long long int i=0;i<n;i++)
{
fscanf(pf,"%d\n",&data[i]);
}
fclose(pf);
clock_t c_start,c_end;
int maxValue=0;
c_start=clock();
for(int i=0;i<repeat_time;i++)
{
maxValue=maxIntervalSum_1(data,n);
}
c_end=clock();
double diff_t=difftime(c_end,c_start);
printf("算法1,时间复杂度0(n^3),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);
c_start=clock();
for(int i=0;i<repeat_time;i++)
{
maxValue=maxIntervalSum_2(data,n);
}
c_end=clock();
diff_t=difftime(c_end,c_start);
printf("算法2,时间复杂度0(n^2),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);
c_start=clock();
for(int i=0;i<repeat_time;i++){
maxValue=maxIntervalSum_3(data,0,n-1);
}
c_end=clock();
diff_t=difftime(c_end,c_start);
printf("算法3,时间复杂度0(nlogn),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);
c_start=clock();
for(int i=0;i<repeat_time;i++){
maxValue=maxIntervalSum_4(data,n);
}
c_end=clock();
diff_t=difftime(c_end,c_start);
printf("算法4,时间复杂度0(n),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);
return 0;
}
=换成==
你这么写不是要从命令行获取数据吗?
int n = 4; //字符串转整数
int repeat_time = 3;//重复次数
修改如下,供参考:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int maxIntervalSum_1(int array[],int len)//穷举法,三层循环
{
int max=0;
for(int i=0;i<len;i++)
{
for(int j=i;j<len;j++)
{
int sum=0;
for(int k=i;k<=j;k++)
{
sum+=array[k];
}
if(sum>max) max=sum;
}
}
return max;
}
int maxIntervalSum_2(int array[],int len)//改进穷举法,两层循环
{
int max=0;
for(int i=0;i<len;i++)
{
int sum=0;
for(int j=i;j<len;j++)
{
sum+=array[j];
}
if(sum>max) max=sum;
}
return max;
}
int maxIntervalSum_3(int array[],int begin,int end)//分治法
{
int mmax=0;
if(begin==end) //(begin=end) 修改
return array[begin]>0?array[begin]:0;
int mid=begin+(end-begin)/2;
int lmax=maxIntervalSum_3(array,begin,mid);//左半区间最大值
int rmax=maxIntervalSum_3(array,mid+1,end);//右半区间最大值
//中间区间最大值
int sum=0;
int left_max=0;
for(int i=mid;i>=begin;i--)
{
sum+=array[i];
if(sum>left_max) left_max=sum;
}
sum=0;
int right_max=0;
for(int i=mid+1;i<=end;i++)
{
sum+=array[i];
if(sum>right_max) right_max=sum;
}
mmax=left_max+right_max;
int max=(lmax>rmax)?(lmax>mmax?lmax:mmax):(rmax>mmax?rmax:mmax);
return max;
}
int maxIntervalSum_4(int array[],int len)//动态规则
{
int max=0;
int sum=0;
for(int i=0;i<len;i++)
{
sum+=array[i];
if(sum<0) sum=0;
if(sum>max) max=sum;
}
return max;
}
int main(int argc,char* argv[])
{
int n = 0,repeat_time = 3;//重复次数
FILE *pf;
if (argc >= 4){ //命令行模式
//char* f_name=argv[1];//文件名 字符串不能赋值,需拷贝
if((pf=fopen(argv[1],"r"))==NULL){
printf("Error\n");
system("PAUSE");
exit(1);
}
n = atoi(argv[2]); //字符串转整数
repeat_time = atoi(argv[3]);//重复次数
}
else{
if((pf=fopen("D:\\text_datum.txt","r"))==NULL){
printf("Error\n");
system("PAUSE");
exit(1);
}
int tmp;
while (1){
if (fscanf(pf,"%d",&tmp) != 1) break;
n++;
}
rewind(pf);
}
//printf("n=%d,repeat_time=%d\n",n,repeat_time);
//读取文件内容到数列
//读取数据到数组
int* data=(int*)malloc(n*sizeof(int));
for(int i=0;i<n;i++)
{
fscanf(pf,"%d\n",&data[i]);
}
fclose(pf);
clock_t c_start,c_end;
int maxValue=0;
c_start=clock();
for(int i=0;i<repeat_time;i++)
{
maxValue=maxIntervalSum_1(data,n);
}
c_end=clock();
double diff_t=difftime(c_end,c_start);
printf("算法1,时间复杂度0(n^3),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);
c_start=clock();
for(int i=0;i<repeat_time;i++)
{
maxValue=maxIntervalSum_2(data,n);
}
c_end=clock();
diff_t=difftime(c_end,c_start);
printf("算法2,时间复杂度0(n^2),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);
c_start=clock();
for(int i=0;i<repeat_time;i++){
maxValue=maxIntervalSum_3(data,0,n-1);
}
c_end=clock();
diff_t=difftime(c_end,c_start);
printf("算法3,时间复杂度0(nlogn),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);
c_start=clock();
for(int i=0;i<repeat_time;i++){
maxValue=maxIntervalSum_4(data,n);
}
c_end=clock();
diff_t=difftime(c_end,c_start);
printf("算法4,时间复杂度0(n),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);
return 0;
}
命令行模式,是模拟dos命令行的情况下运行,如下图,供参考: