Просто УрокТест · Информатика
Динамическое программирование
Отвечай кликом — после каждого вопроса пояснение. 10 вопросов, 4 варианта, 3–5 минут. Без таймеров и регистрации.
Отвечено 0 из 10 · Верно: 0
1/10
Какой базовый принцип лежит в основе метода динамического программирования?
Пояснение. Динамическое программирование основано на разбиении задачи на взаимосвязанные подзадачи с повторным использованием уже вычисленных результатов.
2/10
Исполнитель может совершать прыжки на 1 или 2 клетки вперед. Сколькими способами он попадет из клетки 1 в клетку 5?
Пояснение. Число путей образует ряд Фибоначчи: для клеток с 1 по 5 количество способов равно последовательно 1, 1, 2, 3 и 5.
3/10
Как называется подход в динамическом программировании, при котором решение строится сверху вниз с сохранением промежуточных результатов?
Пояснение. Мемоизация представляет собой оптимизацию рекурсии сверху вниз путем кэширования результатов функций для предотвращения повторных вычислений.
4/10
Робот перемещается по клеткам сетки 3×3 из левого верхнего угла в правый нижний, двигаясь только вправо и вниз. Сколько существует таких маршрутов?
Пояснение. Количество путей вычисляется как число сочетаний C(4, 2) или табличным заполнением динамики и составляет ровно 6 маршрутов.
5/10
Какую временную сложность имеет вычисление N-го числа Фибоначчи с использованием одномерного массива методом табуляции?
Пояснение. Табуляция заполняет массив от 1 до N в одном цикле, что требует линейного времени O(N).
6/10
Какое рекуррентное соотношение определяет минимальное число монет F(S) для выдачи сдачи S монетами достоинством c₁, ..., cₖ?
Пояснение. К минимальному количеству монет для оставшейся суммы (S - cᵢ) добавляется ровно одна текущая монета.
7/10
Исполнитель собирает монеты в матрице a[i][j], двигаясь только вправо и вниз. Какая формула вычисляет максимум монет dp[i][j] в текущей клетке?
Пояснение. Оптимальное значение складывается из награды в текущей клетке и максимума из возможных предыдущих позиций (сверху или слева).
8/10
Какое уравнение динамики используется в дискретной задаче о рюкзаке (0-1) для предмета весом w и ценностью v при вместимости W?
Пояснение. Выбирается максимум между отказом от предмета dp[i-1][W] и его взятием с добавлением ценности v к состоянию с уменьшенным весом.
9/10
Чему равна длина наибольшей возрастающей подпоследовательности для числового массива [5, 2, 8, 6, 3, 7, 9]?
Пояснение. Наибольшей возрастающей подпоследовательностью является цепочка [2, 3, 7, 9] или [2, 6, 7, 9], ее длина равна 4.
10/10
До какого минимального объема дополнительной памяти можно оптимизировать классический алгоритм расстояния Левенштейна между строками длин M и N?
Пояснение. Каждая строка матрицы редакционного расстояния зависит только от текущей и предыдущей строк, что позволяет сократить память до O(min(M, N)).
Разобрать тему перед пересдачей: разбор темы «Динамическое программирование» — примеры и типичные ошибки.
Важно. Тесты носят информационно-образовательный характер и не являются публичной офертой (ст. 437 ГК РФ) или аттестацией. Возможны неточности — сверяйтесь с официальными источниками (ФИПИ, учебники). Заметили ошибку — напишите нам.