Основы программирования на С++ для начинающих

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

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

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

Задача: Построение периодической дроби
4 (80%) 1 vote[s]

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *