🔈Задача:
Исполнитель Фибо преобразуется число на экране. У исполнителя есть две команды, которым присвоены номера:
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.
Авторизуйтесь, чтобы оставить комментарий.