Задание 3. Тип заданий 22: количество программ.
  • Задание:

    Исполнитель Калькулятор имеет две команды:

    Прибавь 1

    Умножь на 2

    Первая команда увеличивает число на 1, вторая умножает число на 2. Например, первая команда преобразует число 5 в число 6, вторая преобразует число 5 в число 10.

    Сколько существует программ для этого исполнителя, преобразующих число 2 в число 20?

  • Решение:

    Первым делом давайте найдём наименьшее число, к которому мы можем применять только одну команду.

    Мы получаем из числа 2 число 20. Очевидно, что если мы возьмем число 11, то умножить на 2 мы его не можем, так как в этом случае результатом будет 22. То есть к 11 мы можем только прибавлять 1, в отличие, к примеру, от числа 10, к которому можно применить обе команды.

    Рассмотрим число 11. К нему мы можем только прибавлять 1, значит из 11 существует только один набор команд:

    Чтобы не запутаться в числах, общее количество программ будем обводить кружком. Теперь рассмотрим число, стоящее перед 11, то есть 10. Из 10 мы можем получить 11 или 20. Из 11, как мы знаем, существует только одна программа, и еще одна программа — умножить число 10 на 2:

    Рассмотрим число 9. Из него мы можем получить 10 или 18. Из числа 10 существует 2 программы, к числу 18 мы можем только прибавлять единицу, то есть из числа 18 существует только одна программа. Всего 3:

    Рассмотрим число 8. Из него можно получить 9 или 16. Из числа 9 существует три программы, к числу 16 мы можем только прибавлять 1, то есть из 16 существует только один набор команд:

    Рассмотрим число 7. Из него мы можем получить 8 или 14. По аналогии с предыдущими заданиями строим граф:

    Рассмотрим число 6. Из него мы можем получить 7 или 12. Построим граф:

    Рассмотрим число 5. Из него мы можем получить 6 или 10. Обратите внимание, из 10 существует два набора программ, то есть граф будет выглядеть так:

    Рассмотрим число 4. Из него мы можем получить 5 или 8. Построим граф:

    Рассмотрим число 3. Из него мы можем получить 4 или 6. Построим граф:

    И последнее число — 2. Из него можем получить 3 или 4. Отобразим это на графе:

    Как мы видим, общее количество программ для получения 20 из числа 2 — 30.

    Ответ: 30

Поделиться:
 
Комментарии (0)

Нет комментариев. Ваш будет первым!

Перевести число из в Результат: 510 = 1012