Решение (1 способ, составление таблицы):. 1) заметим, что при выполнении любой из команд число увеличивается (не может

1) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)

2) для начального числа 2 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через  обозначить количество разных программ для получения числа N из начального числа 2, то .

3) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую  с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N

4) число N могло быть получено одной из трёх операций сложения:

- увеличением на 1 числа N-1;

- увеличением на 2 числа N-2;

- из некоторого числа X увеличением на X+1 (следующее число), так что N = X + X + 1, откуда X = (N – 1) / 2; так могут быть получены только нечетные числа;

поэтому

 для чётных чисел

 для нечётных чисел

5) остается по этой формуле заполнить таблицу для всех значений от 2 до 10:

N	2	3	4	5	6	7	8	9	10
	1	1	2	4	6	11	17	30	47

6) ответ –  47.

Ещё пример задания:

Р-03. Исполнитель Май4 преобразует число, записанное на экране. У исполнителя

три команды, которым присвоены номера:

Прибавь 1

Прибавь 2

Прибавь 4

Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья – на 4. Программа для исполнителя Май4 – это последовательность команд. Сколько есть программ, которые число 21 преобразуют в число 30?

Решение (1 способ, составление таблицы):

7) заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)

8) все числа, меньшие начального числа 21, с помощью этого исполнителя получить нельзя, для них количество программ будет равно 0

9) для начального числа 21 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через  обозначить количество разных программ для получения числа N из начального числа 21, то .

10) теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую  с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N

11) любое число N > 21 могло быть получено одной из трёх операций сложения соответственно из чисел N-1, N-2 и N-4, поэтому

12) остается по этой формуле заполнить таблицу для всех значений от 21 до 30:

N	2 1	2 2	2 3	2 4	25	2 6	2 7	2 8	2 9	3 0
	1	1	2	3	6	10	18	31	5 5	96

13) ответ –  96.

Ещё пример задания:

Р-02. У исполнителя Утроитель две команды, которым присвоены номера:

Прибавь 1

Умножь на 3

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

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

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

⇐ Предыдущая12345Следующая ⇒

Поделиться: