Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Поиск наименьшего общего кратного на Python
Ранее мы рассматривали алгоритм вычисления НОД (наибольший общий делитель). Нам понадобиться этот материал, так что в начале почитайте статью о НОД.
НОК - наименьшее общее кратное. Другими словами, если у нас есть два числа a и b, то N будет называться НОК, если оно 1) делится и на a, и на b, 2) оно наименьшее из всех чисел, которые делятся и на a, и на b.
Простой алгоритм нахождения НОК, для 2 и более чисел
В начале рассмотрим общий и довольно "тупой" алгоритм поиска НОК для произвольного количества чисел. Будем исходить из довольно простых соображений: если НОК равно одному из чисел, то оно равно наибольшему из этих чисел. Следовательно можно действовать так:
1. Возьмём число i = 2.
2. Выберем наибольшее из чисел и проверим, делится ли это число на все остальные числа.
3. Если число делится, то НОК найдено и алгоритм закончен.
4. Если нет, то умножаем исходное максимальное число на i.
5. Увеличиваем i на 1.
6. Переходим к пункту 3.
Вот эта программа. Она, кстати, похожа на одну из программ статьи о НОД.
Связь НОК и НОД
Существует простая формула связывающая НОД и НОК двух чисел a и b
НОК = (a * b) / НОД
Прекрасная формула. Воспользуемся ей для написания поиска НОК для двух чисел.
Последовательный поиск НОК для двух и более чисел
Если вы получили НОК для двух чисел, то легко обобщить алгоритм на три и более числа. Суть алгоритма заключается в следующем. Пусть имеется три числа a, b, c. Тогда НОК трёх чисел равна НОК( (НОК a и b) и c). И этот алгоритм легко обобщить на произвольное количество целых чисел.
Пора заканчивать.
Пишите свои предложения и замечания и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.
