Рекурсивное решение задач с помощью метода «разделяй и властвуй»

Abstract

Методика изучения темы «Рекурсивное решение задач с помощью метода “разделяй и властвуй”» при подготовке школьников к олимпиадам по информатике иллюстрируется в статье решением задачи «Голова на плечах». Решение данной задачи включает в себя несколько алгоритмов (подзадач), рассматриваемых последовательно, а именно: сортировка слиянием, подсчет количества инверсий в перестановке, количество пар пересекающихся отрезков. Изучение метода основано на последовательном решении этих подзадач. Для каждой подзадачи приводятся: формулировка подзадачи, идея решения с предложением придумать самостоятельно реализацию, решение на языке программирования Pascal. Серьезной технической основой является разработанная под управлением автора инструментальная система дистанционного обучения (http://dl.gsu.by), которая позволяет: предложить ученику условие задачи; отправить решение на проверку; получить от системы вердикт — правильное или неправильное решение; для неправильного решения указывается номер теста, на котором решение не прошло. Ученик может взять тест (входные и выходные данные), на котором не прошло его решение, разобраться, в чем ошибка в его программе, исправить ее и отправить решение повторно.