2

Пусть, например, имеется массив a[0], a[1],..,a[6]. Необходимо реализовать алгоритм, который на вход принимает значение количества пар (параметр depth), а на выходе выдает сумму разности элементов в каждой паре. Чтобы было более понятно, рассмотрим то, что должен вернуть алгоритм для конкретного значения depth

depth: 1, 
return: 
       (a[6] - a[0]); /*единственный возможный случай для depth = 1*/

depth: 2, 
return: 
       (a[1] - a[0]) + (a[6] - a[2]);
       (a[2] - a[0]) + (a[6] - a[3]);
       (a[3] - a[0]) + (a[6] - a[4]);
       (a[4] - a[0]) + (a[6] - a[5]);

depth: 3,
return:
       (a[1] - a[0]) + (a[3] - a[2]) + (a[6] - a[4]);
       (a[1] - a[0]) + (a[4] - a[2]) + (a[6] - a[5]);
       (a[2] - a[0]) + (a[4] - a[3]) + (a[6] - a[5]);

Выше был приведен пример для массива размерности 7. Я хочу реализовать алгоритм для массива произвольной размерности.

На данный момент мне удалось реализовать этот алгоритм с помощью рекурсии. Ниже приведен код на C++ (Для примера взят массив длины 100)

int arr[101]; /*Исходный массив длины 100*/
set <__int64> Partitions; /*Множество для накопления суммы разности элементов пар*/

void get_partitions(int start, int end, int depth, int sum) {
    //start - индекс массива, с которого начинаем перебор вариантов
    //end - индекс последнего элемента массива
    //depth - текущее значение параметра количества пар
    //sum - накопленная разность

    //Если depth == 1, то получаем финальный sum и записываем в Partitions
    if (depth == 1) {
        sum += (arr[end] - arr[start]);

        Partitions.insert(sum);
    }
    else {
        int k = end - 2 * (depth - 1);
        int new_start = start + 1;

        while (new_start <= k) {
            int current_sum = (arr[new_start] - arr[new_start - 1]);

            //рекурсивный вызов
            get_partitions((new_start + 1), end, (depth - 1), (sum + current_sum));

            new_start++;
        }
    }
}

int main() {
    get_partitions(0, 100, 5, 0);

    //Обрабатываем множество Partitions

    return 0;
}

Данная реализация имеет одну серьезную проблему. Для массива большой размерности, время выполнения программы слишком долгое.

Можно ли улучшить этот алгоритм? Возможно эта задача уже известная. Есть ли другие способы реализовать данный алгоритм? Буду благодарен за ответы.

UPD: Массив a[0], a[1],..,a[N] разбивается на d пар:

(a[0], a[i_1]), (a[i_1 + 1], a[i_2]), (a[i_2 + 1], a[i_3]), ..., (a[i_{d-1}], a[N]),

где d - параметр depth. Индексы i_j должны удовлетворять условиям:

0 < i_1 < (i_1 + 1) < i_2 < (i_2 + 1) < i_3 < ... < i_{d-1} < N.

2
  • 3
    Поясните подробнее принцип, по которому вы генерируете пары. Например, почему при 1 нельзя рассмотреть a[4]-a[2], а при 2 - (a[5]-a[3]) + (a[4]-a[0])?
    – Harry
    4 июл 2017 в 11:11
  • 2
    Присоединяюсь к вопросу уважаемого @Harry.
    – BuilderC
    4 июл 2017 в 11:34

1 ответ 1

0

Первый, очевидный, недостаток предложенного алгоритма: одни и те же "хвосты" ты считаешь многократно. Если тебе везет со входными данными, и суммы распределены в небольшом диапазоне значений, то оптимальный алгоритм такой:

std::set< std::tuple< int, int, int, int > > Pased;

void get_partitions(int start, int end, int depth, int sum) {

    if(!Pased.insert(std::make_tuple(start, end, depth, sum)).second)
        return; // Для этого набора входных данных мы уже считали разбиение. Новых значений больше не будет.
    // далле твоя реализация get_partitions

Кроме того один и тот-же цикл обсчета "хвоста" ты вызываешь один и тот-же цикл для разных значений аргумента summ, этого тоже можно избежать, если функция get_partitions будет возвращать не окончательный результат (в глобальной переменной), а массив значений разбиений для соответствующего "хвоста" (список уникальных значений current_sum). Результат, вычислений такой функции можно кешировать, (не вызывать повторно, а возвращать ранее посчитанный результат).

Приведенные выше приемы оптимизации относятся к "Динамическому программированию". см. https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5

Кроме того, возможно, смена способа хранения множеств (с set на unodred_set, flat_set, ...) даст существенное ускорение.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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