Как найти нок двух чисел алгоритм

Что такое нок в математике? Продолжим разговор о наименьшем общем кратном, который мы начали в разделе « НОК – наименьшее общее кратное, определение, примеры». В этой теме мы узнаем, как найти наименьшее общее кратное, какие есть для этого способы для трех чисел и более, разберем вопрос о том, как находить НОК отрицательного числа. Также разберемся, что такое нок и нод, как найти нок и нод. 

Вычисление наименьшего общего кратного (НОК) через НОД

Мы уже узнали, что такое нок, а также установили связь наименьшего общего кратного с наибольшим общим делителем (кратность показывает в расчетах во сколько раз один показатель больше другого). Теперь как настоящие математики научимся определять НОК через НОД (нок и нод чисел натуральных). Сначала разберемся, как найти нок для положительных чисел. Сделать это можно и онлайн или на калькуляторе, но лучше научиться самостоятельно.

Поиск наименьшего общего кратного через наибольший общий делитель можно по формуле НОК(a, b)=a·b:НОД(a, b).

В этом примере мы использовали правило нахождения наименьшего общего кратного для целых положительных чисел a и b: если первое число делится на второе, что НОК этих чисел будет равно первому числу.

Нахождение НОК с помощью разложения чисел на простые множители

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

Этот способ нахождения наименьшего общего кратного основан на равенстве НОК(a, b)=a·b:НОД(a, b). Если посмотреть на формулу, то станет понятно: произведение чисел a и b равно произведению всех множителей, которые участвуют в разложении этих двух чисел. При этом НОД двух чисел равен произведению всех простых множителей, которые одновременно присутствуют в разложениях на множители данных двух чисел.

Дадим еще одну формулировку метода нахождения НОК путем разложения чисел на простые множители.

Вернемся к числам 75 и 210, для которых мы уже пробовали искать НОК в одном из прошлых примеров. Разложим их на простые множители: 75=3·5·5 и 210=2·3·5·7. К произведению множителей 3, 5 и 5 числа 75 добавим недостающие множители 2 и 7 числа 210. Получаем: 2·3·5·5·7. Это и есть НОК чисел 75 и 210.

Нахождение НОК трех и большего количества чисел

Независимо от того, с каким количеством чисел мы имеем дело, алгоритм наших действий всегда будет одинаковым: мы будем последовательно находить НОК двух чисел. На этот случай есть теорема.

Предположим, что у нас есть целые числа a1, a2, …, ak. НОК mk этих чисел находится при последовательном вычислении m2=НОК(a1, a2), m3=НОК(m2, a3), …, mk=НОК(mk−1, ak).

Теперь рассмотрим, как можно применять теорему для решения конкретных задач.

Как видите, вычисления получаются несложными, но достаточно трудоемкими. Чтобы сэкономить время, можно пойти другим путем.

Нахождение наименьшего общего кратного отрицательных чисел

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

НОК(54, −34)=НОК(54, 34), а НОК(−622, −46, −54, −888)=НОК(622, 46, 54, 888).

Такие действия допустимы в связи с тем, что если принять, что a и −a – противоположные числа,
то  множество кратных числа a совпадает со множеством кратных числа −a.

Была ли эта статья полезной?

Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления.

Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3. А далее находим НОК (наименьшее) общее кратное). Которое будет равно 30.

Для небольших чисел это легко вычисляется в уме. Но вот с пятиначными числами, так легко не получится. Поэтому предлагаю обратиться к алгоритму Евклида. Математические выкладки и детали в данной статье затрагивать не буду, хотя там много есть интересного.

Но суть достаточно простая. Их двух чисел выбираем большее и аычитаем из него меньшее. Далее выбираем снова большое и вычитаем из него снова, до тех пор пока разница не будет равна одному из чисел. Это и будет искомое число. Предлагаю проверить сперва на очевидных примерха.

Мы с вами уже находили НОД для 6 и 15. И у нас также получилось 3.

Теперь возьмём числа побольше. Я конечно могу сказать, что беру случайные числа, но по факту могы их проверить.

Пусть будут числа 195 и 1450. Очевидно, что они точно деляться на 5, но я предлагаю проверить.

И действительно 195 = 3*5*13, а 1450 = 2*5*5*29.

А теперь рассмотрим как найти НОК (наименьшее общее кратное). Рассмотрим сперва на простом примере. Числа 15 и 6.

Есть такая замечательная формула НОК = (A*B) / НОД.

Теперь проверим это выражение. НОК = (15*6)/3=30.

Оказывается, что всё достаточно просто. Если рассмотреть числа 195 и 1450, то для них НОК будет 195*1450/5=56550 или 2*3*5*5*13*29.

