Вычисление LCM из M последовательных чисел в массиве из N целых чисел - PullRequest
Новая
       34

Вычисление LCM из M последовательных чисел в массиве из N целых чисел

1 голос
/ 05 марта 2012

Я сталкивался с этой проблемой здесь .Это был конкурс по программированию, проведенный ранее в этом году.
Вот сводка:
Учитывая массив из N целых чисел, найдите LCM всех последовательных целых чисел M.
Например, 

Array = [3,5,6,4,8] (hence N = 5)  
M = 3

Вывод: 

LCM(3,5,6) = 30  
LCM(5,6,4) = 60  
LCM(6,4,8) = 24

На самом деле есть эскиз решения здесь , но я не мог понять Динамическое программирование Часть.
Так что, если кто-то мог бы уточнитьТо же решение с некоторыми примерами будет великолепным.
Будет также приветствоваться новое, простое для понимания решение.

1 Ответ

0 голосов
/ 31 июля 2012

Я больше не могу получить доступ к решению (может быть, ссылка не работает?), Но вот что я хотел бы сделать: моя программа работала бы как пирамида.В самой нижней строке у меня будет массив с заданными числами.В каждой строке выше у меня был бы массив с одним полем меньше, чем массив ниже.Он будет хранить LCM двух значений из массива ниже. 

[   30    ]
[ 15,  30 ]
[3,  5,  6]

Таким образом, вы можете работать с рекурсивной функцией, и вам придется строить слои M-1 пирамиды.Вот реализация псевдокода: 

rekursivePyramid (Integer[] numbers, Integer height) {
    if (height == 0) return numbers;
    else {
        newNumbers = Integer[numbers.size() - 1];
        for (i=0; i<newNumbers.size(); i++) {
            newNumbers[i] = LCM ( numbers[i], numbers[i+1]);
        }
        return rekursivePyramid( newNumbers, height-1);
    }
}

Это даст вам массив, где вы найдете LCM первых M чисел в первом поле, LCM от второго до M + 1-го числа ввторое поле и т. д.

...