Идеи реализации

Дробь p / q с положительными числителем и знаменателем называется правильной, если p < q . Мы можем сразу сосредоточиться на правильных дробях. Если дробь неправильная, разделим числитель на знаменатель с остатком. Целую часть дроби запишем отдельно. Если остаток r от деления отличен от нуля, запишем десятичную запятую, после чего займёмся правильной дробью r / q . Так что общий случай легко сводится к случаю правильной дроби.

Вспомним правила преобразования простой дроби в десятичную. Они прямо вытекают из правил деления в столбик. Если делимое меньше делителя, к нему приписывают ноль справа (умножают на 10) и делят нацело на делитель. В результате получается очередная цифра дроби. Остаток от деления служит в качестве очередного делимого, он опять умножается на 10, опять делится нацело на делитель, и так далее. Процесс останавливается, когда делимое обратится в ноль. Этот момент, как мы знаем, может и не наступить, и тогда деление будет продолжаться до бесконечности, порождая всё новые и новые цифры в десятичной записи дроби.

Для примера рассмотрим дробь 7 / 26 . Составим таблицу с тремя колонками. В первой будем записывать числители. Во второй и третьей окажутся целое частное и остаток от деления числителя, умноженного на 10, на знаменатель. Напомним, что x означает целую часть числа x. Так что целое частное при делении чисел α и β ( α div β ) получается как α / β , а остаток от деления ( α mod β ) — как α β α / β . Число из третьей колонки переносится в первую колонку следующей строки таблицы: p 10 p div q 10 p mod q 7 2 18 18 6 24 24 9 6 6 2 8 8 3 2 2 0 20 20 7 18 18 6 24 24 9 6

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

В частности, если там встретится ноль, все последующие числа будут также нулевыми (это потому что 10 0 mod q = 0 ). Это как раз случай конечной десятичной дроби: в какой-то момент наш алгоритм будет добавлять новые и новые незначащие нули, если его не прервать.

Второе наблюдение состоит в том, что одинаковым числителям из первой колонки соответствуют одинаковые десятичные цифры во второй, поскольку цифры однозначно определяются этими числителями. Это значит, что, начиная с некоторого момента, десятичная дробь будет содержать повторяющиеся группы цифр (периоды). Вот мы и доказали, что любое положительное рациональное число представляется в виде конечной или бесконечной десятичной дроби. В первом случае период состоит из единственной цифры — нуля, а во втором период содержит и другие цифры.

Итак, мы выяснили, как получать новые и новые десятичные цифры десятичного представления обыкновенной дроби. Нужно построить рекуррентную последовательность первого порядка, в начале которой находится p 0 = p — числитель дроби, а каждый следующий элемент получается из предыдущего по формуле p k + 1 = 10 p k mod q (последовательность числителей). Тогда k-я цифра после запятой находится по формуле d k = 10 p k div q (та цифра, которая следует сразу за запятой, идёт под номером 0).

Особо отметим, что последовательность d k , в отличие от p k , рекуррентной не является. Каждый элемент рекуррентной последовательности однозначно определяется предшествующим элементом, иначе дробь 2,001 была бы невозможной. Если бы цифры образовывали рекуррентную последовательность, после одинаковых цифр стояли бы одинаковые, чего не наблюдается в примере: после первого ноля находится ноль, а после второго — единица.

Обобщим сделанные наблюдения. Рассмотрим функцию φ, определённую на некотором конечном множестве и принимающую значения также из этого множества. Возьмём какой-нибудь элемент X 0 и для него построим последовательность X 1 = φ X 0 , X 2 = φ X 1 , X 3 = φ X 2 , . Получившаяся последовательность называется орбитой элемента X 0 для функции φ. Мы утверждаем, что, начиная с некоторого номера σ, орбита зациклится. Действительно, число различных элементов орбиты не больше, чем размер множества, и рано или поздно значения последовательности повторятся. Обозначим два первых одинаковых элемента как X σ и X σ + τ . Тогда X σ + 1 = φ X σ = X σ + τ + 1 = φ X σ + τ , и вообще, X n = X n + τ для всех n σ . Иными словами, если два элемента последовательности равны, то равны также и элементы, следующие за этими двумя, поскольку они получаются из предыдущих по одному и тому же правилу. Природа функции φ совершенно не важна, важно лишь то, что множество её значений конечно. Положительное число τ называется наименьшим периодом последовательности, начиная с номера σ.

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

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

Напрашивается следующее решение: каждый вновь найденный элемент последовательности p k добавлять в массив, прежде пытаясь его отыскать в этом массиве. Если элемент уже присутствует в массиве, периодическая часть последовательности начнётся с этого индекса. Если же элемент не найден, он в массив не добавляется, и вычисление рекуррентной последовательности завершается. К этому моменту мы располагаем массивом p k и индексом i в нём, обозначающим начало периодической части. Теперь всё просто. Для всех элементов массива вычисляем d k и тут же выводим, не забывая вставить открывающую скобку перед i-м элементом, и закрывающую в самом конце. Здесь, правда, есть одно осложнение, возникающее в том случае, если десятичная дробь конечна. Наш алгоритм всё равно сочтёт её периодической, и выведет в конце нулевой период (0). Нам это совершенно не нужно. Но такая ситуация возникает только тогда, когда последний вычисленный (и не добавленный в массив) элемент последовательности числителей равен нулю. Так что в том месте программы, где должен быть выведен период в скобках, следует сделать соответствующую проверку, и вообще не выводить периодическую часть, если это не нужно.

