Speeding up recursive solutions using memoization
https://doi.org/10.32517/2221-1993-2022-21-6-55-67
Abstract
In the article, using the example of solving two problems, the methodology for studying the theme "Speeding up recursive solutions using memoization" is illustrated in preparing schoolchildren for Olympiads in informatics. The study is based on the sequential solution of increasingly complex problems. For each problem the following materials are given: the formulation of the problem, 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 (http://dl.gsu.by) is the effective technical base for teaching. The system allows to offer for a student a formulation of the problem; 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. In addition, for each problem there is a link on it to the topic in the forum at site, where you can ask a question onsolving this problem and / or read the answer if the questions have already been asked before.
References
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.
Review
For citations:
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