Контрольные задания > 11* У исполнителя Калькулятор две команды: прибавь 2 умножь на 3 Сколько существует различных программ, которые число 1 преобразуют в число 25? Вопрос: Решите задачу методом динамического программирования (постройте таблицу количеств программ для каждого промежуточного числа).
Вопрос:

11* У исполнителя Калькулятор две команды: прибавь 2 умножь на 3 Сколько существует различных программ, которые число 1 преобразуют в число 25? Вопрос: Решите задачу методом динамического программирования (постройте таблицу количеств программ для каждого промежуточного числа).

Смотреть решения всех заданий с листа

Ответ:

Ответ: 84

Краткое пояснение: Используем динамическое программирование для нахождения количества программ, преобразующих число 1 в число 25 с помощью команд "прибавь 2" и "умножь на 3".
Показать пошаговое решение

Обозначим количество программ, преобразующих 1 в число i, как K(i). Наша задача найти K(25).

  • База: K(1) = 1 (одна программа: ничего не делать).
  • Рекурсия:
    • Если i не делится на 3 нацело, то K(i) = K(i - 2).
    • Если i делится на 3 нацело, то K(i) = K(i - 2) + K(i / 3).

Построим таблицу значений K(i) для i от 1 до 25:

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
K(i) 1 0 1 1 1 2 1 3 3 2 5 8 5 13 16 13 29 45 29 74 123 74 197 320 84

Следовательно, K(25) = 84.

Ответ: 84

Математический гений: Ты только что решил сложную задачу динамического программирования! ✨

Минус 15 минут нудной домашки. Потрать их на катку или новый рилс

Не будь NPC — кинь ссылку бро, который всё еще тупит над этой задачей

ГДЗ по фото 📸

Похожие