При изучении программирования как в школе, так и в вузе, предпочтение в основном отдается стандартным задачам, решение которых в большинстве случаев оказывается очевидным. Однако часть таких задач может быть решена более оптимальными способами, которые, чаще всего, так и остаются не найденными. В статье на примерах рассматриваются вопросы поиска и реализации эффективных алгоритмов при решении некоторого класса задач в процессе обучения программированию. Под эффективностью алгоритма понимается выполнение требований по минимальному использованию памяти программой (в рамках условия задачи) и быстроте работы алгоритма. Рассматриваемые в статье задачи с успехом использовались автором для проведения дистанционной олимпиады по программированию среди студентов физико-математических и технических профилей. Исходные коды программ приведены на языке программирования С++.
программирование, эффективный алгоритм, конструктивное мышление, разработка программы.
В большинстве случаев при обучении программированию, как в школе, так и в вузе, редко обращается внимание на поиск наиболее эффективных решений той или иной задачи. По крайней мере, этот вопрос обычно не рассматривается, если предложенный алгоритм решения задачи дает более-менее хорошие результаты в плане скорости вычислений (при этом, зачастую, об экономии памяти речи вообще не идет).
Однако многие задачи, даже являющиеся достаточно простыми, могут быть решены более эффективными алгоритмами. Простота таких задач, очевидно, и является причиной того, что решение, не лежащее на поверхности, а требующее некоторых мыслительных операций, так и остается не найденным.
Рассмотрим несколько задач, демонстрирующих возможности использования эффективных алгоритмов. Похожие задачи могут быть предложены при обучении программированию как олимпиадные задачи, причем в условиях оценки задач такой олимпиады должно быть обязательно указано, что максимальный балл будет давать именно оригинальный эффективный алгоритм.
Так, например, была организована олимпиада по программированию в дистанционной форме среди студентов физико-математического факультета продолжительностью шесть дней. Задания (по одному в день) высылались участникам ежедневно в одно и то же определенное положением о проведении олимпиады время на адреса электронной почты, и в течение двух часов участник должен был прислать решение. При подведении итогов олимпиады оценивалась эффективность использования оперативной памяти, скорость работы алгоритма, его оригинальность и, конечно же, время решения задачи участником. Результаты олимпиады показали, что только около 20% студентов смогли предложить эффективные алгоритмы решения некоторых задач. Стоит отметить, что при проведении дистанционной олимпиады необходимо придумывать новые задачи, не встречающиеся в сети Интернет, а также активно использовать при проверке решений программы, позволяющие выявить плагиат решения (например, система eTXT Антиплагиат).
1. Дмитриев В.Л. Теория и практика программирования на С++. - Стерлитамак: РИО СФ БашГУ, 2013. - 308 с.
2. Дмитриев В.Л., Ахмадеева Р.З. Развитие конструктивного мышления при изучении программирования // Информатика и образование. - 2009. - № 2. - С. 69-73.
3. Окулов С.М. Программирование в алгоритмах. - М.: БИНОМ. Лаборатория знаний, 2002. - 341 с.
4. Stroustrup Bjarne. The C++ programming language / Bjarne Stroustrup. - Fourth edition. - Boston: Addison-Wesley, 2013. - 1368 p.
