Вопрос 19 из 47

Практика: переменные, ветвления, циклы и функции

Повторяющиеся подзадачи: как запоминание меняет дерево вызовов

От чтения к действию

А теперь — вы

Функция по неотрицательному целому n имеет базы n=0 и n=1; при n≥2 обращается к n−1 и n−2. В однопоточном вычислении F(7) с изначально пустым неограниченным кэшем сколько разных состояний n будет достигнуто?

Разберёмся в теме

Мемоизация сохраняет результат подзадачи под ключом её входных данных. При повторном обращении с тем же ключом готовое значение берут из памяти вместо повторного вычисления тела. Это полезно, когда рекурсия многократно встречает одинаковые подзадачи. Само правило рекурсии и базовые случаи при этом остаются прежними; правильность ответа не возникает из одного наличия кэша.

Объяснение и примеры

Частые вопросы

Где найти подробное решение?

Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.

Можно ли попробовать снова?

Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.