Требование эффективности решения в задачах по программированию

Современное образование требует новых подходов к обучению школьников и связано с необходимостью подготовки выпускников к активной и созидательной жизнедеятельности в новых информационных условиях. Выделим ряд проблем, с которыми сталкивается как учитель, так и учащиеся, при обучении программированию:

• -    учащиеся затрудняются с определением цели решения задачи;

• -    не могут целостно «увидеть» проблему;

• -    не замечают отдельных тонкостей, связанных с реализацией программы на конкретном языке программирования;

• -    возникают трудности с анализом собственных программ и программ одноклассников;

• -    учащиеся часто не в состоянии найти ошибки в программе;

• -    не могут разработать оптимальную (эффективную) программу для решения задачи.

Для решения возникающих проблем необходимо, чтобы учащиеся не просто шаблонно повторяли действия учителя, лишь иногда импровизируя, а мыслили и творчески подходили к решению любой проблемы или задачи. Целенаправленное развитие критического мышления позволит учащимся избежать репродуктивного уровня осмысления учебного материала, позволит им глубже проникать в суть возникающих перед ними проблем, нестандартно подходить к решению задач, а значит, поможет повысить эффективность и качество обучения программированию [1].

В тексте задач части «С» Единого Государственного Экзамена по информатике часто можно увидеть требование написать эффективную программу. В данном случае требование эффективности не является синонимом «рабочая», «правильная». Даже правильно работающая программа может быть неэффективной. Здесь перед учащимися ставится задача написать не просто рабочую программу, а именно программный код, который сможет выполняться в условиях ограниченных ресурсов [26]. Создавая код, школьники должны продемонстрировать умения распоряжаться ресурсами компьютера. Можно выделить два основных критерия эффективности алгоритма решения задач: ограничение на объем использованной памяти и ограничение на время получения решения программой.

Первый критерий предусматривает возможность программы получить решение задачи в условиях ограниченных ресурсов памяти ЭВМ.

Второй критерий напрямую связан с оптимизацией алгоритма решения задачи таким образом, чтобы наиболее быстро по времени получить ее решение. Время выполнения характеризует сложность алгоритма. Например, рассмотрим одномерный массив с количеством элементов, равным N . Если время выполнения программы линейно зависит от количества элементов массива (например, поиск минимального элемента), то сложность алгоритма обозначают O(N) . Если будем сортировать массив, используя «метода пузырька», то потребуется N² шагов, и тогда сложность алгоритма будет уже O(N²).

Эффективность алгоритма решения задачи может быть достигнута не по всем показателям, а лишь по некоторым из них. Так, например, решение может быть эффективно в использовании оперативной памяти, но не эффективно по времени выполнения алгоритма (скорости вычислений). В таких случаях выбор варианта решения зависит от того, какой параметр наиболее критичен в данной ситуации (он может определяться характеристиками оборудования, на котором будет реализовано решение задачи).

Задачи на поиск эффективных алгоритмов пользуются большим успехом у обучающихся, развивают и стимулируют их мыслительные и конструктивные способности, критическое мышление, способствуют развитию творческих способностей. Написание и использование эффективного кода позволяет не только существенно уменьшить время получения результата в задаче, но и дает возможность оптимального использования памяти, что для ряда областей практического применения отдельных алгоритмов является определяющим параметром.

Отметим, что многие задачи, являясь в формулировке достаточно простыми, могут быть решены более эффективными алгоритмами. Часто это задачи, в тексте которых количество элементов незначительно – но стоит увеличить количество элементов, как стандартный подход к решению приведет к тому, что алгоритм решения задачи сможет получить решение лишь через сотни или миллионы лет. Кажущаяся простота таких задач и является причиной того, что эффективное решение остается не найденным.

Рассмотрим формулировки нескольких задач, демонстрирующих возможности поиска и использования эффективных алгоритмов. Похожие задачи могут быть предложены при подготовке к олимпиадам.

Задача 1. Найти все пары дружественных чисел в диапазоне [a, b] или сообщить, что в указанном диапазоне таких чисел нет.

Дружественными числами называются такие два различных числа A и B, что A есть сумма натуральных делителей числа B (исключая само число B), а B есть сумма натуральных делителей числа A (исключая само число A). Например: 220 и 284 – первая пара различных дружественных чисел (делители числа 284: 1, 2, 4, 71, 142; делители числа 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110; тогда 220 есть сумма делителей числа 284, так как 220=1+2+4+71+142, а число 284 есть сумма делителей числа 220, так как 284=1+2+4+5+10+11+20+22+44+55+110).

Задача 2. Дан одномерный массив, содержащий N целых положительных элементов, причем все элементы массива парные, кроме одного. Найти непарный элемент массива.

Задача 3. Дан одномерный массив, содержащий N целых положительных элементов, причем значение каждого из элементов этого массива не менее 1 и не более N . Найти элементы массива, которые встречаются в нем ровно по одному разу.

Отметим, что задачи 2 и 3 решаются в один проход по массиву, дополнительный массив для решения не требуется.