Дроби вам

[vak]

Оказывается, есть такой алгоритм: Штерна—Броко называется. Простым, но неочевидным способом вычисляет все неприводимые дроби (включая целые числа). Очень остроумно. Мне раньше не попадался почему-то.

1. Создаем список из двух дробей:

Не шарахайтесь от деления на единицу и нуль, так нужно.

2. Берём соседнюю пару дробей и между ними вставляем новую дробь. Пусть исходная пара была:

Новая дробь будет:

3. Повторяем итеративно до бесконечности.

Нетрудно доказать, что всякая неприводимая дробь будет рано или поздно вычислена. При этом никакое значение не повторится дважды.

Comments

[spamsink]

Прикладное значение этого алгоритма - находить рациональные приближения для вещественных чисел с любой наперед заданной точностью, использующие минимальный знаменатель, не мучаясь с непрерывными дробями.

[vak]

А можно представить пути в дереве Штерна—Броко как двоичную кодировку рациональных чисел. Нолик - шаг влево, единичка - шаг вправо. И построить для этой кодировки арифметическое устройство. Может найти применение в нейронных сетях, вместо всяких int4 и float8.

[spamsink]

Эта вещица будет посильнее не только Фауста Гёте, но и системы остаточных классов.