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

Проект МЦНМО
при участии
школы 57
Задача 60847
Темы:    [ Теория алгоритмов (прочее) ]
[ Периодические и непериодические дроби ]
[ Рациональные и иррациональные числа ]
[ Периодичность и непериодичность ]
[ Принцип Дирихле (прочее) ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Коля Васин задумал написать программу, которая дала бы возможность компьютеру печатать одну за другой цифры десятичной записи числа . Докажите, что даже если бы машина не ломалась, то Колина затея все равно бы не удалась, и рано или поздно компьютер напечатал бы неверную цифру.


Решение

  Предположим, что компьютер выполняет программу, в результате которой печатается некоторая последовательность цифр. Докажем, что эта последовательность периодическая.
  Можно считать, что компьютер работает дискретно. Состоянием компьютера в каждый (целый ) момент назовём содержимое всех его ячеек памяти и номер выполняемой команды. Поскольку количество ячеек конечно, объём каждой ячейки ограничен, и программа состоит из конечного числа команд, то число различных состояний конечно. Поэтому когда-нибудь состояние компьютера повторится. Каждое следующее состояние полностью определяется предыдущим, поэтому далее компьютер будет повторять свои действия и, следовательно, печатать периодическую последовательность.

Источники и прецеденты использования

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 5
Название Числа, дроби, системы счисления
Тема Системы счисления
параграф
Номер 1
Название Рациональные и иррациональные числа
Тема Дроби
задача
Номер 05.009

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

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