ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 76227
Темы:    [ Знакомство с циклами ]
[ Задачи с целыми числами ]
[ Десятичная запись числа ]
Сложность: 2+
Классы:
В корзину
Прислать комментарий

Условие

Дано натуральное число 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .