Траектории

🔈Задача:

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

1. Прибавить 1
2. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя Фибо — это последовательность команд.

❓Сколько существует программ, которые преобразуют исходное число 3 в число 20 и при этом траектория вычислений содержит число 9 и не содержит числа 15?

🤷Что такое траектория?
– это последовательность результатов выполнения всех команд программы.

📝Один из методов решений таких задачек — разбить траекторию от 3 до 20 на участки, чтобы содержалось число 9 и не содержалось 15, тогда искомое количество программ равно произведению количества программ
— (из 3 в 9), на количество (из 9 в 14) на количество программ (из 16 в 20).

🔎1️⃣Рассмотрим кол-во способов получить из 3 — 9:

(3) = 1
(4) = (3) = 1
(5) = (3) +(4) = 2
(6) = (5) + (4) = 3
(7) = (6) + (5) = 5
(8) = (7) + (6) = 8
(9) = (8) + (7) = 13
=> существует 13 способов попасть в 9 из 3

🔎2️⃣Рассмотрим кол-во способов способов попасть из 9 в 14:

(9) = 1
(10) = (9) = 1
(11) = (9) + (10) = 2
(12) = (10) + (11) = 3
(13) = (11) + (12) = 5
(14) = (12) + (13) = 8

=> существует 8 способов попасть из 9 в 14

🔎3️⃣ И,наконец, рассмотрим, как можно попасть из 16 в 20:

(16) = 1
(17) = (16) = 1
(18) = (16) + (17) = 2
(19) = (17) + (18) = 3
(20) = (18) + (19) = 5

😎ИТОГО: количество программ попасть из 3 в 20, проходя 9 и не задевая 15 = 8 * 13 * 5 = 520 способов.

Ответ: 520.