Найдите пару с наименьшим значением LCM в заданном массиве

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

Я знаю, что есть наивное решение с двойным циклом O (n ^ 2), но, как и ожидалось, оно дало исключение с ограничением по времени. Я слышал, что динамическое программирование используется для оптимизации подходов грубой силы, но я не могу понять, как разделить эту проблему на подзадачи, чтобы была оптимальная подструктура.

Могу ли я получить какое-либо направление для решения этой проблемы с помощью DP? Или какой-нибудь лучший подход? Спасибо.


arrays algorithm data-structures dynamic-programming
person Mushi Master    schedule 17.04.2019    source источник
comment
может помочь предварительная обработка каждого числа для разложения простых чисел.   -  person Jarod42    schedule 17.04.2019
comment
с какой проблемой вы столкнулись?   -  person Syed Mehtab Hassan    schedule 17.04.2019
comment
Я думаю, что в общем случае (например, ни одно из чисел в массиве не имеет общих простых множителей) вы всегда получите O (n²), потому что вам придется вычислять произведение каждой комбинации и сравнивать их размеры. Единственная возможность улучшить вашу скорость может быть в особом случае (по общему признанию, вероятно, очень распространенном), когда элементы имеют много общих простых множителей.   -  person Alfe    schedule 17.04.2019
comment
@Alfe, если все числа взаимно просты, вы можете просто взять 2 наименьших числа O (n)   -  person maraca    schedule 17.04.2019
comment
@maraca Вы правы, если знаете, что все они взаимно просты. Если у вас есть это предположение, проверка его также просто O (n), но я предполагал нормальный случай, когда некоторые будут взаимно простыми, а некоторые нет, поэтому вам нужно придумать что-то, что может иметь дело с этим , и этот (неспециализированный) алгоритм будет иметь O(n²) в списке всех взаимно простых чисел.   -  person Alfe    schedule 17.04.2019

Ответы (1)


arrow_upward
0
arrow_downward

(Предположим, что числа положительные.)

Наименьший LCM, вероятно, будет получен из наименьших элементов, поэтому для сокращения пробных значений можно отсортировать массив.

int[] v = { ... };

int minLCM = Integer.MAX_VALUE;
int bestVi = -1;
int bestVj = -1;
Arrays.sort(v);
for (int i = 0; i < v.length; ++i) {
    int vi = v[i];
    //                                  _____________
    for (int j = i + 1; j < v.length && v[j] < minLCM; ++j) {
        int vj = v[j];
        int lcm = lcm(vi, vj);
        if (lcm < minLcm) {
            minLCM = lcm;
            bestVi = vi;
            bestVj = vj;
        }
    }
}

Для обрезки:

lcm(vi, vj) >= vi
lcm(vi, vj) >= vj
(lcm(vi, vj) <= vi*vj

Это сокращение может быть выполнено в цикле for-j только как vj >= vi.

Лучшее сокращение можно было бы сделать, если бы вместо числа у вас был список (не более ²log value) простых множителей. Поскольку факторизация тоже стоит, можно просто попробовать, например, (2, 3, 5, 7).

Улучшение цикла также может быть достигнуто заменой обоих вложенных циклов так, чтобы наименьший (vi, vj) был первым. Выше (v0, v100) предшествует (v1, v2). Цикл по возрастанию i+j.

i j
0 1
0 2
0 3
1 2
0 4
1 3
0 5
1 4
2 3
...

(Математика для счетчиков циклов с использованием диагоналей — хорошая головоломка. Это действительно нужно сделать.)

Хотя все еще O(n²) это может сработать.

Иногда также имеет значение язык программирования, и в этих контекстах часто можно увидеть вклад C. В таком случае использование Ruby может оказаться контрпродуктивным.

person Joop Eggen    schedule 17.04.2019