C說話求向量和的兩則成績解答分享

C說話求向量和的兩則成績解答分享。本站提示廣大學習愛好者：（C說話求向量和的兩則成績解答分享）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話求向量和的兩則成績解答分享正文

求一個向量的任何持續子向量的最年夜和

好比向量(31,-41,59,26,-53,58,97,-93,-23,84);
最年夜和是從59到97即為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;
} 

求一個向量的任何持續最接近0的子向量的和

好比向量(31,-41,59,26,-53,58,97,-93,-23,84);
最年夜和是從97到-93即為4

#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;
}

 運轉成果：