个人中心
gpt4 book ai didi

C语言求向量和的两则问题解答分享

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C语言求向量和的两则问题解答分享由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

求一个向量的任何连续子向量的最大和 。

比如向量(31,-41,59,26,-53,58,97,-93,-23,84); 最大和是从59到97即为187 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include<stdio.h>
#include<stdlib.h>
 
//两者的最大值
int max( int x, int y );
//三者的最大值
int max2( int x, int y, int z );
//最原始的算法，复杂度为T(n)=O(n*n)
int oringinal( int v[], int len );
//原始基础上变体版,复杂度为T(n)=O(n*n)
int oringinal_ex( int v[], int len );
//分治法,复杂度为T(n)=O(n*log(n))
/*
  *分治法的思想是：将原数组分成两部分，要求的最大值
  *要么在左边这部分里面，要么在右边这部分里面
  *要么就在左右相交的交界处
  */
int divAndCon( int v[], int low, int high );
//扫描法,复杂度为T(n)=O(n)
int scan( int v[], int len);
 
 
void main()
{
      int i = 0;
      int v[] = {31,-41,59,26,-53,58,97,-93,-23,84};
      int len = 0;
      int result;
      len = sizeof (v) / sizeof ( int );
      printf ( "oringinal datas:\n" );
      for ( i = 0; i < len; i++ )
      {
        printf ( "%d\t" ,v[i]);
      }
      printf ( "\n" );
      //最原始的算法
      result = oringinal(v,len);
      printf ( "oringinal(v,len):%d\n" ,result);
      //最原始变体的算法
      result = oringinal_ex(v,len);
      printf ( "oringinal_ex(v,len):%d\n" ,result);
      //分治法
      result = divAndCon(v,0,len-1);
      printf ( "divAndCon(v,0,len):%d\n" ,result);
      //扫描法
      result = scan(v,len);
      printf ( "scan(v,len):%d\n" ,result);
}
 
 
//两者的最大值
int max( int x, int y )
{
      if ( x < y )
      {
         x = y;
      }
      return x;
}
 
 
//三者的最大值
int max2( int x, int y, int z )
{
      if ( x < y )
      {
        x = y;
      }
      if ( x < z )
      {
        x = z;
      }
      return x;
}
 
 
 
//最原始的算法，复杂度为T(n)=O(n*n)
int oringinal( int v[], int len )
{
      int maxsofar = 0;
      int i;
      int j;
      int sum = 0;
      //通过双层循环逐步扫描，通过max( sum, maxsofar)获得当前最大值
      for ( i = 0; i < len; i++ )
      {
        sum = 0;
        for ( j = i; j < len; j++ )
        {
          sum += v[j];
          maxsofar = max( sum, maxsofar );
         }
      }
      return maxsofar;
}
 
 
//原始基础上变体版,复杂度为T(n)=O(n*n)
int oringinal_ex( int v[], int len )
{
      int i = 0;
      int j = 0;
      int sum = 0;
      int maxsofar = 0;
      int *cumarr = ( int * ) malloc ( len * sizeof ( int ) );
 
 
     for ( i = 0; i < len; i++ )
     {
        if ( i == 0 )
        {
          cumarr[0] = v[i];
        }
        else
        {
          cumarr[i] = cumarr[i-1] + v[i];
        }
 
      }
     for ( i = 0; i < len; i++ )
       for ( j = i; j < len; j++ )
       {
         if ( i == 0 )
         {
            sum = cumarr[i];
          }
          else
         {
            sum = cumarr[j] - cumarr[i-1];
          }
         maxsofar = max(maxsofar,sum);
       }
       return maxsofar;
 
}
 
 
 
//分治法,复杂度为T(n)=O(n*log(n))
int divAndCon( int v[], int low, int high )
{
     int mid = 0;
     int lmax = 0;
     int rmax = 0;
     int sum = 0;
     int i = 0;
 
     if ( low > high )
     {
       return 0;
     }
     if ( low == high )
     {
       return max(0,v[low]);
     }
     mid = ( low + high ) / 2;
     lmax = sum = 0;
     for ( i = mid; i >= low; i-- )
     {
        sum += v[i];
        lmax = max(lmax,sum);
     }
     rmax = sum = 0;
     for ( i = mid + 1; i <= high; i++ )
     {
       sum +=v[i];
       rmax = max(rmax,sum);
     }
     return max2(lmax + rmax,divAndCon(v,low,mid),divAndCon(v,mid+1,high));
 
}
 
 
//扫描法,复杂度为T(n)=O(n)
int scan( int v[], int len)
{
      int maxsofar = 0;
      int maxendinghere = 0;
      int i = 0;
      for ( i =0; i < len; i++ )
      {
        maxendinghere = max(maxendinghere + v[i],0);
        maxsofar = max(maxsofar,maxendinghere);
      }
      return maxsofar;
}

C语言求向量和的两则问题解答分享

  。

求一个向量的任何连续最接近0的子向量的和 。

比如向量(31,-41,59,26,-53,58,97,-93,-23,84); 最大和是从97到-93即为4 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<stdio.h>
#include<math.h>
 
//返回最接近0的数
int closeZero( int x, int y );
//最原始的算法，复杂度为T(n)=O(n*n)
int oringinal( int v[], int len );
 
void main()
{
      int i = 0;
      int v[] = {31,-41,59,26,-53,58,97,-93,-23,84};
      int len = 0;
      int result;
      len = sizeof (v) / sizeof ( int );
      printf ( "oringinal datas:\n" );
      for ( i = 0; i < len; i++ )
     {
       printf ( "%d\t" ,v[i]);
     }
     printf ( "\n" );
     //最原始的算法
     result = oringinal(v,len);
     printf ( "oringinal(v,len):%d\n" ,result);
 
}
 
 
//返回最接近0的数
int closeZero( int x, int y )
{
      if ( abs (x) > abs (y) )
      {
        x = y;
      }
      return x;
}
 
 
 
//最原始的算法，复杂度为T(n)=O(n*n)
int oringinal( int v[], int len )
{
      int sofar = v[0];
      int i;
      int j;
      int sum = 0;
 
      for ( i = 0; i < len; i++ )
      {
        sum = 0;
        for ( j = i; j < len; j++ )
        {
          sum += v[j];
          sofar = closeZero( sum, sofar );
        }
      }
      return sofar;
}

 运行结果:

C语言求向量和的两则问题解答分享

最后此篇关于C语言求向量和的两则问题解答分享的文章就讲到这里了,如果你想了解更多关于C语言求向量和的两则问题解答分享的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： Web 现代应用程序架构下的性能优化，渐进式的极致艺术
文章推荐： 五款PHP代码重构工具推荐
文章推荐： ThinkPHP 表单自动验证运用示例
文章推荐： Ubuntu 正在开发全新的安装程序
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com