Задача 9.
Найти длину периода и сам период бесконечной степенной дроби по основанию Р, представляющей рациональное число N/M (для конечных дробей считать, что длина периода равна 1). M,N,P - целые десятичные числа, 0<N<M, 1<P.
|
Решение задачи 9.
Введем переменную N1=N.
Пусть N1 и M заданы в десятичной системе счисления. Переведем дробь N1/M в систему счисления с основанием p:
Пусть в системе с основанием p искомая дробь 0.a(1)a(2)...
Получаем:
a(1)*p-1+a(2)*p-2+ ... =N1/M.
Умножим правую и левую части равенства на p:
a(1)+a(2)*p-1+ ... = N1*p/M.
Выделяя целую часть выражений слева и справа от знака равенства, получаем
a(1) = целая часть (N1*p/M).
Обозначим N2 = N1*p mod M; очевидным образом получаем
a(2)*p-1+ ... = N2/M.
Домножая на p и находя целую часть, опять же имеем
a(2) = целая часть (N2*p/M);
продолжая аналогично, определяем коэффициенты a(3),a(4) и т.д.
В ходе выделения цифр ai мы можем получить различных значений Ni не более чем M (по алгоритму выше у нас всегда Ni<M).
Если вдруг какие-то два остатка совпадают: Ni=Nj, i<>j, то совпадают и цифры разложения: ai+1=aj+1, ai+2=aj+2, ... , т.е. цифры (ai+1, ... ,aj) образуют один из кратных периодов. Нам надо найти минимальную длину такой периодически повторяющейся последовательности, которая равна количеству цифр между двумя ближайшими повторяющимися остатками, и сами цифры.
Поступаем следующим образом:
Выделяем M цифр p-ичной дроби (исходя из вышесказанного, к этому моменту период уже обязан начаться). Запоминаем Nm, и ищем первый такой остаток Nk, k>m, что Nm=Nk. Величина k-m как раз и есть искомая длина периода.
|
