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

Abstract

Методика изучения темы «Рекурсивное решение задач с помощью метода “разделяй и властвуй”» при подготовке школьников к олимпиадам по информатике иллюстрируется в статье решением задачи «Голова на плечах». Решение данной задачи включает в себя несколько алгоритмов (подзадач), рассматриваемых последовательно, а именно: сортировка слиянием, подсчет количества инверсий в перестановке, количество пар пересекающихся отрезков. Изучение метода основано на последовательном решении этих подзадач. Для каждой подзадачи приводятся: формулировка подзадачи, идея решения с предложением придумать самостоятельно реализацию, решение на языке программирования Pascal. Серьезной технической основой является разработанная под управлением автора инструментальная система дистанционного обучения (http://dl.gsu.by), которая позволяет: предложить ученику условие задачи; отправить решение на проверку; получить от системы вердикт — правильное или неправильное решение; для неправильного решения указывается номер теста, на котором решение не прошло. Ученик может взять тест (входные и выходные данные), на котором не прошло его решение, разобраться, в чем ошибка в его программе, исправить ее и отправить решение повторно/ = The methodology for studying the theme "Recursive solving of the problem using the "divide & conquer" method" in preparing schoolchildren for Olympiads in informatics is illustrated in the article by solving the "Head on shoulders" problem. The solution of this problem includes several algorithms (subtasks) considered sequentially, namely: merge sort, counting the number of inversions in a permutation, the number of pairs of intersecting segments. The study of the method is based on the sequential solution of these subtasks. For each subtask, the following materials are given: the formulation of the subtask, the idea of a solution with a proposal to come up with an implementation on their own, the solution in the Pascal programming language. Distance learning system DL.GSU. BY is the effective technical base for teaching. The system allows to offer for a student a formulation of the task; to submit the solution for review; to get a verdict from the system — a correct or incorrect solution; for incorrect solution, the number of the test on which the solution did not pass is indicated. A student can take a test (input and output data), on which his solution did not pass, figure out what the error is in his program, correct and send the solution again.