Ускорение рекурсивных решений при помощи мемоизации

Abstract

В статье на примере решения двух задач проиллюстрирована методика изучения темы «Ускорение рекурсивных решений при помощи мемоизации» при подготовке школьников к олимпиадам по информатике. Изучение основано на последовательном решении усложняющихся задач. Для каждой задачи приводятся следующие материалы: условие задачи, идея решения с предложением придумать самостоятельно реализацию, решение на языке программирования Pascal. Серьезной технической основой является разработанная под управлением автора инструментальная система дистанционного обучения (http://dl.gsu.by), которая позволяет: предложить ученику условие задачи; отправить решение на проверку; получить от системы вердикт — правильное или неправильное решение; для неправильных решений указывается номер теста, на котором решение не прошло. Ученик может взять тест (входные и выходные данные), на котором не прошло его решение, разобраться, в чем ошибка в его программе, исправить и послать решение повторно. Кроме того, для каждой задачи есть ссылка по ней на тему в форуме, где можно задать вопрос по решению этой задачи и/или почитать ответ, если вопросы уже задавались ранее. = 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.