Методические рекомендации по подготовке обучающихся к решению олимпиадных заданий для учащихся

Методические рекомендации по подготовке обучающихся к решению заданий для учащихся 5-8 класс

Если задача задана, то тут же возникает вопрос: с чего начать ее решение? Можно выделить следующие этапы, которые присущи процессу решения большинства олимпиадных задач:

• Разбор условия задачи.

• Формализация условия задачи.

• Разработка алгоритма решения задачи.

• Программная реализация алгоритма.

• Отладка и тестирование программы. Отправка решения на проверку.

1. Разбор условия задачи

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

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

1. Формализация условия задачи.

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

1. Разработка алгоритма решения задачи

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

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

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

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

1. Программная реализация алгоритма

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

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

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

1. Отладка и тестирование программы

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

5 класс

Задача 1. В таблице разрешается переставлять местами любые две строки друг с другом и любые два столбца. Можно ли с помощью нескольких таких операций получить из левой таблицы правую? Если да, то приведите набор операций, содержащий минимальное число операций перестановки. Если нет — то объясните почему.

Решение

Нужный результат достигается, например, выполнением следующих команд:

1. Поменять столбцы 1 и 3.

2. Поменять строки 1 и 3.

3. Поменять столбцы 2 и 3.

Начальное состояние

Шаг 1

Шаг 2

Шаг 3

Критерии оценивания

5 баллов – правильный ответ и приведен набор операций из трех шагов.

3 балла – правильный ответ и приведен набор операций из более чем трех шагов.

0 баллов – остальные случаи.

Памятка решения олимпиадных задач по информатике

для учащихся 9-11 классов

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

Далее можно скопировать эту заготовку столько раз, сколько задач предложено на туре, и сразу назвать каждый файл так, как это требуется по условиям олимпиады. В результате вам не придется при переходе от решения одной задачи к другой начинать работу с нуля (а попытка править текст с решением одной задачи для ускорения набора текста другой ведет только к порождению ошибок, на исправление которых будет потрачено гораздо больше времени). В разделе OPTIONS|enviroment|preferences среды программирования Турбо Паскаль полезно установить параметр Auto save [X]Editor Files (автосохранение редактируемых файлов). Это гарантирует автоматическое сохранение текста программы при каждом ее запуске. Таким образом, если, например, программа зависнет и среду программирования придется запускать заново, то результат последнего редактирования будет сохранен (к сожалению, во время тура школьники зачастую забывают самостоятельно время от времени запоминать сделанные ими изменения в тексте программ).

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

Если вы приступили к решению конкретной задачи и основная структура данных для нее вам ясна, то можно описать основные глобальные переменные и набить процедуру readdata ввода данных, чтобы она считывала все параметры задачи так, как это указано в условии. Если не оговорено иное, то делать формальную проверку считанных данных, то есть проверять соответствие введенных значений переменных условию задачи не нужно (!). Объясняется это тем, что, по правилам проведения большинства олимпиад последних лет, считается, что все входные данные при тестировании будут корректны. Кроме того, заметим, что при считывании из файла чисел обычно следует использовать только процедуру read (а не readln), для случаев же считывания символов и строк (тип string) это не так. Если количество чисел во входном файле неизвестно, то нужно использовать функцию seekeof вместо eof для проверки условия окончания считывания чисел. Для файлов, содержащих произвольный текст, это опять же уже не так.

В процедуре initial следует обнулить или присвоить соответствующие начальные значения всем (!) глобальным переменным, за исключением тех, которые будут использоваться в качестве параметров циклов. Затем запрограммировать вывод результата в процедуре outdata так, как это требуется в условии задачи. Это поможет дальнейшей отладке программы, и в дальнейшем не потребуется “простой” вывод переделывать в “правильный”. Таким образом, к этому моменту у вас уже должна быть “работающая” программа. Она, по крайней мере, должна компилироваться, считывать данные и выводить результат, пусть и нулевой, но в нужном формате. Еще одна типичная ошибка из данного класса — задание временных имен для входных и выходных файлов, и как результат, не работающая с точки зрения автоматической системы проверки программа.

5) При выполнении пунктов 3, 4 данной памятки или после следует подумать над подходами к решению задачи, для чего ответить себе на ряд вопросов и проделать ряд действий.

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

- Определить, относится ли данная задача к знакомому вам классу, или решение придется искать “с нуля”.

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

9-11 класс

Задача 2. Часовые пояса

Таня решила позвонить своей подруге, но вспомнила, что та живёт очень далеко, поэтому в часовом поясе подруги может быть слишком поздно или рано. Часы у Тани показывают ровно H часов, Таня живёт в часовом поясе UTC+A, а её подруга – в часовом поясе UTC+B. Помогите Тане определить время в часовом поясе подруги в этот момент.

Программа получает на вход три целых числа H, A и B, 0 ≤ H ≤ 23, −11 ≤ A ≤ 12, −11 ≤ B ≤ 12.

В часовом поясе UTC+A местное время больше, чем время в часовом поясе UTC+0 на A часов (если же A

Программа должна вывести одно число – время (количество часов) в часовом поясе подруги.

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

Пример входных и выходных данных

Решение

Если в часовом поясе UTC+A время H часов, то в поясе UTC+0 время H − A, а в часовом поясе UTC+B время будет равно H − A + B. Но при этом не учитываются возможные переходы между сутками — время может оказаться в следующих сутках или в предыдущих сутках. Это можно учесть при помощи двух условий: если получили время, больше или равное 24 часов, то нужно вычесть 24 часа, а если получили отрицательное время, то нужно прибавить 24 часа. Получается следующее решение:

H = int(input())

A = int(input())

B = int(input())

answer = H – A + B

if answer = 24:

answer -= 24

if answer

answer += 24

print(answer)

Но вместо условий проще взять остаток от деления на 24:

H = int(input())

A = int(input())

B = int(input())

answer = (H – A + B) % 24

print(answer)

Заметим, что в большинстве языков программирования (Pascal, C++, Java, C#) при взятии остатка от деления отрицательного числа на положительное получится отрицательный результат, то есть решение задачи будет неверным. В этом случае нужно действовать так (пример для Pascal). answer := (H – A + B + 24) mod 24 С