РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ КАК УСЛОВИЕ ФОРМИРОВАНИЯ ПРОФЕССИОНАЛЬНЫХ КОМПЕТЕНЦИЙ МАТЕМАТИКА-ПРОГРАММИСТА

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

Для ответа разобьем общее множество задач, с которыми может столкнуться математик-программист в своей профессиональной деятельности, на три условных класса:

1. Технические задачи.

2. Исследовательские задачи.

3. Технико-исследовательские задачи.

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

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

Технико-исследовательские задачи — задачи, которые располагаются на пересечении первых двух классов задач. Для этого класса характерно не только построение алгоритма, основанного на математической модели, но и преодоление различных сложностей, связанных с реализацией алгоритма. Алгоритм в этом случае будет именно математическим, поскольку не рассматривается вопрос о его технической реализации, что позволяет осуществлять его запись на формальном языке математики, не переводя на язык конкретной предметной области.

Последний класс задач представляет особый интерес, так как умение решать задачи из первых двух классов являет собой обособленные навыки умения программировать и разрабатывать алгоритмы, что в равной мере необходимы математику-программисту. Третий же класс позволяет рассматривать данные навыки не в отрыве друг от друга, но в совокупности, что позволяет в равной мере судить об их сформированности.

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

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

Приведем разбор трех задач, одна из которых («Фишка») была предложена в четвертьфинале Всемирной студенческой командной олимпиады по программированию (ACM ICPC), проходившем осенью 2015 года на базе Рыбинского Государственного авиационного технического университета им. П. А. Соловьева.

Задача «Рыба»

Условие задачи.

Мы все прекрасно знаем старинную игру Домино. Напомним кратко правила этой игры.

Стандартный набор домино включает в себя 28 костяшек. Костяшка домино представляет собой прямоугольную плитку, длина вдвое больше ширины. Её лицевая сторона разделена линией на две квадратные части. Каждая часть содержит от нуля до шести точек. Количество костяшек в домино равно количеству сочетаний с повторениями по 2 из набора 7 чисел {0, 1, 2,…, 6} и рассчитывается по формуле: (n+1)×(n+2)/2, где n – максимальное количество точек. К примеру, «стандартный» набор включает в себя (6+1)×(6+2)/2 = 28 костяшек.

Обычно игроки берут по семь костяшек. Остальные костяшки размещаются в закрытом резерве («базаре»). В процессе игры костяшки домино выкладываются в линию. После того, как первый игрок начал игру какой-либо костяшкой, следующие игроки по очереди выставляют подходящую костяшку с числом точек, совпадающим с числом точек на одном из концов линии. Если подходящих костяшек нет, то приходится добирать их из резерва.

Игра заканчивается, когда один из игроков выложит последнюю свою костяшку либо возникнет ситуация блокировки хода – так называемая «рыба»– когда на руках у игроков еще есть костяшки, но сделать ход невозможно.

Напишите программу, которая по выстроенной линии из n костяшек и количеству костяшек k и m на руках у двух игроков определит, имеет ли место в настоящий момент ситуация блокировки хода, то есть «рыба».

Разбор решения задачи.

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

Формализуя задачу, можно перефразировать ее условие следующим образом: пусть дано множество чисел A = {0, 1, 2, 3, 4, 5, 6} (исходное множество костяшек). Известны два некоторых неотрицательных числа C и D (количество костяшек на руках у игроков), а также некоторая последовательность B (выложенные костяшки) такая, что:

1. B состоит из элементов множества A.

2. Каждый элемент из A встречается не более семи раз в B.

3. Общая длина последовательности не превышает 28 элементов.

Будем считать, что последовательность является «рыбой», если выполняются следующие условия:

1. Числа C и D оба отличны от нуля.

2. Элементы, с которых начинается и заканчивается последовательность, встречаются в последовательности семь раз.

Необходимо определить, является ли последовательность B «рыбой».

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

Программная реализация функции, отвечающей за проверку последовательности на «рыбу» приведена ниже:

Листинг 1. Функция для определения, является ли последовательность «рыбой».

bool isFish(int C, int D, int sequenceLenght, int *sequence)

{ bool result = false; int entriesA[7];

  if ((C!=0)&&(D!=0)) {

    for (int i=0; i<sequenceLenght; i++)

      entriesA[sequence[i]]++;

    if ((entriesA[sequence[0]]==7)&&

       (entriesA[sequence[sequenceLenght-1]]==7))

      result = true; }

  return result; }

Рассмотрим данную функцию. Она принимает четыре параметра: целые числа C и D, которые соответствуют количеству костяшек на руках у играющих; целое число sequenceLeght, равное удвоенному количеству костяшек на столе и хранящее количество чисел в последовательности B; массив sequence, хранящий последовательность B. Сама функция возвращает значение TRUE, если последовательность является «рыбой», и FALSE в противном случае.

