Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё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.