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

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

2 голосов
/ 17 апреля 2019

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

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

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

1 Ответ

0 голосов
/ 17 апреля 2019

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

Наименьший 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²) это может сработать.

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

...