2

Есть массив A - размерностью N. Есть массив B - размерностью N-1; Массив А отвечает за числа в арифметическом выражении, а B - за действие.

Например A = { 1 , 2 , 3 } , B = { 0 , 2 }. Это является представлением выражения "1-2*3". ( 0 - минус, 1 - плюс, 2 - умножить ). Необходимо написать функцию, которая будет вычислять значение этого выражения. Также нужно учесть приоритет вычислений (из-за умножения). Мой вариант кода:

double result(vector<double> &a, vector<int> &b)
{
    double last = a[0];
    double res = 0;
    for (int i = 0; i < b.size(); i++)
    {
        if (b[i] == 2)
        {
            last *= a[i + 1];
        }
        if (b[i] == 0)
        {
            res+=last;
            last = -a[i + 1];
        }
        if (b[i] == 1)
        {
            res +=  last;
            last = a[i + 1];
        }
    }
    res += last;
    return res;
}

При возможности необходимо улучшить его как можно сильней. Я понимаю, что он и так в принципе работает за линейное время и асимптотически его особо не улучшишь. Может есть какие-то рекомендации насчет хранения данных, что выльется в более быстрое решение? Единственное требование: чтоб было разделение между числами и операциями.

Вообще полная задача выглядит немного иначе. Массив A - не меняется во время работы, а в функцию передаются различные варианты массива B. Основное время решения полной задачи занимает эта функция. Возможно, есть какой-то вариант 'запоминания' уже каких-то вычисленных шагов, и при небольшом отличии B и B' вычислить только ту часть, которая отличается.

8
  • тебе нужно i < b.size() -1 в цикле. так как ты берешь a[i + 1]. 13 сен 2017 в 20:27
  • @Senior Pomidor размер массива A - n, массива B - n-1, так что все верно
    – 9Pasha
    13 сен 2017 в 20:29
  • Лучше всего ознакомьтесь с общим алгоритмом вычисления выражений, который использует 2 стека -- один для операций, другой для операндов (и промежуточных результатов). Потом можете оптимизировать его под условия своей задачи. Похоже, вам под операнды и промежуточный результат будет нужен стек максимум из 3-х элементов, а откладывать "на будущее" нужно только одну операцию (сложение и вычитание).
    – avp
    13 сен 2017 в 20:29
  • @Harry, неправда, работает. Вы пробовали тестировать или почему вы так говорите?
    – 9Pasha
    14 сен 2017 в 11:32
  • Снимаю свое возражение.
    – Harry
    14 сен 2017 в 12:01

1 ответ 1

0

Если размерности массивов невелики (b.size() < 16), а массив A - фиксированный, то можно:

  1. Создать функцию вычисления дескриптора из флагов умножения d = ∧(i) ( bi >> 1) << i).
  2. Создать двумерный массив ATABd,i, в котором для каждого значения дескриптора d последовательности множителей массива a заменены их произведениями.
  3. Для каждого нового массива B вычислять дескриптор d и вместо массива A использовать ATABd, а операции умножения игнорировать.

Такой подход полностью снимает вопрос о старшинстве операций.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.