пятница, 30 апреля 2010 г.

Задача об удалении элемента массива с получением максимального произведения оставшихся элементов

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

Первым делом, конечно, представил нечто такое (привожу алгоритмические наброски):
1. Считаем произведение всех 
              элементов массива MultAll
2. В MultStart заносим минимально 
   возможное целов число
2. Для каждого элемента массива Arr - ArrElem
       1. если MultAll / ArrElem > MultStart, 
          то запонимаем индекс текущего 
             элемента в переменной Idx и
             в MultStart заносим новое 
             значение MultAll / ArrElem
4. Возвращаем индекс Idx

Но тут возникают сразу две сложности: в массиве могут быть элементы, равные 0, а значит, нужно как-то корректно обрабатывать эти случаи, исключая деление на 0, и второе - более важное - возможна ситуация, когда по причине переполнения значение произведения элементов будет элементарно не укладываться в предназначенную для него
переменную. Таким образом, нужно искать другой подход к решению задачи.
Начнем с того, что посчитаем кол-во положительных, отрицательных и нулевых элементов массива. Обозначим их, соответственно, pCnt, nCnt и zCnt.
Если кол-во нулевых элементов больше 1, то какой бы элемент мы из массива не выбросили, мы получим произведение, равное 0. То есть, из массива можно безболезненно удалить любой элемент массива.
Далее. Если нулевой элемент всего один, то тут возможны 2 варианта: если кол-во отрицательных элементов является нечетным, мы не должны удалять нулевой элемент, так как в этом случае результирующее произведение будет отрицательным числом. Что меньше, чем если бы мы удалили любой элемент, кроме нулевого (в этом случае произведение будет равно 0). Если же кол-во отрицательных элементов четно, то удалять нужно именно нулевой элемент, так как в этом случае произведение станет положительным, что больше 0, получаемого во всех остальных случаях.
Ну и последний случай, когда в нашем исходном массиве полностью отсутствуют нулевые элементы. Если у нас кол-во отрицательных элементов является нечетным, то есть, произведение отрицательно, мы должны удалять отрицательный элемент, имеющий минимальное значение по модулю. Это приведет к тому, что произведение станет положительным, а его величина будет максимальна среди всех возможных. Если же кол-во отрицательных элементов является четным, и произведение - положительное число, то удалять мы должны положительный элемент, имеющий минимальное значение. А если положительных элементов нет, то удалить следует отрицательный элемент, модуль которого является максимальным (в этом случае мы получим максимально возможное отрицательное число в качестве результирующего произведения).
То есть, если не брать в расчет граничные случаи (а при решении практических задач это нужно делать обязательно), общий алгоритм действий представляется следующим:
1. Подсчитываем кол-во положительных (pCnt), 
              отрицательных (nCnt) и нулевых (zCnt)
   элементов.
2. Если zCnt > 1, возвращаем индекс любого 
   элемента массива
3. Если zCnt = 1, то 
   1. Если nCnt - нечетное число, возвращаем индекс 
      любого элемента массива, кроме нулевого
   2. иначе - возвращаем индекс нулевого элемента
4. Если zCnt = 0 (нулевые элементы отсутствуют)
   1. Если nCnt - нечетное число, возвращаем 
      индекс отрицательного элемента, 
      имеющего самое малое абсолютное значение
   2. Иначе 
      1. Если pCnt > 0,  возвращаем индекс самого 
         малого положительного элемента
      2. Иначе, возвращаем индекс самого малого 
         отрицательного элемента 
Будем надеяться, что я нигде не ошибся в логических умозаключениях :) А если же вы обнаружили какие-то несоответствия логике, пишите в комментариях - с удовольствием пообщаемся с вами.

Комментариев нет:

Отправить комментарий