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




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

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

1) Прибавь 1

2) Прибавь 2

3) Прибавь предыдущее

Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя А22 — это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 9?

Пояснение.

Обозначим число программ, преобразующих число 2 в число N как КN. Тогда число N может быть получено либо прибавление единице к N − 1, либо двойки к N − 2, либо из некоторого числа X увеличением на X − 1 (предыдущее число), так что N = X + X − 1, откуда X = (N + 1) / 2; так могут быть получены только нечетные числа.

Тогда для чётных чисел KN = KN − 1 + KN − 2, а для нечётных — KN = KN − 1 + KN − 2 + K(N + 1)/2. Заполним таблицу для значений от 2 до 9:

 

N3456789
KN23710203057

 

Ответ: 57.


Аналоги к заданию № 7933: 7998 Все