Максимальный продукт C

ProgramBox

Максимальный продукт C

Post author:admin
Запись опубликована:7 марта, 2023
Post category:Вопросы по программированию

#c #algorithm #vector #max

#c #алгоритм #вектор #макс

Вопрос:

Мне дано несколько массивов как отрицательных, так и положительных чисел. Я должен найти максимальное произведение, полученное при умножении 2 соседних чисел в массиве. Это код, который я написал :

  #include <vector>
#include <iostream>
using namespace std; 
int adjacentElementsProduct(vector<int> inputArray) 
  {
      for(int i = 0; i < inputArray.size(); i  ) {
      if((inputArray[i] * inputArray[i 1])>(inputArray[i 1] * inputArray[i 2])) {
        std::cout << inputArray[i] * inputArray[i 1] << "n";
       }  else  if((inputArray[i 1] * inputArray[i 2])>(inputArray[i 2] * inputArray[i 3])) {
           std::cout << inputArray[i 1] * inputArray[i 2] << "n";
           } else if((inputArray[i 2] * inputArray[i 3])>(inputArray[i 3] * inputArray[i 4])) {
               std::cout << inputArray[i 2] * inputArray[i 3] << "n";
               } else if((inputArray[i 3] * inputArray[i 4])>(inputArray[i 4] * inputArray[i 5])) {
                   std::cout << inputArray[i 3] * inputArray[i 4] << "n";
                   } else {
           std::cout << "Unknow" << "n";
       } return 1;
      }
  }

int main() {
  adjacentElementsProduct({5, 8});
  adjacentElementsProduct({1,2,3});
  adjacentElementsProduct({1,5,10,9});
  adjacentElementsProduct({5,1,2,3,1,4});
  adjacentElementsProduct({4,12,3,1,5});
  adjacentElementsProduct({3,6,-2,-5,7,3});
  adjacentElementsProduct({9, 5, 10, 2, 24, -1, -48});
  adjacentElementsProduct({5, 6, -4, 2, 3, 2, -23});
  adjacentElementsProduct({-23, 4, -5, 99, -27, 329, -2, 7, -921});
  adjacentElementsProduct({1,0,1,0,1000});
  adjacentElementsProduct({1,2,3,0});
  return 1 ;
}

Вывод:

Код сравнивает только произведение inputArray[i] * inputArray[i 1] и inputArray[i 1] * inputArray[i 2], но я хочу найти максимальное произведение среди всех чисел в массиве.

1. Я не понял. Итак, вам нужно найти максимальное произведение смежных элементов или всех элементов?

2. Мне нужно найти максимальное произведение всех соседних элементов в массиве.

3. @PooryaKeshavarzi — Что, если бы в векторе было 1000 элементов? Я уверен, что вы не хотите писать 2000 строк кода.

4. Ваш код демонстрирует неопределенное поведение. Ваш цикл позволит i достичь inputArray.size()-1 , и в этот момент inputArray[i 1] доступ к массиву выходит за рамки. Вы написали цикл, так что используйте его. (Кроме того, пожалуйста, подумайте о более разумном отступе. Обычно an else получает тот же уровень отступа, что и соответствующий if .)

Ответ №1:

Вы хотите перебрать входной вектор и вычислить произведения смежных элементов. Затем вы хотите найти максимум этих продуктов. Вам не нужны все эти жестко [i 1], [i 2], [i 3], ... запрограммированные махинации, у вас уже есть что-то, что может получить все эти числа для вас — цикл for .

 int adjacentElementsProduct(vector<int> inputArray) 
{
      // Set initial max product to a very small number so that 
      // it is always replaced by our first product
      int maxProduct = std::numeric_limits<int>::min();
      for(int i = 0; 
            i < inputArray.size() - 1;  /* because we will be doing i   1 inside the loop */
            i  ) {
          // Calculate product of this and next element
          int product = inputArray[i] * inputArray[i   1];
          
          if (product > maxProduct) 
              maxProduct = product; // This product is the greatest so far,  
                                    // so keep it and get rid of the old max.
      }
      return maxProduct;
}

Чтобы объяснить, как это работает, давайте посмотрим на выполнение функции для примера ввода. Допустим, мы делаем adjacentElementsProduct({5,1,2,3,1,4});

maxProduct устанавливается на какое-то очень большое отрицательное число (скажем, -99999999)
inputArray.size() равно 6. inputArray.size() - 1 равно 5.
i = 0 . Есть 0 < 5 ? Да. Перейти внутрь цикла
1. product = inputArray[0] * inputArray[1] = 5
2. есть 5 > maxProduct (-99999999) ? Да. Набор maxProduct = 5
3. Увеличить i до 1.
i = 1 . Есть 1 < 5 ? Да. Перейти внутрь цикла
1. product = inputArray[1] * inputArray[2] = 2
2. есть 2 > maxProduct (5) ? Нет.
3. Увеличить i до 2.
i = 2 . Есть 2 < 5 ? Да. Перейти внутрь цикла
1. product = inputArray[2] * inputArray[3] = 6
2. есть 6 > maxProduct (5) ? Да. Набор maxProduct = 6
3. Увеличить i до 3.
i = 3 . Есть 3 < 5 ? Да. Перейти внутрь цикла
1. product = inputArray[3] * inputArray[4] = 3
2. есть 3 > maxProduct (6) ? Нет.
3. Увеличить i до 4.
i = 4 . Есть 4 < 5 ? Да. Перейти внутрь цикла
1. product = inputArray[4] * inputArray[5] = 4
2. есть 4 > maxProduct (6) ? Нет.
3. Увеличьте i до 5.
i = 5 . Есть 5 < 5 ? Нет.
Возвращает maxProduct значение, равное 6.

1. int maxProduct = -9999999; — int maxProduct = std::numeric_limits<int>::min();

2. @PaulMcKenzie спасибо! -999999 был заполнителем, пока я не просмотрел документы для того, что numeric_limits было вызвано!

3. Привет. Спасибо. Можете ли вы объяснить свою часть if?

4. if (product > maxProduct) вводится только в том случае, если произведение двух текущих элементов больше максимального произведения, с которым мы сталкивались до сих пор, т.Е. Текущее произведение является новым максимумом , поэтому мы записываем его значение в maxProduct переменную @PooryaKeshavarzi

5. @NathanPierson Я просто использую цикл, который уже был в вопросе OP. Я подумал, что добавление дополнительных элементов к ответу излишне запутает OP.

Ответ №2:

Я думаю, что ваша функция излишня. Вы можете сделать это с помощью запущенных максимумов:

 const unsigned int length = inputArray.length();
int maximum = inputArray[0] * inputArray[1];
for (unsigned int i = 1U; i < (length - 1U);   i)
{
    const int product = inputArray[i] * inputArray[i   1];
    if (product > maximum) maximum = product;
}

Это может быть дополнительно оптимизировано, но это упражнение для OP.

Редактировать 1: с помощью указателей
Это может быть более оптимальным, но только язык ассемблера скажет (или профилирование):

 const unsigned int length = inputArray.length();
int const * p_first = amp;inputArray[0];
int const * p_second = amp;inputArray[1];
int maximum = (*p_first  ) * (*p_second  );
for (unsigned int i = 1u; i < (length - 1);   i)
{
    int product = (*p_first  ) * (*p_second  );
    if (product > maximum) maximum = product;
}

В приведенном выше фрагменте кода два местоположения массива сохраняются в указателях. Указатели могут храниться в регистрах. Нет необходимости вычислять смещение внутри цикла каждый раз. Увеличение указателей — простая и быстрая операция. У некоторых процессоров есть инструкции, которые могут разыменовывать указатель и увеличивать его в одной инструкции. Некоторые компиляторы могут выполнять эту оптимизацию в зависимости от настройки оптимизации.

Редактирование 2: отслеживание предыдущего значения
Другая оптимизация заключается в сокращении обращений к памяти примерно наполовину за счет запоминания предыдущего значения в массиве:

 const unsigned int length = inputArray.length();
int previous = inputArray[0];
int next     = inputArray[1];
int maximum  = previous * next;
previous = next;
for (unsigned int i = 1u; i < length;   i)
{
    next = inputArray[i];
    const int product = previous * next;
    if (product > maximum) maximum = product;
    previous = next;
}

В приведенном выше фрагменте кода предыдущее значение массива запоминается в переменной. Это устраняет необходимость доступа к массиву для предыдущего значения; требуется только один доступ к массиву.

Компилятор может выполнять эту оптимизацию на более высоких уровнях оптимизации. Доказательство заключается в сравнении фрагментов переменных на языке ассемблера.

Ответ №3:

