среда, 8 марта 2017 г.

Произведение n чисел массива на JavaScript

Задача 1.1. У вас есть массив целых чисел, найдите наибольшее произведение из трёх чисел данного массива.
Решение.

var unsortedArray = [-10, 7, 29, 30, 5, -10, -70];
 
computeProduct(unsortedArray); // 21000
 
function sortIntegers(a, b) {
  return a - b;
}
 
// Наибольшее прозиведение - это (min1 * min2 * max1 || max1 * max2 * max3)
function computeProduct(unsorted) {
  var sortedArray = unsorted.sort(sortIntegers),
    product1 = 1,
    product2 = 1,
    array_n_element = sortedArray.length - 1;
 
  // Получаем произведение трёх наибольших элементов уже отсортированного массива
  for (var x = array_n_element; x > array_n_element - 3; x--) {
      product1 = product1 * sortedArray[x];
  }
 
  product2 = sortedArray[0] * sortedArray[1] * sortedArray[array_n_element];
 
  if (product1 > product2) return product1;
 
  return product2;
}
Возникла идея, чтобы скрипт находил произведение из произвольного количества чисел данного массива.
Решение.
// Массив из 21 элемента.
var unsortedArray = [-10, 7, 29, 30, 5, -10, -70, -11, 8, 28, 31, 6, -11, -71, -13, 79, 99, 32, 55, -100, -170];

// Вывод массива по элементам.
function outArrayByElement(ar) {
    var i;
    for (i = 0; i < ar.length; i += 1) {
        document.writeln(ar[i] + '>br /<');
    }
}

// Основная функция. Подсчет минимального и максимального произведений заданного количества элементов массива.
function multiPulti(ar, m) {
    var n = ar.length - 1,
        keys = [],
        max, min,
        maxAr, minAr,
        tmp,
        flag;

    // Возвращает произведение элементов массива по переданному массиву индексов.
    // Если указано, что print равно true, выводит строку из вышеуказанных значений.
    function multi(_ar, print = false) {
        var _i, _m;
        if (print) { _m = '( '; } else { _m = 1; }
        for (_i = 0; _i < _ar.length; _i += 1) {
            if (print) {
                _m += ar[_ar[_i]] + ' ';
            } else {
                _m *= ar[_ar[_i]];
            }
        }
        if (print) { _m += ')' }
        return _m;
    };

    // Наполнение массива индексов начальными значениями.
    // Анонимная функция для ограничения области видимости переменных.
    (function () {
        var _i;
        for (_i = 0; _i < m; _i += 1) {
            keys.push(_i);
        }
    })();

    max = min = multi(keys);

    // Сердце основной функции.
    // Вычисление произведения m элементов n-мерного массива.
    // Вывод минимального и максимального вышеуказанных произведений.
    (function () {
        var _j, _k;
        do {
            for (_j = m - 1; _j >= 0; _j -= 1) {
                flag = false;
                if (keys[_j] < n - m + 1 +_j) {
                    keys[_j] += 1;
                    for (_k = _j + 1; _k < m; _k += 1) {
                        keys[_k] = keys[_k - 1] + 1;
                    }
                    flag = true;
                    _j = -1;
                }
            }
            tmp = multi(keys);
            //document.writeln(multi(keys, true) + '>br /<');
            //outArrayByElement(keys);
            if (tmp > max) { max = tmp; maxAr = multi(keys, true); }
            if (min > tmp) { min = tmp; minAr = multi(keys, true); }
        } while (flag);
        document.writeln('min=' + min + ' ' + minAr + ', ' + 'max=' + max + ' ' + maxAr);
    })();
}
// Первый параетр - массив элементов.
// Второй параметр - количество элементов, произведене которых нужно найти.
multiPulti(unsortedArray, 7);
Некоторые результаты (для последовательностей из 2, 3, 5, 7 и 20 чисел):
min=-16830 ( 99 -170 ), max=17000 ( -100 -170 )
min=-1329570 ( 79 99 -170 ), max=1683000 ( 99 -100 -170 )
min=-9439947000 ( -71 79 99 -100 -170 ), max=8364510000 ( -70 -71 99 -100 -170 )
min=-16614306720000 ( -71 79 99 32 55 -100 -170 ), max=36343795950000 ( -70 -71 79 99 55 -100 -170 )
min=-4.641808736809999e+28 ( -10 7 29 30 -10 -70 -11 8 28 31 6 -11 -71 -13 79 99 32 55 -100 -170 ), max=2.3209043684049993e+28 ( -10 7 29 30 5 -70 -11 8 28 31 6 -11 -71 -13 79 99 32 55 -100 -170 )