Начинаешь как программист изучать алгоритмику и прописываешь в гугле, «Алгоритм Евклида». Твой взгляд цепляет куча непонятных слов.
Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел
Постараемся из этого страшного математического термина, сделать термин который реален.
Задача: нужно равномерно заполнить стену плиткой, но при этом мы не хотим видеть в углах неравномерно — обрезанную плитку. Для этого нам нужно найти самую большую высоту и ширину плитки. Посмотрите на эту стену она квадратная и имеет одинаковые стороны, по этому для нас будет очевидно разбить на четыре ровных квадрата.
Но что делать с не очевидным случаем. Как распределить здесь плитку?
Вот здесь нам и поможет Евклидовый алгоритм. Нам потребуется найти самую маленькую сторону и сделать из неё квадрат. На картинке самая малая сторона состоит из 3 квадратов. Вот из этой длины заполняем плиткой всю область фигуры.
Но в один момент мы доходим до того что не делиться наша стена на наши 3 квадрата. Не паникуем. Ищем новую наименьшую сторону стены и из её длины заполняем всю область новыми плитками по меньше. Пока не заполним всю область
Но и тут мы видим что в один момент стена перестает делиться и находим ещё меньше сторону которая состоит из одного квадрата. Продолжаем работать по алгоритму. Нашли меньше сторону заполняем с помощью её длины всю возможную область и так до того момента пока не заполним всю область.
Вот как на реальном примере можно использовать Евклидовый алгоритм.
Более подробно про алгоритмы можете почитать в книге — «Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. Бхаргава А.»
Доказательство можно почитать — тут
С вас оценка и подписка
Блог автора - illyalandar.site