То есть без калькулятора можно свободно найти НОД и НОК. Естественно что для программиста эта задача становится очень простой.

Для начала разберем алгоритм через блок-схему.

Подробнее можно увидеть на видео:

У меня всё, благодарю за внимание.

———————————————————————-

Делюсь другими материалами:

Сериал Дистанционка от коллег в А1: Дистанционка. Серия 1. Дистанционка. Серия 2. Дистанционка. Серия 3.

Материалы по Scratch.

Алгоритмы вычисления наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) описаны в одной теме, т.к. для эффективного вычисления НОК нужно вычислить НОД.

1 Алгоритм расчета наибольшего общего делителя

Даны два целых числа A и B, их наибольший общий делитель — такое число C, что на него делится без остатка и A, и B

В школе нас учили искать НОД разложением на простые множители, однако такая задача крайне тяжело решается на компьютере, зато мы можем заставить его перебрать все числа от min(a, b) до единицы и проверить условие делимости, однако и это не самый эффективный способ.

Люди, интересующиеся алгоритмами, сразу вспомнять алгоритм Евклида, однако, на мой взгляд, нет смысла зубрить алгоритмы — наиболее ценно их понимание и способность разработать нечто аналогичное. Для этого я предлагаю пытаться визуализировать задачу.

Целое число — это количество чего-либо неделимого. На следующей картинке два числа показаны в виде прямоугольников, под значением числа можно понимать количество «блоков в прямоугольнике». Показано схематично (я не пытался рисовать точно).

В физической интерпретации — замените блоки на кирпичи. НОД — размер кузова грузовика, такой что им можно перевезти все кирпичи, наполняя каждый раз кузов доверху.

Эффективный алгоритм расчета НОД строится на следующих наблюдениях (постарайтесь их «почувствовать»):

1. если A делится на B без остатка — то НОД(A, B) = B;
2. любое число, которое делит оба числа A и B, делит также и A-B, поэтому
   НОД(A, B) <= НОД (A — B, B);. То есть уменьшение числа A на значение B не повлияет на результат вычисления НОД;
3. мы можем воспользоваться предыдущим пунктом несколько (t) раз — если A = B*t + r для целых чисел t и r — то НОД(A, B) = НОД(r, B).

Из второго пункта следует идея следующего алгоритма поиска НОД: Отнимать от большего меньшее, пока числа не станут равны. Полученное число и является наибольшим общим делителем. Такой алгоритм будет работать значительно быстрее чем полный перебор, но и его можно улучшить — посмотрим визуализацию (исходное состояние показано выше):

В какой-то момент числа окажутся равны и мы получим результат. Этот момент обязательно настанет — в крайнем случае когда оба числа станут равны единице (потому что это ей кратны любые целые числа).

Из последней иллюстрации видно, что многократное вычитание можно заменить на получение остатка от деления (об этом же говорит третье «наблюдение»). Тогда алгоритм можно записать на псевдокоде следующим образом:

наибольший_общий_делитель(a, b) {
  если a делится на b без остатка то - верни b;
  если b делится на a без остатка то - верни a;
  
  если a > b - то верни наибольший_общий_делитель(a mod b, b);
  иначе верни наибольший_общий_делитель(a, b mod a);
}

Тут mod — операция получения остатка от деления.

2 Алгоритм расчета наименьшего общего кратного

Наименьшее общее кратное двух целых чисел A и B есть наименьшее натуральное число, которое делится на A и B без остатка.

Чтобы лучше понять о чем речь — предлагаю такую геометрическую интерпретацию: значения A и B задают длины отрезков. НОК — это длина другого отрезка, который можно составить как из целого количества отрезков A, так и отрезков B:

Для любых чисел мы можем найти общее кратное C = A*B, однако, оно не всегда будет наименьшим. Примитивный алгоритм вычисления НОК мог бы заключаться в переборе всех чисел от max(A, B) до A*B. Однако, это не самое эффективное решение. На самом деле, если длина отрезка A = 4, а B = 3, то перебирать надо все отрезки, кратные 4, т.е. max(A, B).

Обратите снимание, что если A и B взаимнопростые (иными словами НОД(A, B) = 1) — то НОК(A, B) = A*B. Если же у этих чисел есть делители d0, d1, ..., dn, то их общими кратными будут числа: (A*B)/d0, (A*B)/d1, … (A*B)/dn. Значит, чтобы найти наименьшее общее кратное, нужно найти наибольший из делителей:

наименьшее_общее_кратное(a, b) {
  верни (A*B)/наибольший_общий_делитель(a, b);
}