Algorithmic Toolbox: максимизировать арифметическое выражение, используя скобки?Неудачный тестовый пример № 5/19 - PullRequest
Новая
       21

Algorithmic Toolbox: максимизировать арифметическое выражение, используя скобки?Неудачный тестовый пример № 5/19

0 голосов

Проблема была в шестой неделе курса алгоритмического инструментария на Coursera. Задача состоит в том, чтобы найти максимальное значение арифметического выражения, состоящего только из +, - и *.

Я написал решение, выполнил его с тестовыми примерами, а также провел стресс-тест с другими решениями, доступными в Интернете. Везде мой код, кажется, работает нормально. Но всякий раз, когда я пытаюсь представить, он проваливает 5-й контрольный пример. Сначала я подумал, что это происходит из-за переполнения значений в long long, поэтому представил решение с двойным типом данных. Тем не менее проблема остается.

Максимальные и минимальные функции 

long long maximum(long long a,long long b,long long c,long long d)
{
    int a1 = a>b?a:b;
    int a2 = c>d?c:d;
    return a1>a2?a1:a2;
}

long long minimum(long long a,long long b,long long c,long long d)
{
    int a1 = a<b?a:b;
    int a2 = c<d?c:d;
    return a1<a2?a1:a2;
}

Функция eval 

long long eval(long long a, long long b, char op) {
  if (op == '*') {
    return a * b;
  } else if (op == '+') {
    return a + b;
  } else if (op == '-') {
    return a - b;
  } else {
    assert(0);
  }
}

Алгоритм реализации 

long long get_maximum_value(char *str) {
  int len = strlen(str);
  int n = (len+1)/2,i,j,k;
  long long a,b,c,d,a1,b1;
  long long **max = (long long **)malloc(n*sizeof(long long*));
  long long **min = (long long **)malloc(n*sizeof(long long*));
  for(i=0;i<n;i++)
  {
      max[i] = (long long*)malloc(n*sizeof(long long));
      min[i] = (long long*)malloc(n*sizeof(long long));
  }
  for(i=0;i<n;i++){
    max[i][i] = str[i*2] - '0';
    min[i][i] = str[i*2] - '0';
  }
  for(i=1;i<n;i++)
    for(j=0;i+j<n;j++)
    {
        max[j][i+j] = LLONG_MIN;
        min[j][i+j] = LLONG_MAX;
        for(k=j;k<i+j;k++)
        {
            a = eval(max[j][k],max[k+1][i+j],str[2*k+1]);
            b = eval(max[j][k],min[k+1][i+j],str[2*k+1]);
            c = eval(min[j][k],max[k+1][i+j],str[2*k+1]);
            d = eval(min[j][k],min[k+1][i+j],str[2*k+1]);
            a1 = maximum(a,b,c,d);
            b1 = minimum(a,b,c,d);
            if(a1>max[j][i+j]) max[j][i+j] = a1;
            if(b1<min[j][i+j]) min[j][i+j] = b1;
        }
    }
  return max[0][n-1];
}

Кто-нибудь сталкивался с подобной проблемой? Пожалуйста, если возможно, предложите контрольный пример с кодом не удастся. Это будет очень полезно. Заранее спасибо.

1 Ответ

1 голос

У меня проблема.Это было целочисленное переполнение.Я фактически определил a1 и a2 как int внутри функции максимума и минимума. 

long long maximum(long long a,long long b,long long c,long long d)
{
    long long a1 = a>b?a:b;
    long long a2 = c>d?c:d;
    return a1>a2?a1:a2;
}

long long minimum(long long a,long long b,long long c,long long d)
{
    long long a1 = a<b?a:b;
    long long a2 = c<d?c:d;
    return a1<a2?a1:a2;
}

Изменение его в long long решило проблему.

...