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

Условие:
Есть (вводится с терминала) правильная рациональная дробь 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] массива на его положительность.

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

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

Дата
Страница
Задача: Построение периодической дроби
Рейтинг
51star1star1star1star1star
Olej

Об авторе Olej

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

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

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