Ускорение рекурсивных решений при помощи мемоизации
https://doi.org/10.32517/2221-1993-2022-21-6-55-67
Аннотация
В статье на примере решения двух задач проиллюстрирована методика изучения темы «Ускорение рекурсивных решений при помощи мемоизации» при подготовке школьников к олимпиадам по информатике. Изучение основано на последовательном решении усложняющихся задач. Для каждой задачи приводятся следующие материалы: условие задачи, идея решения с предложением придумать самостоятельно реализацию, решение на языке программирования Pascal. Серьезной технической основой является разработанная под управлением автора инструментальная система дистанционного обучения (http://dl.gsu.by), которая позволяет: предложить ученику условие задачи; отправить решение на проверку; получить от системы вердикт — правильное или неправильное решение; для неправильных решений указывается номер теста, на котором решение не прошло. Ученик может взять тест (входные и выходные данные), на котором не прошло его решение, разобраться, в чем ошибка в его программе, исправить и послать решение повторно. Кроме того, для каждой задачи есть ссылка по ней на тему в форуме, где можно задать вопрос по решению этой задачи и/или почитать ответ, если вопросы уже задавались ранее.
Об авторе
М. С. ДолинскийБеларусь
Долинский Михаил Семенович, кандидат технических наук, доцент, доцент кафедры математических проблем управления и информатики
246000, г. Гомель, ул. Советская, д. 104
Список литературы
1. Баррон Д. Рекурсивные методы в программировании. М.: Мир,1974. 79 с.
2. Бердж В. Методы рекурсивного программирования. М.: Машиностроение, 1983. 256 с.
3. Головешкин В. А., Ульянов В. В. Теория рекурсии для программистов. М.: Физматлит, 2006. 296 с.
4. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2019. 320 с.
5. Долинский М. С. Введение в решение задач с помощью рекурсивных процедур и функций // Информатика в школе. 2016. № 9. С. 49–56. EDN: XEQEZR.
6. Долинский М. С. Генерация комбинаторных объектов с помощью рекурсивных процедур и функций // Информатика в школе. 2019. № 4. С. 59–63. DOI: 10.32517/2221-1993-2019-18-4-59-63. EDN: TCJKQY.
7. Долинский М. С. Рекурсивное решение задач с помощью метода «разделяй и властвуй» // Информатика в школе. 2022. № 2. С. 58–64. DOI: 10.32517/2221-1993-2022-21-2-58-64. EDN: JOEVGG.
8. Долинский М. С. Решение задач рекурсивной генерацией чисел // Информатика в школе. 2021. № 1. С. 46–51. DOI: 10.32517/2221-1993-2021-20-1-46-51. EDN: OIHIZJ.
9. Долинский М. С. Решение игровых задач с помощью рекурсии // Информатика в школе. 2021. № 9. С. 43–50. DOI: 10.32517/2221-1993-2021-20-9-43-50. EDN: XQIAMP.
10. Долинский М. С. Решение рекурсивных задач по определению // Информатика в школе. 2020. № 2. С. 60–66. DOI: 10.32517/2221-1993-2020-19-2-60-66. EDN: EAYQZS.
11. Златопольский Д. М. 1400 задач по программированию. М.: ДМК Пресс, 2019. 192 с.
12. Луридас П. Алгоритмы для начинающих. Теория и практика для разработчика. М.: ЭКСМО, 2018. 608 с.
13. Паронджанов В. Д. Дружелюбные алгоритмы, понятные каждому. М.: ДМК Пресс, 2014. 464 с.
14. Потопахин В. В. Искусство алгоритмизации. М.: ДМК Пресс, 2013. 320 с.
15. Рафгарден Т. Совершенный алгоритм. Графовые алгоритмы и структуры данных. СПб.: Питер, 2020. 256 с.
16. Рафгарден Т. Совершенный алгоритм. Жадные алгоритмы идинамическое программирование. СПб.: Питер, 2020. 256с.
17. Рафгарден Т. Совершенный алгоритм. Основы. СПб.: Питер, 2019. 256 с.
18. Рубио-Санчес М. Введение в рекурсивное программирование. М.: ДМК Пресс, 2019. 436 с.
19. Скиена С. Алгоритмы. Руководство по разработке. СПб.: BHV, 2011. 720 c.
20. Солтис М. Введение в анализ алгоритмов. М.: ДМК Пресс, 2019. 278 с.
21. Стивенс Р. Алгоритмы. Теория и практическое применение. М.: ЭКСМО, 2016. 544 с.
22. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 2017. 320 с.
23. Castro R., Lehmann N., Pérez J., Subercaseaux B. Wavelet trees for competitive programming // Olympiad in Informatics. 2016. Vol. 10. P. 19–37.
24. Do P. T., Pham B. T., Than V. C. Latest algorithms on particular graph classes // Olympiad in Informatics. 2020. Vol. 14. P. 21–35.
25. Erdősné Németh A. Teaching graphs for contestants in lower-secondary-school-age // Olympiad in Informatics. 2017. Vol. 11. P. 41–53.
26. 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.
27. Forisek M. Towards a better way to teach dynamic programming // Olympiad in Informatics. 2015. Vol. 9. P. 45–55.
28. Manev K. Tasks on graphs // Olympiad in Informatics. 2008. Vol. 2. P. 90–104.
29. Manev K., Nikolov N., Markov M. Reconstruction of trees using metric properties // Olympiad in Informatics. 2011. Vol. 5. P. 82–91.
30. 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;(6):55-67. https://doi.org/10.32517/2221-1993-2022-21-6-55-67
For citation:
Dolinsky M.S. Speeding up recursive solutions using memoization. Informatics in school. 2022;(6):55-67. (In Russ.) https://doi.org/10.32517/2221-1993-2022-21-6-55-67