В нем есть алгоритм, <numeric> который делает это за вас:

 int adjacentElementsProduct(std::vector<int> const amp; inputArray) 
{
  // [[assert: inputArray.size > 1 ]]

  return std::inner_product(inputArray.begin(), inputArray.end() - 1,
                            inputArray.begin()   1, 
                            0, 
                            [](int i, int j) { return std::max(i, j); }, 
                            std::multiplies{});
}

который примерно настолько эффективен и удобочитаем, насколько это возможно.

1. Спасибо за помощь, но я намного новичок в программировании, поэтому я делаю это с помощью более простых вещей. В любом случае спасибо

2. @PooryaKeshavarzi Хорошо, это зависит от вас. ИМО, это решение легче понять, чем использовать необработанные циклы.

Ответ №4:

Для начала функция не должна выводить никаких сообщений. Именно вызывающий функцию будет решать, выводить сообщение или нет.

Функция должна возвращать итератор или пару итераторов, которые указывают на два соседних элемента с максимальным произведением.

Что касается вашей реализации функции, то она имеет неопределенное поведение, поскольку может обращаться к несуществующим элементам вектора.

Я могу предложить следующее определение функции, как показано в демонстрационной программе ниже.

 #include <iostream>
#include <utility>
#include <vector>
#include <iterator>

std::pair<std::vector<int>::const_iterator, std::vector<int>::const_iterator>
adjacentElementsProduct( const std::vector<int> amp;v )
{
    std::pair<std::vector<int>::const_iterator, std::vector<int>::const_iterator> 
    p = { std::begin( v ), std::end( v ) };

    if (not ( v.size() < 2 ))
    {
        p.second = std::next( std::begin( v ) );
        long long int max_product = static_cast<long long int>( *p.first ) * *p.second;

        for (auto prev = p.second, current = std::next( p.second );
            current != std::end( v );
            std::advance( prev, 1 ), std::advance( current, 1 ))
        {
            if (max_product < static_cast<long long int>( *prev ) * *current)
            {
                p = { prev, current };
            }
        }
    }

    return p;
}

int main()
{
    std::vector<int> v = { 5, 8 };
    auto p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { 1,2,3 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { 1,5,10,9 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { 5,1,2,3,1,4 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { 4,12,3,1,5 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { 3,6,-2,-5,7,3 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { 9, 5, 10, 2, 24, -1, -48 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { 5, 6, -4, 2, 3, 2, -23 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { -23, 4, -5, 99, -27, 329, -2, 7, -921 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { 1, 0, 1, 0, 1000 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';

    v = { 1,2,3,0 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( *p.first ) * *p.second << 'n';
}

Вывод программы

Если вы еще не знаете итераторы, то функция может быть определена следующим образом

 #include <iostream>
#include <utility>
#include <vector>

std::pair<std::vector<int>::size_type, std::vector<int>::size_type>
adjacentElementsProduct( const std::vector<int> amp;v )
{
    std::pair<std::vector<int>::size_type, std::vector<int>::size_type>
    p = { 0, v.size() };

    if (not ( v.size() < 2 ))
    {
        p.second = 1;
        long long int max_product = static_cast<long long int>( p.first ) * p.second;

        for (std::vector<int>::size_type i = 3; i < v.size(); i   )
        {
            if (max_product < static_cast<long long int>( v[i - 1] ) * v[i] )
            {
                p = { i - 1, i };
            }
        }
    }

    return p;
}

int main()
{
    std::vector<int> v = { 5, 8 };
    auto p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { 1,2,3 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { 1,5,10,9 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { 5,1,2,3,1,4 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { 4,12,3,1,5 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { 3,6,-2,-5,7,3 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { 9, 5, 10, 2, 24, -1, -48 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { 5, 6, -4, 2, 3, 2, -23 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { -23, 4, -5, 99, -27, 329, -2, 7, -921 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { 1, 0, 1, 0, 1000 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';

    v = { 1,2,3,0 };
    p = adjacentElementsProduct( v );
    std::cout << static_cast< long long int >( p.first ) * p.second << 'n';
}

1. Спасибо. Но я пока не понимаю код Ur, потому что я действительно новичок, но все равно спасибо, я только что сделал это сам

2. @PooryaKeshavarzi Смотрите мой обновленный пост. Что касается вашего решения, то я уверен, что это неправильно.:)