Контрольные тренировочные задания
(решения)

Часть 1

Задание 22

Решение примера 1

Исполнитель Май 15 преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя Май 15 – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Ответ: ___________________________.

Решение.

Решим нашу задачу в два этапа:
1 этап. Найдем количество программ Получить из 2 — 14
2 этап. Найдем количество программ Получить из 14 — 29, не проходя число 25

Найдем минимальное число, из которого существует два способа получения числа 14:
14/2 = 7 (это число 7)
Все числа, большие 7 имеют только один способ получения числа 14 (с помощью команды +1)

Рассмотрим числа, меньшие 7:

6: *2=12 (1 способ) или +1=7 (2 способа) Итого: 3

5: *2=10 (1 способ) или +1=6 (3 способа) Итого: 4

4: *2=8 (1 способ) или +1=5 (4 способа) Итого: 5

3: *2=6 (3 способа) или +1=4 (5 способов) Итого: 8

2: *2=4 (5 способов) или +1=3 (8 способов) Итого: 13

Итого, у числа 2 есть 13 способов получения числа 14.

Для того, чтобы перескочить число 25, нужно использовать команду *2.
Минимальное число, к которому можно применить эту команду равно 14 (14*2=28).
Есть только один спобоб получения числа 29 из 28: 28 + 1

Вывод: Количество решений равно: 13*1 = 13

Ответ: 13

Возврат на страницу    Решение примеров части 1 задание 22