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

Решение.  Период  дроби  равен периоду в последовательности остатков. Кроме того, в этой последовательности все периодически повторяющиеся все члены различны, а предпериод имеет длину не более n. Поэтому достаточно найти (n+1)-ый член последовательности остатков и  затем  минимальное  k,  при  котором (n+1+k)-ый член совпадает с (n+1)-ым.

  l := 0; r := 1;
  {инвариант: r/n = результат отбрасывания l знаков в 1/n}
 
while l <> n+1 do begin
  | r := (10 * r) mod n;
  | l := l + 1;
  end;
 
c := r;
  {c = (n+1)-ый член последовательности остатков}
  r := (10 * r) mod n;
  k := 0;
  {r = (n+k+1)-ый член последовательности остатков}
 
while r <> c do begin
  | r := (10 * r) mod n;
  | k := k + 1;
  end;


2009-12-04 • Просмотров [ 3324 ]