Задача: Построение периодической дроби

Оцени эту статью

Условие:
Есть (вводится с терминала) правильная рациональная дробь a / b (запись в виде простой дроби).
— a и b — целые числа;
— если дробь правильная, то a < b.

Нужно программно определить период периодической дроби и вывести её в формате с десятичной точкой, вида 0.12(34) (из курса школьной арифметики помним, что это 0.12343434… — бесконечная дробь).

Усложняем задачу тем, том, что система счисления записи бесконечной дроби может быть произвольной и выбирается случайно (при вводе данных).

Например, в 10-тичной системе мы должны получить:
1 / 12 = 0.08(3)
11 / 13 = 0.8(461538)
2 / 5 = 0.4
А в 2-ичной системе, соответственно:
17 / 47 = 0.(01011100100110001000001)

Это 1-я задача. А после решения этой первой задачи, ставим себе задачу 2: переделать программу так, чтобы на каждом шаге (определения цифры) не делать полный поиск уже встречавшихся ранее остатков…

Решение:

Прежде всего, вспомним как рациональная дробь (1/3) преобразовывается в бесконечную (0.3333… или 0.(3)) — это можно подробно почитать здесь — Обращение обыкновенных дробей в десятичные и обратно:

  • В цикле находим частное и остаток от деления числителя на знаменатель.
  • Частное — это очередная цифра в бесконечной записи. Сохраняем остатки на каждом шаге.
  • Умножаем остаток на основание системы счисления — это у нас будет числитель для следующегошага итерации.
  • Если остаток на каком-то шаге равен нулю, то дробь — конечная.
  • Иначе ищем остаток в числе ранее сохранённых. Если нашли, то мы нашли период (дальше всё будет периодически повторяться).
  • Если не нашли, то сохраняем текущий остаток и возвращаемся к вычислению следующего разряда.

Собственно, этого достаточно, чтобы записать решение задачи 1 (с поиском сохранённых остатков):

Как легко видеть, весь алгоритм начинается со строки 39 и занимает всего 12 строк — всё остальное это ввод и подготовка данных:

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

И теперь мы видим, что на каждом шаге нам нужно искать полученный остаток в массиве (векторе) на совпадение с ранее полученными. Это расточительно. Зная, как работает алгоритм, можно пойти на такой трюк:

  • для знаменателя N остаток может иметь только N значений 0…N-1
  • создадим массив из N элементов, и разметим его значением -1, которое означает «такое значение остатка ещё не встречалось»…
  • а вот если на очередном шаге мы получим значение M, то в элемент [M] массива запишем номер итерации, на котором было это значение…
  • теперь, если после очередного шага, мы получим значение K, то нам не нужно искать это значение во всём массиве, а нужно только проверить элемент [K] массива на его положительность.

И вот что из этого получается:

Рассылка новых уроков по программированию:

Olej

Об авторе Olej

Стаж практических программных разработок около 40 лет. Преподаватель международной софтверной компании Global Logic. Постоянный автор публикаций IBM Developer Works. Научный редактор книжного издательства компьютерной литературы "Символ-Плюс", Санкт-Петербург.

Добавить комментарий

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>