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




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

У исполнителя Арифметик две команды, которым присвоены номера:

 

1. прибавь 1,

2. прибавь 3.

 

Первая из них увеличивает на 1 число на экране, вторая увеличивает это число на 3.

Программа для Арифметика — это последовательность команд.

Сколько существует программ, которые число 2 преобразуют в число 15?

Пояснение.

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

Обе команды увеличивают исходное число, поэтому количество команд не может превосходить 15 − 2 = 13. При этом минимальное количество команд — 5 (так как (15 −2)/3 = 4 с остатком 1). При этом заметим, что 15 — нечетное, а 2 — четное. А так как обе команды увеличивают исходное число на нечетное число, то количество команд должно быть нечетным.

Иначе говоря, команд может быть 5, 7, 9, 11 или 13. Так как, как было сказано выше, порядок команд не имеет значения, каждому числу команд соответствует один набор команд, которые можно расположить в любом порядке. Пяти командам соответствует набор 22221 (5 возможных вариантов расположения), 7 командам — набор 2221111 (здесь получается 35 возможных вариантов расположения: это число перестановок с повторениями P7(3,4)=7!/(3! · 4!)), 9 командам — 22111111 (здесь получается 36 возможных вариантов расположения), 11 командам — 21111111111 (11 возможных вариантов расположения), 13 командам — 11111111111111 (1 вариант расположения). Всего имеем 88 программ.

 

Ответ: 88.