Начинаешь как программист изучать алгоритмику и прописываешь в гугле, «Алгоритм Евклида». Твой взгляд цепляет куча непонятных слов. Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел Постараемся из этого страшного математического термина, сделать термин который реален. Задача: нужно равномерно заполнить стену плиткой, но при этом мы не хотим видеть в углах неравномерно — обрезанную плитку. Для этого нам нужно найти самую большую высоту и ширину плитки. Посмотрите на эту стену она квадратная и имеет одинаковые стороны, по этому для нас будет очевидно разбить на четыре ровных квадрата...
539 подписчиков
А теперь к настоящим алгоритмам, а не использованию уже написанных в стандартной библиотеке. Читаем условие задачи: Алгоритм Евклида - это, действительно, эффективный способ вычисления наибольшего общего делителя двух чисел. Но та версия, которую изучил Дима из условия задачи является неоптимальной. Давайте посмотрим на примере. Если даны два числа 1000000 и 12, то шаг 4 будет выполняться очень много раз (83333), после чего a будет равно 4, а b - 12 (затем, они, конечно, поменяются местами). На примере мы можем заметить, что 1000000 = 83333 * 12 + 4, или в общем виде a = k * b + r...