Рекурсивное решение задач с помощью метода «разделяй и властвуй»
https://doi.org/10.32517/2221-1993-2022-21-2-58-64
Аннотация
Методика изучения темы «Рекурсивное решение задач с помощью метода “разделяй и властвуй”» при подготовке школьников к олимпиадам по информатике иллюстрируется в статье решением задачи «Голова на плечах». Решение данной задачи включает в себя несколько алгоритмов (подзадач), рассматриваемых последовательно, а именно: сортировка слиянием, подсчет количества инверсий в перестановке, количество пар пересекающихся отрезков. Изучение метода основано на последовательном решенииэтих подзадач. Для каждой подзадачи приводятся: формулировка подзадачи, идея решения с предложением придумать самостоятельно реализацию, решение на языке программирования Pascal. Серьезной технической основой является разработанная под управлением автора инструментальная система дистанционного обучения (http://dl.gsu.by), которая позволяет: предложить ученику условие задачи; отправить решение на проверку; получить от системы вердикт — правильное или неправильное решение; для неправильного решения указывается номер теста, на котором решение не прошло. Ученик может взять тест (входные и выходные данные), на котором не прошло его решение, разобраться, в чем ошибка в его программе, исправить ее и отправить решение повторно.
Об авторе
М. С. ДолинскийБеларусь
Долинский Михаил Семенович, канд. тех. наук, доцент, доцент кафедры математических проблем управления и информатики
246000, г. Гомель, ул. Советская, д. 104
Список литературы
1. Баррон Д. Рекурсивные методы в программировании. М.: Мир, 1974. 79 с.
2. Бердж В. Методы рекурсивного программирования. М.: Машиностроение, 1983. 256 с.
3. Головешкин В. А., Ульянов В. В. Теория рекурсии для программистов. М.: Физматлит, 2006. 296 с.
4. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2019. 320 с.
5. Долинский М. С. Введение в решение задач с помощью рекурсивных процедур и функций // Информатика в школе. 2016. № 9. С. 49–56.
6. Долинский М. С. Генерация комбинаторных объектов с помощью рекурсивных процедур и функций // Информатика в школе. 2019. № 4. С. 59–63.
7. Долинский М. С. Решение задач рекурсивной генерацией чисел // Информатика в школе. 2021. № 1. С. 46–51.
8. Долинский М. С. Решение игровых задач с помощью рекурсии // Информатика в школе. 2021. № 9. С. 43–50.
9. Долинский М. С. Решение рекурсивных задач по определению // Информатика в школе. 2020. № 2. С. 60–66.
10. Златопольский Д. М.1400 задач по программированию. М.: ДМК, 2019. 192 с.
11. Луридас П. Алгоритмы для начинающих. Теория и практика для разработчика. М.: ЭКСМО, 2018. 608 с.
12. Рафгарден Т. Совершенный алгоритм. Графовые алгоритмы и структуры данных. СПб.: Питер, 2020. 256 с.
13. Рафгарден Т. Совершенный алгоритм. Жадные алгоритмы и динамическое программирование. СПб.: Питер, 2020. 256 с.
14. Рафгарден Т. Совершенный алгоритм. Основы. СПб.: Питер, 2019. 256 с.
15. Рубио-Санчес М. Введение в рекурсивное программирование. М.: ДМК Пресс, 2019. 436 с.
16. Скиена С. Алгоритмы. Руководство по разработке. СПб.: BHV, 2011. 720 c.
17. Солтис М. Введение в анализ алгоритмов. М.: ДМК, 2019. 278 с.
18. Стивенс Р. Алгоритмы. Теория и практическое применение. М.: ЭКСМО, 2016. 544 с.
19. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 2017. 320 с.
20. Castro R., Lehmann N., Pérez J., Subercaseaux B. Wavelet trees for competitive programming // Olympiad in Informatics.2016. Vol. 10. P. 19–37.
21. Do P. T., Pham B. T., Than V. C. Latest algorithms on particular graph classes // Olympiad in Informatics. 2020. Vol. 14. P. 21–35.
22. Erdősné Németh A. Teaching graphs for contestants in lower-secondary-school-age // Olympiad in Informatics. 2017. Vol. 11. P. 41–53.
23. Erdősné Németh A., Zsakó L. The place of the dynamic programming concept in the progression of contestants’ thinking // Olympiad in Informatics. 2016. Vol. 10. P. 61–72.
24. Forisek M. Towards a better way to teach dynamic programming // Olympiad in Informatics. 2015. Vol. 9. P. 45–55.
25. Manev K. Tasks on graphs // Olympiad in Informatics. 2008. Vol. 2. P. 90–104.
26. Manev K., Nikolov N., Markov M. Reconstruction of trees using metric properties // Olympiad in Informatics. 2011. Vol. 5. P. 82–91.
27. Pachocki J., Radoszewskij J. Where to use and how not to use polynomial string hashing // Olympiad in Informatics. 2013. Vol. 7. P. 90–100.
Рецензия
Для цитирования:
Долинский М.С. Рекурсивное решение задач с помощью метода «разделяй и властвуй». Информатика в школе. 2022;(2):58-64. https://doi.org/10.32517/2221-1993-2022-21-2-58-64
For citation:
Dolinsky M.S. Recursive solving of the Problems using the "Divide & conquer" method. Informatics in school. 2022;(2):58-64. (In Russ.) https://doi.org/10.32517/2221-1993-2022-21-2-58-64