Максимальное произведение трёх чисел

22 Август 2019 - Время чтения: 22 минуты

Условие задачи: Дан массив вещественных чисел, размер не менее трёх элементов. Найти максимально возможное произведение любых трёх чисел в нём. Например, в массиве [1, 2, -4, 3] это 1 * 2 * 3 = 6, а в массиве [1, -2, -4, 3] это -2 * -4 * 3 = 24.

Все решения этой задачи, которые я видел, либо крайне неэффективны, либо содержат мешанину кода. Давайте сначала рассмотрим эти решения. Первое, что приходит в голову - тупой перебор, он же метод грубой силы. Пройдёмся по всем возможным тройкам чисел, вычисляя их произведение, и найдём максимум. Очевидно, сложность этого решения O(n3), и это ужасно, так что этот код я представляю только для того, чтобы показать, как не надо делать.


Исходный код на C99
#include <float.h>
#include <math.h>
#include <stdio.h>
 
#define MAX_SIZ 100
 
double arr[MAX_SIZ];
 
int main(void)
{
    size_t siz = 0;
    for (double x; siz < MAX_SIZ && scanf("%lf", &x) == 1;) {
        arr[siz++] = x;
    }
    double max3 = -DBL_MAX;
    for (size_t i = 2; i < siz; ++i) {
        for (size_t j = 1; j < i; ++j) {
            double prod2 = arr[i] * arr[j];
            for (size_t k = 0; k < j; ++k) {
                max3 = fmax(max3, prod2 * arr[k]);
            }
        }
    }
    printf("%f\n", max3);
    return 0;
}

Работает этот код так же плохо, как и выглядит. Как же сделать поумнее? Давайте подумаем, как вообще может получиться максимум в данной ситуации. Числа могут быть положительными и отрицательными. Допустим, все три положительные, тогда произведение положительно. Если же одно из них отрицательно, то произведение получится тоже отрицательным, и будет заведомо меньше. Если отрицательных чисел два, то минус на минус даёт плюс, и опять получается положительное число. Таким образом, наиболее выгодно умножать либо три положительных, либо одно положительное и два отрицательных. Причём отрицательные должны быть как можно меньше, тогда их произведение получится максимальным. Таким образом, нам надо найти три самых больших числа в массиве, и два самых маленьких.

Итак, нам нужно найти максимум из двух чисел:

  1. Произведение трёх самых больших чисел.
  2. Произведение двух самых маленьких и самого большого.

Как получить три максимума и два минимума? Напрашивается сортировка. Действительно, если отсортировать массив по возрастанию, то потом можно легко взять два первых элемента и три последних.


Исходный код на C99
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_SIZ 100
 
int cmp(const void *a, const void *b)
{
    double aa = *(double *)a;
    double bb = *(double *)b;
 
    return aa == bb ? 0 : aa < bb ? -1 : 1;
}
 
double arr[MAX_SIZ];
 
int main(void)
{
    size_t siz = 0;
    for (double x; siz < MAX_SIZ && scanf("%lf", &x) == 1;) {
        arr[siz++] = x;
    }
    qsort(arr, siz, sizeof(double), cmp);
    printf("%f\n", fmax(arr[0] * arr[1] * arr[siz - 1], arr[siz - 3] * arr[siz - 2] * arr[siz - 1]));
    return 0;
}

Ясно, что этот вариант тоже не лучший, потому что сложность сортировки O(n * log n). К тому же нам нужно всего пять элементов, а сортировать будем, может быть, пять тысяч. Или пять миллионов. Можно сделать за время O(n). Для этого обычно заводят пять переменных, которые хранят, соответственно, три максимума и два минимума, а потом пишут простыню кода с большим количеством вложенных условий. Это так скучно, что я даже не буду пытаться это делать. Получится код, который не столько сложный, сколько трудоёмкий, и ошибиться в нём легко. Я придумал другой способ.

Решение: Представим, что у нас есть массив из первых 6 элементов данного массива. Если мы отсортируем его, то очевидно, что мы получим три максимума, два минимума, и ещё определим "лишний" элемент. Теперь достаточно записать очередной элемент на место лишнего и опять отсортировать. Можно воспользоваться библиотечной функцией сортировки, но ведь очевидно, что если мы заменим один элемент в отсортированном массиве, то получим "почти отсортированный" массив. Гораздо лучше написать простую функцию сортировки, которая оптимизирована под эту ситуацию. Например, подойдёт гномья сортировка, которая является модификацией сортировки вставками. Ещё для оптимизации можно начинать сортировку не с первого элемента массива, а с того числа, которого только что было добавлено. Добавлять будем в позицию 2, если в массиве уже 6 элементов, или в очередную, пока не вырастет до 6.


Исходный код на C99
#include <math.h>
#include <stddef.h>
#include <stdio.h>
 
int main(void)
{
    double arr[6];
    size_t siz = 0;
    for (double x; scanf("%lf", &x) == 1;) {
        size_t i = siz == 6 ? 2 : siz++;
        arr[i] = x;
        while (i < siz) {
            if (i == 0 || arr[i - 1] <= arr[i]) {
                ++i;
            } else {
                double t = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = t;
                --i;
            }
        }
    }
    printf("%f\n", fmax(arr[0] * arr[1] * arr[siz - 1], arr[siz - 3] * arr[siz - 2] * arr[siz - 1]));
    return 0;
}

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

Currently there are no comments, so be the first!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории