Источник: Nuances of Programming Предположим, вы ищете человека по имени “Эльвира” в огромном телефонном справочнике. Он может состоять из 100 страниц, и было бы утомительно изучать каждую из них с самого начала линейным способом, пока вы не найдете девушку с нужным вам именем. К счастью, имена в справочнике расположены в алфавитном порядке  —  это большой плюс. Представьте, что вы открываете справочник на середине. Вы смотрите на страницу и видите имена, начинающиеся на “Н”. Зная, что буква “Э”...

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