Условие
Дано натуральное число
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 := 1;
{r = (n+k+1)-ый член последовательности остатков}
while r <> c do begin
| r := (10 * r) mod n;
| k := k + 1;
end;
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
1 |
|
Название |
Задачи без массивов |
|
задача |
|
Номер |
1.1.31 |
