Both at school and at higher educational institutions the priority generally is given to standard mathematical problems, which in most cases seem to have quite evident solutions. However some of these problems can be solved in more optimal ways, which are often not been found at all. Based on a range of examples the paper considers how to seek and apply efficient algorithms when solving a specific class of problems in the course of programming teaching. The algorithm efficiency is meant that the program (as far as the current problem specifications require) meets requirements of minimal memory use and certain speed of algorithms. The author has successfully used the problems discussed in the paper for running the distant programming competition among students of physical-mathematical and engineering profiles. Source codes for the programs discussed are indicated in terms of C++ programming language.
programming, efficient algorithm, possibility thinking, software engineering.
В большинстве случаев при обучении программированию, как в школе, так и в вузе, редко обращается внимание на поиск наиболее эффективных решений той или иной задачи. По крайней мере, этот вопрос обычно не рассматривается, если предложенный алгоритм решения задачи дает более-менее хорошие результаты в плане скорости вычислений (при этом, зачастую, об экономии памяти речи вообще не идет).
Однако многие задачи, даже являющиеся достаточно простыми, могут быть решены более эффективными алгоритмами. Простота таких задач, очевидно, и является причиной того, что решение, не лежащее на поверхности, а требующее некоторых мыслительных операций, так и остается не найденным.
Рассмотрим несколько задач, демонстрирующих возможности использования эффективных алгоритмов. Похожие задачи могут быть предложены при обучении программированию как олимпиадные задачи, причем в условиях оценки задач такой олимпиады должно быть обязательно указано, что максимальный балл будет давать именно оригинальный эффективный алгоритм.
Так, например, была организована олимпиада по программированию в дистанционной форме среди студентов физико-математического факультета продолжительностью шесть дней. Задания (по одному в день) высылались участникам ежедневно в одно и то же определенное положением о проведении олимпиады время на адреса электронной почты, и в течение двух часов участник должен был прислать решение. При подведении итогов олимпиады оценивалась эффективность использования оперативной памяти, скорость работы алгоритма, его оригинальность и, конечно же, время решения задачи участником. Результаты олимпиады показали, что только около 20% студентов смогли предложить эффективные алгоритмы решения некоторых задач. Стоит отметить, что при проведении дистанционной олимпиады необходимо придумывать новые задачи, не встречающиеся в сети Интернет, а также активно использовать при проверке решений программы, позволяющие выявить плагиат решения (например, система eTXT Антиплагиат).
1. Dmitriev V.L. Teoriya i praktika programmirovaniya na C++ [Theory and practice of C++ programming]. Sterlitamak, RIO SF BashGU Publ., 2013. 308 p.
2. Dmitriev V.L., Akhmadeeva R.Z. Development of constructive thinking in the study of programming. Informatika i obrazovanie [Computer science and education], 2009. I. 2, pp. 69-73. (in Russian)
3. Okulov S.M. Programmirovanie v algoritmakh [Programming algorithms]. Moscow, BINOM. Laboratorija znanij Publ., 2002. 341 p.
4. Stroustrup Bjarne. The C++ programming language. Fourth edition. Boston, Addison-Wesley, 2013. 1368 p.
