Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Теория чисел /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Период бесконечной дроби N/M по основанию P - Программирование от RIN.RU
Период бесконечной дроби N/M по основанию P

Здесь можно прочитать о решении частного случая задачи:


"Дано натуральное число n>1. Определить длину периода десятичной записи дроби 1/n."


Введем переменную 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

Если вдруг какие-то два остатка совпадают: 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 как раз и есть искомая длина периода.



 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь