Олимпиадные задачи по информатике

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

Согласно приказу министра образования Российской Федерации № 500 победители и призеры международных олимпиад могут руко­водством российских вузов зачисляться без экзаменов на профиль­ные специальности и факультеты.

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

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

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

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

Примеры олимпиадных задач по информатике в других уни­верситетах и вузах Российской Федерации, которые засчитывают результаты побед в региональных, российских и международных олимпиадах по информатике, можно найти в Интернете по запросу «олимпиада информатики» с помощью поисковых систем Апорт, Ремблер или Яндекс. В 1999 году таких вузов было более сорока.

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

Оценки за решение задач проставлялись по следующей методике:

1) при правильных результатах на всех тестах 100% баллов; 2) при получении правильного решения хотя бы на одном тесте 40% баллов, а за результаты на остальных (n - 1 )-м тестах добавляется 60%/(n - 1) баллов; 3) при неправильных результатах на всех тестах или отсутст­вии программы оценка не ставилась.

На первом туре первой сетевой олимпиады были предложены четыре задачи информационно-логического и геометрического со­держания со следующими оценками сложности, определенными экспертами:

задача 1 («Экзамены») - 50 баллов;

задача 2 («Слова») - 100 баллов;

задача 3 («4 точки») -150 баллов;

задача 4 («Ломаная») - 250 баллов.

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

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

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

Задача 1. «Экзамены».

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

фамилия	имя	информатика	математика	язык
Иванов	Саша
Петрова	Катя
Сидоров	Алеша

Приведем проверочные тесты и правильные результаты:

Тест 1:

Иванов	Саша
Петрова	Катя
Сидоров	Алеша

проходной балл =? 12

Правильные результаты:

отличники:

Петрова Катя

не меньше проходного:

Иванов Саша

Петрова Катя

Тест 2:

Иванов	Саша
Сидоров	Алеша

проходной балл =? 12

Правильные результаты:

отличники:

отсутствуют

не меньше проходного:

Иванов Саша 4 4 4

Тест 3:

Сидоров

Алеша

проходной балл =? 14

Правильные результаты:

отличники:

отсутствуют

не меньше проходного:

отсутствуют.

В приведенных тестах анализируются различные логические ситуации с отсутствием «отличников» или «успешно» сдавших экза­мены. При составлении программы эти ситуации можно явно преду­смотреть в сценарии диалога с ЭВМ:

Сценарий

оценки учащихся:

<фам> <имя> <мат> <инф> <язык> *

………………………………….

проходной балл=? <b1>

отличники:

<фам> <имя> *

……………

отсутствуют

не меньше проходного:

<фам> <имя> <sum> *

……………..

отсутствуют

ПрограммаАлгоритм

' результаты экзаменов алг «результаты экзаменов»

cls нач

? «оценки учащихся:» вывод («оценки учащихся:»)

do цикл

read fm$, nm$, mt, in, zk ввод fm$, nm$, mt, in, zk

if fm$ = «» then exit do если fm$ = «» то выход

? fm$, nm$, mt, in, zk вывод (fm$, nm$, mt, in, zk)

loop кцикл

input «проходной балл=»,b1 запрос («проходной балл=»,b1)

restore ocenki перезагрузка_ oценки

? «отличники:» вывод («отличники:»)

n = 0 п = 0

do цикл

read fm$, nm$, mt, in, zk ввод fm$, nm$, mt, in, zk

if fm$ = «» then exit do если fm$ = «» то выход

if mt=5 and in=5 and zk=5 then если mt=5 и in = 5 и zk=5 то

? fin$, nm$ вывод (fm$, nm$)

n = n + 1 n = n + 1

end if кесли

loop кцикл

if n=0 then ? «отсутствуют» если п=0 то вывод(«отсутствуют»)

restore ocenki перезагрузка-оценок

? «не меньше проходного:» вывод («не меньше проходного:»)

n = 0 п = 0

do цикл

read fm$, nm$, mt, in, zk ввод fm$, nm$, mt, in, zk

if fm$ = «» then exit do если fm$ = «» то выход

sum = mt + in + zk sum = mt + in + zk

if sum >= hi then если sum >= bl то

? fm$, nm$, sum вывод (fm$, nm$, sum)

n = n + 1 n = n + 1

end if кесли

loop кцикл

if n = 0 then ? «отсутствуют» если п = 0 то вывод («отсутствуют»)

end кон

Ocenki: 'оценки учащихся

Data «Иванов», «Саша», 4, 4, 3

Data «Петрова», «Катя», 5, 5, 5