≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 22 № 11123

Исполнитель Вычитатель преобразует число, которое записано на экране. У исполнителя Вычитатель две команды, которым присвоены номера:

 

1. Вычти 2

2. Вычти 5

 

Первая из них уменьшает число на экране на 2, вторая уменьшает его на 5. Программа для Вычитателя – это последовательность команд. Сколько есть программ, которые число 22 преобразуют в число 2?

Пояснение.

Для вычитания справедлив коммутативный (переместительный) закон, значит, порядок команд в программе не имеет значения для результата.

 

Обе команды уменьшают исходное число, поэтому количество команд не может превосходить (22 — 2)/2 = 10. При этом минимальное количество команд — 4 (т. к. [22 − 2]/5 = 4). Заметим, что 22 — чётное и 2 — четное. Поскольку команда 2 вычитает нечётное число, то команда 2 должна встречаться чётное число раз.

 

Иначе говоря, команд может быть от четырёх, до десяти.

Четырём командам соответствует набор 2222.

При помощи пяти команд нельзя преобразовать число 22 в число 2.

При помощи шести команд нельзя преобразовать число 22 в число 2.

Семи командам соответствует набор 111 1122. (21 возможный вариант расположения: это число перестановок с повторениями P7(2,5) = 7!/(2! · 5!))

При помощи восьми команд нельзя преобразовать число 22 в число 2.

При помощи девяти команд нельзя преобразовать число 22 в число 2.

Десяти командам соответствует набор 11 1111 1111.

Всего имеем 23 программы.

 

Ответ: 23.

Источник: ЕГЭ по ин­фор­ма­ти­ке 23.03.2016. До­сроч­ная волна