Методы решения олимпиадных задач: от простого перебора к динамическому программированию
Цели и задачи
- Цель: сформировать навык оптимизации алгоритмов от полного перебора к методу динамического программирования на примере задачи о поиске количества путей.
- Образовательная задача: изучить принцип декомпозиции задачи и использования результатов решения подзадач.
- Развивающая задача: развивать алгоритмическое мышление и умение анализировать вычислительную сложность алгоритма.
- Воспитательная задача: формировать культуру командной работы и уверенность при решении нестандартных интеллектуальных задач.
Планируемые результаты
Личностные
- Готовность к саморазвитию и самообразованию в области информационных технологий.
- Умение конструктивно реагировать на ошибки в коде и находить способы их исправления.
- Интерес к олимпиадному движению как способу профессионального самоопределения.
Метапредметные
- Умение устанавливать причинно-следственные связи и строить логическое рассуждение.
- Навык формализации условия задачи и создания математической модели.
- Умение эффективно работать в паре, распределяя роли при написании и отладке кода.
Предметные
- Знание понятия динамического программирования и его отличия от рекурсии.
- Умение писать программный код на языке программирования (Python/C++) для решения комбинаторных задач.
- Владение навыком оценки эффективности алгоритма по времени выполнения.
Универсальные учебные действия (УУД)
Личностные УУД
- Формирование ответственного отношения к учению, способности к преодолению трудностей в интеллектуальной деятельности.
Регулятивные УУД
- Самостоятельное планирование путей достижения целей, осознанный выбор наиболее эффективных способов решения задач.
Познавательные УУД
- Выбор оснований и критериев для классификации алгоритмов, синтез как составление целого из частей.
Коммуникативные УУД
- Умение аргументировать свою точку зрения при выборе алгоритма в паре, владение устной и письменной речью.
Подготовка учителя к уроку
- Подготовить презентацию с визуализацией дерева рекурсии и таблицы динамики.
- Распечатать карточки с условиями задач (3 уровня сложности) — 15 комплектов (по одному на парту).
- Проверить работоспособность среды программирования (IDLE Python или VS Code) на 15 рабочих станциях.
- Загрузить на школьный сервер файлы-шаблоны для практической работы.
- Подготовить секундомер для демонстрации разницы в скорости работы алгоритмов.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: создать эмоциональный настрой и заинтересовать учеников олимпиадным программированием.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | «Здравствуйте, будущие чемпионы олимпиад! Сегодня мы не просто изучаем информатику, мы учимся думать как архитекторы алгоритмов. Представьте, что вы создаете навигатор для марсохода. У него ограничен заряд батареи и слабый процессор. Если ваш алгоритм будет думать слишком долго, марсоход просто застрянет. Сегодня мы узнаем, как заставить компьютер решать задачи, на которые у обычного алгоритма ушли бы годы, всего за доли секунды. Готовы взломать систему?» | Приветствуют учителя, проверяют наличие тетрадей и доступ к компьютерам. Включаются в диалог, обсуждая важность скорости работы программ в реальных устройствах. |
Завершение этапа: учитель подводит итог: «Отлично, вижу азарт в глазах. Но прежде чем строить ракету, нужно проверить фундамент — вспомним, как мы обычно решаем задачи на перебор путей.»
Этап 2. Актуализация знаний и фиксация затруднения (7 мин)
Цель этапа: актуализировать знания о рекурсии и выявить проблему экспоненциального роста сложности.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | «Давайте вспомним классическую задачу о Кузнечике. Он стоит в точке 1 и хочет попасть в точку N. Прыгать может на +1 кочку или на +2. Если N=5, сколько способов? Давайте нарисуем дерево вариантов на доске. Кто поможет?» Учитель рисует корень дерева (5) и ветви к (4) и (3). | Ученики диктуют варианты: «Из 5 мы могли прийти из 4 или 3. Из 4 — из 3 или 2...». Один ученик у доски дорисовывает дерево до единиц. |
3 мин | «А теперь представьте, что кочек не 5, а 50. Посмотрите на экран (слайд с огромным деревом). Сколько времени будет считать компьютер, если для каждой кочки мы будем заново строить такое дерево? Я запускаю код с рекурсией для N=40. Смотрите на таймер... Программа зависла! Почему?» | Наблюдают за выполнением кода. Высказывают предположения: «Компьютер делает много лишней работы», «Он много раз считает одно и то же для маленьких чисел». Фиксируют проблему: рекурсия слишком медленная для больших N. |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Запись в тетрадях
Задача: Кузнечик (1 -> N, шаги +1, +2). Рекурсивная формула: K(n) = K(n-1) + K(n-2). Проблема: избыточность вычислений.
Завершение этапа: учитель подводит итог: «Мы увидели, что компьютер делает одну и ту же работу тысячи раз. Как нам заставить его запоминать уже решенные задачи? Встречайте — динамическое программирование!»
Этап 3. Открытие нового знания (10 мин)
Цель этапа: объяснить принцип заполнения таблицы (снизу-вверх) как альтернативу рекурсии.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | «Принцип динамики прост: не считай заново, а посмотри в шпаргалку. Давайте создадим массив (список), где в ячейке i будет храниться количество способов попасть на кочку i. На первую кочку — 1 способ (мы там стоим). На вторую — тоже 1 (прыжок +1). А на третью? Мы можем прийти с первой или со второй. Значит, складываем значения из ячеек 1 и 2. Посмотрите на доску, я заполняю таблицу.» Учитель рисует таблицу на 10 ячеек. | Следят за логикой заполнения. Вычисляют значения в уме: «Для 4-й кочки: 1+2=3», «Для 5-й: 2+3=5». Осознают, что это последовательность Фибоначчи. |
5 мин | «Теперь переведем это на язык Python. Нам нужен цикл, который идет от 3 до N и просто складывает два предыдущих элемента массива. Я запускаю этот код для N=100. Смотрите!» Учитель демонстрирует мгновенный результат на экране. | Сравнивают скорость. Записывают базовый шаблон кода: dp = [0]*(n+1); dp[1]=1; dp[2]=1; for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2]. |
Эталон решения (Python)
n = int(input())
dp = [0] * (n + 1)
dp[1] = 1
if n > 1:
dp[2] = 1
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])
Завершение этапа: учитель подводит итог: «Теперь у вас есть суперсила. Но олимпиадные задачи коварны. Что если на пути кузнечика есть ловушки? Давайте проверим это в парах.»
Этап 4. Первичное закрепление и работа в парах (10 мин)
Цель этапа: применить метод динамики к модифицированной задаче (с запрещенными состояниями).
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | «Инструктаж: работаем в парах. Перед вами карточка с задачей 'Кузнечик-сапер'. Кочки №7 и №13 заминированы, на них наступать нельзя. Как изменится наш алгоритм? Обсудите идею 1 минуту, затем приступайте к реализации на компьютерах.» | Разворачиваются друг к другу, обсуждают. Выдвигают гипотезу: «В ячейках 7 и 13 нужно просто поставить 0 способов, тогда они не добавят ничего к следующим суммам». Садятся за ПК. |
8 мин | Учитель проходит между рядами, консультирует. Применяет приём «Две звезды и пожелание» для тех, кто уже написал код: просит пары поменяться местами и оценить код соседа. | Пишут код, вводят данные, проверяют результат. Взаимодействуют с напарником: один пишет код, второй проверяет логику (парное программирование). |
Завершение этапа: учитель подводит итог: «Вы справились с минами! Как видите, динамика легко адаптируется под любые условия. Пора проверить ваши силы в индивидуальном зачете.»
Этап 5. Самостоятельная работа с самопроверкой (10 мин)
Цель этапа: индивидуальная проверка усвоения метода на более сложной задаче (3 варианта прыжка).
Время | Действие учителя | Действие учеников |
|---|---|---|
7 мин | «Индивидуальное задание: Кузнечик умеет прыгать на +1, +2 и +3. Найдите количество способов добраться до кочки №15. Внимание на экран: там появится эталонный ответ через 7 минут. Работаем самостоятельно.» | Каждый ученик самостоятельно пишет программу. Те, кто закончил раньше, получают бонусную задачу: «Минимизировать стоимость пути (каждая кочка стоит денег)». |
3 мин | Выводит на экран правильный ответ и код. «Сверьте свои результаты. Если у вас получилось 927 — вы всё сделали верно. Если нет — посмотрите на формулу: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. Где могла закрасться ошибка?» | Сверяют код с эталоном. Проводят самоанализ. Поднимают руки те, у кого ответ совпал. |
Завершение этапа: учитель подводит итог: «Ошибки в индексах — это нормально для первого раза. Главное, что вы поняли принцип накопления результата.»
Этап 6. Рефлексия и домашнее задание (5 мин)
Цель этапа: осознание метода и постановка задач на будущее.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | «Подведем итоги. Мы использовали приём 'KWL'. В начале урока мы 'Знали' рекурсию, 'Хотели узнать' как ускорить код. Что мы 'Узнали' теперь? Заполните короткую анкету на выходе. И запишите домашнее задание — оно на выбор, как вы любите.» | Заполняют билеты на выход. Записывают ДЗ. Обсуждают, какой уровень сложности выберут. |
Критерии оценивания практической работы
- «5» — программа работает корректно, учтены все условия (включая ловушки), код структурирован и прокомментирован.
- «4» — алгоритм верный, но допущена ошибка в индексации массива или не обработан случай N=1.
- «3» — понятна идея динамического программирования, но код содержит синтаксические ошибки и не запускается.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
В какой момент вы поняли, что таблица лучше дерева? | Осознание преимущества динамического программирования. |
Что было сложнее: придумать формулу или написать код? | Выявление индивидуальных затруднений (логика vs синтаксис). |
Сможете ли вы объяснить этот метод другу, который пропустил урок? | Проверка глубины понимания материала. |
Завершающее слово учителя
«Сегодня вы сделали первый шаг в мир серьезных алгоритмов. Динамическое программирование — это база для задач на биоинформатику, экономику и искусственный интеллект. Если сегодня вам было сложно — это отлично, значит, мозг рос. На следующем уроке мы разберем задачу о Роботе в двумерной сетке. Будет еще интереснее. До встречи!»
Домашнее задание
Уровень сложности | Задания | Описание |
|---|---|---|
Базовый (обязательный) | Задача 'Лестница' | Ученик поднимается по лестнице. За шаг можно пройти 1 или 2 ступеньки. На каждой ступеньке лежит монета. Найти максимальную сумму монет. |
Средний (повышающий) | Задача 'Черепашка' | Реализовать задачу о поиске количества путей в прямоугольной таблице 5х5 (движение только вправо и вниз). |
Продвинутый (дополнительный) | Codeforces / Informatics | Решить задачу №203 (Дипломы) на любом онлайн-судье, используя метод динамики. |