Увы, это решение совершенно ужасно. Заметим, что каждый числитель, попавший в массив, подвергался безуспешному сравнению со всеми предшествующими элементами. Общее количество сравнений равняется количеству всевозможных пар, которые можно составить из элементов массива. Мы знаем из комбинаторики, что для n-элементного множества количество пар, составленных из элементов, равно C n 2 = n n 1 / 2 , что при больших n приближённо равно n 2 / 2 . Вспомним, что n в нашей задаче может достигать значения q, так что для знаменателя дроби порядка миллиона может потребоваться массив миллионной длины, да и вряд ли мы дождёмся его заполнения, которое потребует полтриллиона сравнений.

Остроумный метод Черепахи и Зайца, который также называют в честь первооткрывателя методом Флойда, позволяет выявлять циклы в последовательностях, то есть находить числа σ и τ.

Мысленно проведём стрелки от каждого элемента последовательности к следующему за ним. Черепаха и Заяц, герои басни Эзопа, могут сдвигаться по стрелкам. Выявление цикла, согласно методу Флойда, происходит в три этапа, каждый из которых завершается, как только Черепаха и Заяц встречаются. Разберём в подробностях каждый этап, но прежде введём нужные обозначения.

Два целых числа x и y, дающих при делении на целое положительное число a одинаковые остатки, будем называть сравнимыми по модулю a. Этот факт обычно записывают так: x y modulo a , а выписанное выражение называют сравнением по модулю.

Сравнения во многом похожи на равенства. В частности, к обеим частям сравнения можно прибавить одно и то же целое число, и сравнение останется верным. Этот факт следует из того, что при увеличении или уменьшении на единицу обеих частей сравнения остатки от деления на a одновременно либо увеличиваются (уменьшаются) на единицу, либо одновременно обращаются в нуль. Несложно доказать также, что сравнение останется верным при умножении обеих частей на одно и то же целое число. Достаточно показать это для сравнений вида x y 0 (к такому виду можно привести любое сравнение, перенося правую часть налево с изменением знака). Полученное сравнение означает, что x y делится нацело на a, и этот факт не перестанет быть верным при умножении обеих частей сравнения на произвольное целое число.

На первом этапе Черепаха и Заяц находятся в начале последовательности. На каждом шаге Черепаха сдвигается по стрелке один раз, а Заяц — дважды (рисунок 15.1. «Черепаха и Заяц: первый этап»). Мы утверждаем, что их встреча обязательно состоится, и не позже, чем Черепаха пройдёт первый круг цикла. И в самом деле, рано или поздно Черепаха достигнет начала цикла. Пронумеруем элементы последовательности в цикле числами i = 0 , , τ 1 . Как только Черепаха вступит в цикл (то есть окажется в положении T = 0 ), Заяц уже будет где-то на цикле в положении H = H * . Дальнейшее движение Черепахи по циклу подчиняется закону T = i , а Зайца — H = H * + 2 i mod τ . Условием встречи героев является сравнение T H modulo τ , или i H * + 2 i mod τ , или просто i H * + 2 i , или i H * . Наименьшим неотрицательным решением этого сравнения будет i = H * mod τ , это i и будет номером позиции, где произойдёт встреча.

Интересно, что сделанное Черепахой количество шагов на первом этапе делится на длину периода τ. К моменту, когда Черепаха пройдёт по стрелкам путь n от начала дистанции, Заяц пройдёт путь 2 n . В момент встречи они оба будут находиться на цикле, и поэтому выполнится сравнение n 2 n , или n 0 (конечно же по модулю τ).

Рисунок 15.1. Черепаха и Заяц: первый этап

Целью второго этапа является обнаружение начала цикла. Теперь Черепаха становится в начало дистанции, а Заяц остаётся там, где закончился первый этап. На втором этапе герои на каждом шаге сдвигаются вперёд на одну позицию, и так происходит до их встречи (рисунок 15.2. «Черепаха и Заяц: второй этап»). Оказывается, место встречи будет как раз в начале цикла. Шаги на втором этапе подсчитываются, и после окончания забега их количество будет равно длине непериодической части орбиты.

Мы уже знаем, что Заяц после первого забега и перед началом второго прошёл по стрелкам путь σ + H * и ещё плюс какое-то количество полных кругов, то есть пробег Зайца сравним с нулём по модулю τ. Если сдвинуть Зайца σ раз, его пробег увеличится на σ, и выполнится сравнение 2 σ + H * σ . Пробег Черепахи после σ шагов будет равен σ. В этот момент она как раз окажется в начале цикла (Заяц к этому времени уже будет там). Вот тут-то они и встретятся, поскольку их пробеги будут сравнимы по модулю τ.

Рисунок 15.2. Черепаха и Заяц: второй этап

Третий этап нужен для определения конца цикла и он совершенно тривиален. Черепаха остаётся неподвижно там, где она встретились с Зайцем в конце второго этапа, то есть в начале цикла. Заяц же на каждом шаге сдвигается на одну позицию, пока не встретится с Черепахой, пройдя один круг. Шаги Зайца подсчитываются, и после окончания третьего забега счётчик покажет длину цикла (рисунок 15.3. «Черепаха и Заяц: третий этап»).