Переменная result хранит значение, которое возвращает функция. По умолчанию принимается, что последовательность «рыбой» не является.

В случае, если С и D отличны от нуля, заполняется вспомогательный массив, на i-ой позиции в котором хранится количество вхождений элемента i. После того, как обработаны все элементы последовательности, проверяется, максимально ли вхождение в нее крайних элементов. Если да, то последовательность является «рыбой», иначе — нет.

Задача «Мыши»

Условие задачи.

N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S-тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий порядок, в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.

Разбор решения задачи.

Заведем двумерный массив A размерности (N+M) x2. Первую строку данного массива заполним нулями, а во второй строке для i-ого элемента будем указывать элемент, следующий за данным, причем последний элемент будет указывать на первый. Таким образом, массив A будет являться кольцевым однонаправленным связным списком.

Организовав список, отсчитываем в нем S элементов, начиная с первого, причем отсчет осуществляем с помощью второй строки.

В первую строку полученного столбца помещаем единицу, что сигнализирует о том, что мышь была съедена; во вторую строку предыдущего столбца помещаем значение второй строки полученного столбца (это необходимо для исключения съеденной мыши из дальнейшего рассмотрения). Последующий отсчет осуществляем с позиции, следующей за текущей.

В общей сложности необходимо осуществить (N+M)-(K+L) таких замен, чтобы получить результирующий список, который будет находиться в одном из трех возможных состояний:

1. Первый элемент списка равен нулю и K равно нулю.

2. Первый элемент списка равен нулю и К отлично от нуля.

3. Первый элемент списка равен единице.

Рассмотрим каждое из состояний подробно.

Если первый элемент списка и К равны нулю, то исходная расстановка отсутствует, так как все мыши должны быть съедены, но первая мышь, которая, по условию, является серой, съедена не была.

Если первый элемент списка равен нулю и число К от нуля отлично, то во все позиции списка, значение которых равно единице, помещаем N-K серых и M-L белых мышей. После этого в первую ячейку помещаем серую мышь, а в остальные — белых и серых в произвольном порядке.

Если первый элемент равен единице, то в первую ячейку помещаем серую мышь, а в остальные P-1 единичных элементов в произвольном порядке расставляем N-K-1 серую и M-L белую мышь; в нулевые ячейки помещаем случайным образом оставшихся белых и серых мышей.

Описанный алгоритм может быть с успехом реализован на любом языке высокого уровня императивной парадигмы.

Задача «Фишка»

Условие задачи.

Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца.

Разбор решения задачи.

Решение задачи предполагает разложение числа N на всевозможные суммы таким образом, чтобы каждое слагаемое в сумме не превосходило k. Отметим, что таких разложений очень много, особенно если учитывать то обстоятельство, что порядок слагаемых в разложении существенен, так как он соответствует различной последовательности ходов фишки. 

Обозначим через S(i) количество различных путей, по которым фишка может пройти поле от начала до позиции с номером i. Предположим теперь, что для любого j от 1 до i известны значения величин S(j). Задача состоит в определении правила вычисления значения S(i+1), используя значения известных величин. Легко заметить, что в позицию с номером i+1 фишка может попасть из позиций i, i-1,..., i-k. Следовательно,

S(i+1)=S(i)+S(i-1)+...+S(i-k).

Таким образом, вычисляя последовательно значения величин S(1), S(2),..., S(N) по описанному выше правилу, получаем значение S(N), которое и указывает общее количество различных путей, по которым фишка может пройти поле от начала до позиции с номером N.

Листинг 2. Функция, определяющая количество различных путей.

int groupsSolution(int K, int N)

{ int *path=new int[N]; path[0]=1;

  for (int i=1; i<N; i++)

  { for (int j=1; j<=k; j++)

    { if ((i-j)>=0) { path[i]+=path[i-j]; }

      else break; }}

  return path[N-1]; }

Рассмотрим данную функцию. На первом шаге выделяется память под целочисленный массив длины N, который будет хранить значения величин S(1), S(2), … S(N). После этого в нулевую ячейку массива помещается значение 1 как количество путей, которым можно дойти до первого поля. После этого в цикле перебираются все элементы массива, каждому из которых присваивается значение S(n+1), где n — номер ячейки массива. Внутренний цикл необходим для суммирования k элементов, предшествующих текущему. Причем, данное суммирование прекращается в двух случаях — если просуммированы все k элементов или если был прибавлен нулевой элемент массива.

Функция возвращает значение S(N), записанное в ячейку S(N-1).

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

Список литературы

1. Ванькова, В. С. Задачи школьных олимпиад по информатике/ В. С. Ванькова, Ю. М. Мартынюк, С. В. Даниленко// Современные информационные технологии и ИТ-образование: Сборник избранных трудов VII Международной научно-практической конференции. – М: Фонд содействия развитию интернет-медиа, ИТ-образования, человеческого потенциала "Лига интернет-медиа", 2015. - С. 343-347.