РЕШЕНИЕ ЗАДАЧ ПОВЫШЕННОЙ СЛОЖНОСТИ ПО ПРОГРАММИРОВАНИЮ
Раздел: Материалы I Всероссийской очно-заочной научно-практической конференции «Проблемы и перспективы современного физико-математического, информационного и технологического образования» (Новокузнецк, февраль 2017)
Журнал: ИКТ в системах образования, социально-психологическая подготовка специалиста
26 апреля 2017 г.
Авторы: Можаров Максим Сергеевич , Густяхин Андрей Евгеньевич
УДК 37.016:004.42
М. С. Можаров, А. Е. Густяхин
Можаров Максим Сергеевич, канд. пед. наук, профессор, заведующий кафедрой ТиМПИ НФИ КемГУ, г. Новокузнецк.
Густяхин Андрей Евгеньевич, студент 4 курса ФМиТЭФ НФИ КемГУ, г. Новокузнецк.
РЕШЕНИЕ ЗАДАЧ ПОВЫШЕННОЙ СЛОЖНОСТИ ПО ПРОГРАММИРОВАНИЮ
Аннотация. В статье анализируется проблема подготовки школьников к олимпиаде по программированию, рассматриваются классификации задач повышенной сложности с примерами формулировок по каждому разделу. Автор поднимает проблему недостаточности практических педагогических инструментов, учебников и методик.
Ключевые слова: программирование, задачи повышенной сложности, классификация олимпиадных задач.
Программирование – один из самых сложных разделов информатики, как школьной, так и вузовской. Междисциплинарный характер знаний и умений, привлекаемых к решению учебных задач, собственный язык, сложные языковые конструкции и иерархи, необходимость длительных периодов сосредоточенности делают обучение программированию сложной методической задачей.
Работа с одаренными учащимися является важной задачей образования. Практика показывает, что важнейшим направлением такой работы выступает подготовка детей к предметным олимпиадам. Педагог, решая эту задачу, сталкивается с недостатком содержания обучения, его постоянным обновлением и, несмотря на большую представленность различных материалов в Интернете, с отсутствием подходящих для этого форм и методов обучения.
Олимпиады по программированию в современной мировой образовательной практике занимают одно из ведущих мест, в связи с интенсивным развитием информационных технологий и востребованностью специалистов в данной области. Конкурсы и олимпиады по программированию проводятся на школьном, вузовском, государственном уровнях. Крупные корпорации проводят собственные он-лайн олимпиады по программированию для школьников и студентов.
При подготовке будущих учителей информатики большое внимание уделяется не только обучению программированию – теории и практике решения алгоритмических задач в системе профильных курсов, но и обучению студентов формированию содержания, подбору форм и методов в курсе методики обучения информатике. Ведь участие в олимпиадах позволяет развивать творческие способности школьников и обеспечивает высокую мотивацию к образовательной деятельности.
Исторически олимпиада по информатике – это олимпиада по программированию, которая предполагает наличие обширных познаний в математике, физике и других областях, также владение технологией решения алгоритмических задач на языке программирования.
Решение задач повышенной сложности позволяет раскрыть творческий потенциал школьника во время подготовки к олимпиаде, учитывая возрастные особенности ребенка и перспективу его развития. Использование многоуровневых олимпиадных задач позволяет школьникам применить свой творческий потенциал, независимо от уровня подготовки.
Для формирования содержания подготовки к решению задач повышенной сложности по программированию учителю важно иметь классификацию задания. Как показывает практика, таких классификаций существует множество, и это связано, в большей степени, с междисциплинарностью текстовых формулировок (геометрические, алгебраические, стохастические, физические и т. д.), а также классификацией методов и алгоритмов их решения (поиск, сортировка, очереди и стеки, обход деревьев, разделение графов и т. д.).
Приведем в качестве примера одну из классификаций олимпиадных задач, а также примеры формулировок задач из разделов данной классификации:
- Арифметика – математические задачи, работа с большими числами (длинная арифметика), такие задачи, как правило, требуют знания формул, умение их применять, а код программ может быть небольшим.
Примеры:
Задача 1. Число вводится своим двоичным представлением (длина числа не превышает 10000 двоичных разрядов). Необходимо определить, делится ли число на 15.
Задача 2. Дан массив X(100) и Y(100). Записать алгоритм, меняющий последовательно местами значения элементов X(k) и Y(k) для этих таблиц, для k=1,2,...,100, не используя промежуточных переменных.
- Геометрия – геометрические задачи, здесь может быть описана какая-либо ситуация взаимодействия тел на плоскости и в пространстве.
Примеры:
Задача 1. На плоскости заданы две точки A(x1,y1) и B(x2,y2). Определить, какой из отрезков - OA или OB образует больший угол с осью OX.
Задача 2. Многоугольник на плоскости задается координатами своих N вершин в порядке обхода их по контуру по часовой стрелке. Считается, что контур самопересечений не имеет. Найти площадь, периметр и углы многоугольника.
- Динамическое программирование – задачи, направленные на выявление рекуррентных соотношений.
Примеры:
Задача 1. Написать программу определения количества шестизначных «счастливых» билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр.
Задача 2. У покупателя есть n монет достоинством H(1), ..., H(n). У продавца есть m монет достоинством B(1), ..., B(l). Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима)?
- Сортировка и последовательности – работа с данными, представленными в виде массива.
Примеры:
Задача 1. Задается словарь. Найти в нем все анаграммы (слова, составленные из одних и тех же букв).
Задача 2. В музее регистрируется в течение дня время прихода и ухода каждого посетителя. Таким образом, за день получены N пар значений, где первое значение в паре показывает время прихода посетителя и второе значения – время его ухода. Найти промежуток времени, в течение которого в музее одновременно находилось максимальное число посетителей.
- Графы – задачи с графами (структурами данных, основанных на вершинах и ребрах).
Примеры:
Задача 1. Найти кратчайшее расстояние между двумя вершинами в графе. Найти все возможные пути между этими двумя вершинами в графе, не пересекающиеся по: а) ребрам; б) вершинам.
Задача 2. Имеется N человек и прямоугольная таблица А[1:N,1:N]; элемент A[i,j] равен 1, если человек i знаком с человеком j, А[i,j] = А[j,i]. Можно ли разбить людей на две группы, чтобы в каждой группе были только незнакомые люди?
- Рекурсия – задачи на поиск с рекурсивным перебором вариантов.
Примеры:
Задача 1. В заданной последовательности целых чисел найти максимально длинную подпоследовательность чисел, такую, что каждый последующий элемент подпоследовательности делился нацело на предыдущий.
Задача 2. Вводится три неотрицательных числа d, i, c и две строки X и Y. Найти преобразование строки X в Y минимальной стоимости. Допустимы следующие три операции:
- удалить любой символ из X (стоимость операции d);
- вставить любой символ в X (стоимость операции i);
- заменить символ в X на произвольный (стоимость операции e).
К наиболее распространённым формам организации задач по программированию повышенной сложности относят индивидуальное решение задач и командное решение задач; решение задач при помощи преподавателя и самостоятельное решение, организацию соревнований на специализированных веб-сайтах, использование проектной деятельности при исследовании и описании предметных областей, а также решение задач в виртуальных средах.
К известным методам подготовки детей к решению задач повышенной сложности, наряду с традиционными, относят метод проектов, парное обучение, мозговой штурм, использование виртуальных и игровых контекстов и др.
В имеющейся литературе по данному вопросу, как правило, приводится набор задач, теория по алгоритмическому методу и решение. Педагогическим, методическим вопросам уделяется явно недостаточное внимание.
Отсутствие современных учебников по методике обучения школьников решению олимпиадных задач по программированию затрудняет подготовку будущих учителей к данному виду деятельности. И, несмотря на большую представленность материалов по данной проблеме в Интернете, подбор содержания, форм и методов подготовки школьников в данном направлении – неординарная задача для учителя.
Список литературы
- Кормышов, М. Д. Всероссийские олимпиады школьников Красноярского края по информатике. 2005–2006 учебный год [Текст] : учеб.-метод. пособие / М. Д. Кормышов, Н. В. Лалетин. – Красноярск, 2010. – 123 с.
- Олимпиадные задачи по программированию [Электронный ресурс]. – Режим доступа : http://algolist.manual.ru/olimp/