Древние алгоритмы: чему нас учат египетские дроби

Каждый раз, когда вы пишете рекурсивную функцию или реализуете жадный алгоритм, вы следуете по стопам математиков, живших тысячи лет назад. Египетские дроби — выражения, использующие только обратные значения целых чисел — представляют один из древнейших задокументированных алгоритмов в истории человечества. И они гораздо глубже, чем кажется на первый взгляд.

Задача, которую решали египтяне

Современные дроби кажутся нам чем-то естественным: 3/7, 5/12, 17/23. Но такой формат записи появился в Европе только в XVIII веке. До этого, если нужно было записать дробь, её разбивали на сумму долей единицы — то есть дробей с единицей в числителе.

Египтяне столкнулись с практической задачей: как справедливо разделить 7 буханок хлеба между 8 людьми? Ответом не было простое «7/8». Вместо этого результат записывали как сумму разных единичных долей: 1/2 + 1/4 + 1/8.

Этот, казалось бы, простой подход требовал серьёзного математического мышления и породил то, что сейчас называют алгоритмом египетских дробей.

Жадный алгоритм в древнем исполнении

Здесь становится интересно для разработчиков. Метод, который египтяне использовали для преобразования любой дроби в египетскую, по сути является жадным алгоритмом — выбираем наибольшую возможную единичную долю, вычитаем её, затем повторяем.

Возьмём 4/23. Алгоритм спрашивает: какое наименьшее целое число больше, чем 23/4? Это 6. Значит, начинаем с 1/6, вычитаем из 4/23, получаем 1/138, и готово: 4/23 = 1/6 + 1/138.

Этот подход работает всегда — теорема была доказана в 1880 году, хотя европейцы узнали о технике ещё в XII веке благодаря Фибоначчи.

Почему это важно для разработчиков

На первый взгляд — просто исторический факт. Но давайте разберём, что происходит в этом алгоритме:

1. Рекурсивное разложение — разбиваем сложную задачу на более простую подзадачу
2. Жадный выбор — делаем оптимальный локальный выбор на каждом шаге
3. Доказательство завершимости — остаток постоянно уменьшается, гарантируя окончание работы

Эти концепции лежат в основе современного алгоритмического мышления. Когда вы пишете рекурсивную функцию, вы применяете ту же логическую структуру, что и древние математики.

Исторический пробел

Здесь есть неудобная история, которую стоит упомянуть. Метод египетских дробей появился на тысячелетия раньше греческой математики. Однако когда европейские математики «заново открыли» папирус Ринда в XIX веке, технику часто приписывали греческим учёным, а не её реальному египетскому происхождению.

Такая закономерность — приуменьшение или стирание вклада африканских и других неевропейских цивилизаций в математическую историю — сохраняется в том, как мы преподаём и обсуждаем информатику сегодня.

Математические загадки

Одна любопытная головоломка связана с тем, что учёные называют «египетским триплом»: 13, 17 и 173. Если интерпретировать их как 3 + 1/13 + 1/17 + 1/173, это выражение даёт приближение числа π с точностью до четырёх знаков — точнее, чем широко упоминаемое египетское значение 3.16.

Было ли это намеренным или совпадением — вопрос, который до сих пор обсуждают историки математики.

От древности к современности

Египетские дроби связаны с цепными дробями — темой, которая активно изучается в информатике и теории чисел. Подход с жадным алгоритмом находит применение в задачах распределения ресурсов, планирования и оптимизации.

Так что в следующий раз, когда будете отлаживать рекурсивную функцию или объяснять, почему работает жадный подход, вспомните: вы участвуете в математической традиции, которая насчитывает почти 4000 лет.

Иногда самые старые алгоритмы — всё ещё лучшие алгоритмы.