286 читали · 4 года назад
Задача 527. Алгоритм Евклида
А теперь к настоящим алгоритмам, а не использованию уже написанных в стандартной библиотеке. Читаем условие задачи: Алгоритм Евклида - это, действительно, эффективный способ вычисления наибольшего общего делителя двух чисел. Но та версия, которую изучил Дима из условия задачи является неоптимальной. Давайте посмотрим на примере. Если даны два числа 1000000 и 12, то шаг 4 будет выполняться очень много раз (83333), после чего a будет равно 4, а b - 12 (затем, они, конечно, поменяются местами). На примере мы можем заметить, что 1000000 = 83333 * 12 + 4, или в общем виде a = k * b + r...
6390 читали · 2 года назад
Гениальное и самое наглядное объяснение первого в истории математики алгоритма. Греки называли его "антифарезис"
Приветствую Вас, уважаемые Читатели! Сегодня у нас день занимательной арифметики, который будет посвящен одному из первых дошедших до нас арифметических алгоритмов. Только познакомимся мы с ним самым простым и наглядным путем. Итак, поехали! Вспомните: у Вас под рукой тетрадный лист в клеточку, скучное занятие, чем Вы можете заняться? Для начала - нарисовать прямоугольник! Ширина и длина выбраны совершенно произвольно. Что будем делать дальше? Я предлагаю взять и разделить прямоугольник на квадраты,...