Preview

Информатика в школе

Расширенный поиск

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

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

Просмотров: 209


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2221-1993 (Print)