|
Математика: Теория чисел.
Дано натуральное число 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;
![](../../gif/3arrow1.gif) Вверх по странице, к оглавлению и навигации.
| |