Динамическое программирование решает задачу, сохраняя ответы подзадач. Игры с полной информацией анализируют тем же способом — от конечных позиций к начальной. Графический интерфейс строится на событиях и обработчиках.
Что нужно знать
- Схема ДП: подзадача → рекуррентное соотношение → базовые значения → порядок заполнения таблицы → ответ.
- Фибоначчи таблицей: f[1] = f[2] = 1, f[i] = f[i − 1] + f[i − 2] — линейно; наивная рекурсия — экспоненциально. Мемоизация: functools.lru_cache.
- Исполнитель «+1, *2» из 1 в n: f(n) = f(n − 1) + (f(n // 2), если n чётное), f(1) = 1; заполнять от меньших к большим.
- Пути по полю вправо/вниз: путей в клетку = путей слева + путей сверху; первые строка и столбец — единицы.
- Оптимальный путь: best[i][j] = клетка + max(best[i − 1][j], best[i][j − 1]).
- Игры: позиция проигрышная, если все ходы ведут в выигрышные; выигрышная, если есть ход в проигрышную. В игре «бери 1 или 2» проигрышны кратные 3.
- GUI на Tkinter: виджеты (Button, Label, Entry), обработчик — функция; command=имя_функции без скобок; widget.bind('<KeyPress>', f); root.mainloop() — цикл событий.
- Событийная программа не идёт сверху вниз: порядок выполнения определяют действия пользователя.
Где чаще всего ошибаются
- Заполнять таблицу ДП в порядке, при котором нужные значения ещё не посчитаны.
- Забывать базовые значения или ставить f(1) = 0.
- Писать command=on_click() — функция срабатывает один раз при запуске.
- Определять выигрышность позиции только по одному возможному ходу, а не по всем.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Алгоритмы и структуры данных · 9 класс · Динамическое программирование, игры и графический интерфейс