2

プログラムの要点は、ブルートフォース法（機能している！）と分割統治法（機能していない）の両方を使用して、株価が変動する1次元配列の最大サブ配列を見つけることです。プログラムの目的は、一連の日数（したがって、構造体のlsubとrsub）とそれらの日の最大利益を見つけることです。

このパワーポイントのように私がオンラインで見たところはどこでも、私のコードが機能するはずであることを示しています。私もこれに似たものを見ましたが、StackOverflowのJavaでは、そのコードの実装も機能しません。これがそのJavaプログラムへのリンクです。

私のコードは次のとおりです。

#include <stdio.h>
#include <iostream>
#include <climits>
#include <cstring>

struct funOut{
int lsub; //Left subscript
int rsub; //Right subscript
int maximum; //Contains the max value
 //This way, max has the absolute smallest value and only needs to be done once rather than at the beginning of the algorithm calls.
};

void load(int arr[], int n);
void brute(int arr[],  int n, funOut &out);
funOut dac(int arr[], int low, int high, funOut &out);
void findMax(int sumLval, int sumRval, funOut &sumMval, int low, int mid, int high, funOut &out);
funOut crossSum(int arr[], int low, int mid, int high);
void print(funOut out);

using namespace std;


int main(void)
{
   funOut out;

   string alg;
   cin >> alg;

   int n;
   cin >> n;

   int arr[n];

   // cout << n << endl;

   load(arr, n);
   if(alg[0] == 'b')
      brute(arr, n, out); //PARAMETERS NEEDED
   else if(alg[0] == 'd')
   {
      out.maximum = 0;
      out = dac(arr, 1, n-1, out);
   }

   else
   {
      cout << "\nERROR: No algorithm chosen, aborting program." << endl;
      return 0;
   }

   cout << "Before Print" << endl;
   print(out);
   return 0;
}

void load(int arr[], int n)
{
   cout << "Loading" << endl;
   for(int i=0; i<n; i++)
      cin >> arr[i];
}

void brute(int arr[], int n, funOut &out) //THIS WORKS!!!
{
   out.maximum = 0;
   int change;
   int temp = 0;
   for(int i=1; i<n-1; i++)
   {
      for(int j=i; j<n; j++)
      {
         change = arr[j] - arr[j-1];
         temp += change;
         if(temp > out.maximum){
            out.lsub = i;
            out.rsub = j;
            out.maximum = temp;
         }     
      }
      temp = 0;
   }
}

funOut dac(int arr[], int low, int high, funOut &out)
{
   cout << "DAC Start!" << endl;
   if(low == high)
   {
      out.lsub = out.rsub = low;
      out.maximum = arr[low];
      return out;
   }
   else
   {
      // cout << "DAC IF" << endl;
      int mid = (low + high)/2;

      funOut sumLval = dac(arr, low, mid, out);
      funOut sumRval = dac(arr, mid+1,high, out);
      funOut sumMval = crossSum(arr, low, mid, high);

      cout << "\nsumLval = " << sumLval.maximum << endl; 
      cout << "\nsumRval = " << sumRval.maximum << endl;
      cout << "\nsumMval = " << sumMval.maximum << endl;
      //FindMax
      if(sumLval.maximum >= sumRval.maximum && sumLval.maximum >= sumMval.maximum)
         return sumLval;         
      else if(sumRval.maximum >= sumLval.maximum && sumRval.maximum >= sumMval.maximum)
         return sumRval;
      else
         return sumMval;
   }
}



funOut crossSum(int arr[], int low, int mid, int high)
{
funOut sumMval;
int lsum = 0;
int rsum = 0;
int sum = 0;
int maxl, maxr;
//For loop finding lsum
for(int i=mid; i>=low; i--)
{
   cout << "DAC For I = " << i << endl;
   sum += arr[i];
   if(sum > lsum)
   {
      lsum = sum;
      maxl = i;
   }
}

sum = 0;

for(int j=mid+1; j<=high; j++)
{
   cout << "DAC For J = "<< j << endl;
   sum += arr[j];
   if(sum > rsum)
   {
      rsum = sum;
      maxr = j;
   }
}

sumMval.lsub = maxl;
sumMval.rsub = maxr;
sumMval.maximum = lsum + rsum;

return sumMval;
}

void print(funOut out)
{
   cout << "The max value is: ";
   cout << out.maximum << endl;
   cout << "The left subscript is: ";
   cout << out.lsub << endl;
   cout << "The right subscript is: ";
   cout << out.rsub << endl;
}

サンプルデータセット:(それらは別々の行にあるはずですが、それは私にそうさせません。）

d
17
100
113
110
85
105
102
86
63
81
101
94
106
101
79
94
90
97

意図した出力は次のとおりです。

最大値は次のとおりです：43

左の添え字は次のとおりです：8

右の添え字は次のとおりです。11

4

1 に答える 1

0

概念的には、ブルートフォース方式は非常に多くの冗長な作業を行っています。

配列内のすべてのポイントツーポイントの違いを合計すると、両端の違いだけが得られます。

int diff = (x[1] - x[0]) + (x[2] - x[1]) + (x[3] - x[2]) + (x[4] - x[3]);

上記はこれと同じです（他のすべての値がキャンセルされるため）：

int diff = x[4] - x[0];

したがって、ブルートフォースアルゴリズムが実行しているように見えるのは、を検索することだけiでありj、最大の違いは。によって制約されi < jます。これは、配列の最小値と最大値を見つけることと同じです。ここで、最小値は最大値の前に表示されます。

動的計画法の問題のように私には見えます。分割統治法がこの問題にどのように役立つかわかりません。

[編集]

だから、問題はだと思いますcrossSum。とはまったく違うことをしていbruteます。minl確かに、左側の最小値のインデックス（）と右側の最大値のインデックス（）を見つけたいだけですmaxr。その出力構造体の「最大」は単純にarr[maxr] - arr[minl]です。

面白いことに、分割統治法はこの問題に対して不必要に非効率的です。このことを考慮：

struct funOut f;
f.lsub = 0;
f.rsub = 0;
f.maximum = 0;

int minval = arr[0];
int minidx = 0;

for( int i = 1; i < n; i++ ) {
    if( arr[i] < minval ) {
        minval = arr[i];
        minidx = i;
        continue;
    }

    int delta = arr[i] - minval;
    if( delta > f.maximum ) {
        f.lsub = minidx;
        f.rsub = i;
        f.maximum = delta;
    }
}
于 2012-09-16T23:21:49.650 に答える