Название: Информатика

Жанр: Информатика

Рейтинг:

Просмотров: 3382

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

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

Согласно приказу министра образования Российской Федерации № 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

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

отличники:

отсутствуют                            

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

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

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

Сценарий

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

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

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

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

отличники:

                                                                         <фам> <имя>                      *

                                                                                ……………

отсутствуют

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

                                                                  <фам> <имя>                  *

                                                                                ……………..

отсутствуют

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

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

    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

data «Сидоров», «Алеша», 5, 3, 3

data «», «», 0, 0, 0

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

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

Задача 2. «Слова».

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

Исходная фраза:

ВЕЧЕРАМИ МЫ СМОТРИМ ТЕЛЕВИЗОР

Циклическая перестановка слов:

МЫ СМОТРИМ ТЕЛЕВИЗОР ВЕЧЕРАМИ

СМОТРИМ ТЕЛЕВИЗОР ВЕЧЕРАМИ МЫ

ТЕЛЕВИЗОР ВЕЧЕРАМИ МЫ СМОТРИМ

ВЕЧЕРАМИ МЫ СМОТРИМ ТЕЛЕВИЗОР

Сценарий

     Исходная фраза:

<строка>

Перестановка слов:

                                                                                <строка'>          *

Проверочные .тесты:

Тест 1: Исходная фраза:

утром был дождь

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

Перестановка слов:

был дождь утром

дождь утром был

утром был дождь

Тест 2: Исходная фраза:

правильно

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

Перестановка слов:

правильно

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

¢ перестановка слов                                           алг «перестановка слов»

cls                                                                           нач

? «Исходная фраза:»                              вывод («Исходная фраза:»)

line input st$                                             ввод-строки (st$)

? st$                                                                вывод st$

In = len(st$)                                                           in = len(st$)

? «Перестановка слов:»                    вывод («Перестановка слов:»)

s$ = st$                                                  s$ = st$

do                                                                           цикл

k = instr(s$,«»)                                          k = instr(s$,«»)

if k = 0 then                                              если k = 0 то

? s$                                                              вывод (s$)

exit do                                                         выход

end if                                                           кесли

lf$ = left$(s$,k-l)                                      lf$ = left$(s$,k-l)

rt$ = right(s$,ln-k)                                  rt$  = right(s$,ln-k)

ns$ = rt$ + «» + lf$                                 ns$ = rt$  + «» + lf$

? ns$ вывод                                            (ns$ )

if ns$ = st$ then exit do                         при ns$ = st$  выход

s$ = ns$                                                     s$  = ns$

loop                                                              кцикл

end                                                                         кон

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

Задача 3. «4 точки».

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

Составление алгоритмов и программы для решения этой задачи также полезно начать с составления сценария диалога.

Сценарий

       координаты точек:

<х1> <у1>

… … …

<х4> <у4>

максимальный маршрут:

длина =

минимальный маршрут:

длина =

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

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

¢мин. и макс. маршруты                                   алг «мин. и макс. маршруты»

cls                                                                                           нач

n = 4                                                                               п = 4

dim x(n),y(n),r(n,n)                                                  dim x(n),y(n),r(n,n)

? «координаты точек»                              вывод («координаты точек»)

gosub vvdan 'ввод данных                       ввод-координат-точек

 restore mrshrt 'маршруты                        загрузка-маршрутов

? «маршруты:»                                                      вывод («маршруты:»)

mr = 1*2*3                                                    mr =1*2*3

mx = 0                                                                            тх = 0

for l = 1 to mr                                                от l = 1 до mr

read k1, k2, k3, k4                                            ввод k1, k2, k3, k4

dl = r(kl,k2) + r(k2,k3)                                      dl = r(kl,k2) + r(k2,k3)

d3 = r(k3,k4) + r(k4,kl)                                     d3 = r(k3,k4) + r(k4,k1)

d = dl + d3                                                        d = d1 + d3

? kl; k2; k3; k4, d                                              вывод (k1; k2; k3; k4, d)

if mx = 0 then                                                 если тх = 0 то

mx = d: mn = d                                                               mx = d: mn = d

ml = kl: m2 = k2                                                             ml = k1: m2 = k2

m3 = k3: m4 = k4                                           m3 = k3: m4 = k4

nl = kl: n2 = k2                                                               n1 = k1: n2 = k2

n3 = k3: n4 = k4                                                             n3 = k3: n4 = k4

elseif d > mx then                                                 инеc d > mx то

mx = d                                                                             mx = d

ml = kl: m2 = k2                                                             m1 = k1: m2 = k2

m3 = k3: m4 = k4                                           m3= k3: m4 = k4

elseif d < mn then                                                 инеc d < mn то

mn = d                                                                           mn = d

nl = kl: n2 = k2                                                              n1 = k1: n2 = k2

n3 = k3: n4 = k4                                                     n3 = k3: n4 = k4

end if                                                                               кесли

next 1                                                                            кцикл

? «максимальный маршрут:»                            вывод («максимальный маршрут:»)

? ml; m2; m3; m4                                                      вывод (m1; m2; m3; m4)

? «длина =»; mx                                                      вывод («длина =»; mx)

? «минимальный маршрут:»                              вывод («минимальный маршрут:»)

? nl; n2; n3; n4                                                         вывод (n1; n2; n3; n4)

? «длина =»; mn                                                     вывод («длина =»; mn)

end                                                                                         кон

vvdan: 'ввод данных                                           алг «ввод данных»

restore tchks                                                             загрузка-точек

for k = 1 to n                                                                 от k = 1 до п

read x(k),y(k)                                                                   ввод x(k),y(k)

? x(k),y(k)                                                                         вывод x(k),y(k)

next k                                                                                      кцикл

for k = 1 to n                                                                          от k = 1 до п

for l = 1 to n                                                                от l = 1 до п

dx = x(k) - x(l)                                                                 dx = x(k) - x(l)

dy = y(k) - y(l)                                                           dy = y(k) - y(l)

rs = dx*dx + dy*dy                                                  rs = dx*dx + dy*dy

r(k,l) = sqr(rs)                                                               r(k,l) = sqr(rs)

next 1                                                                              кцикл

next k                                                                           кцикл

return                                                                                     кон

mrshrt: 'маршруты:

data 1, 2, 3, 4

data 1, 2, 4, 3

data 1, 3, 2, 4

data 1, 2, 4, 3

data 1, 4, 2, 3

data 1, 4, 3, 2

tchks: 'координаты точек 

data 0, 0

data 0, 3

data 4, 0

data 4, 3

Результаты выполнения на              ЭВМ приведенной программы:

координаты точек:

0 0

03

4 0

4 3

маршруты:                                           длина:

1  2  3  4                                  16

1  2  4  3                                  14

1  3  2  4                                  18

1  2  4  3                                  14

1  4  2  3                                  18

1   4  3  2                                 16

максимальный маршрут:

1  3  2  4

длина =18

минимальный маршрут:

1  2  4   3

длина = 14

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

Задача 4. «Ломаная».

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

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

Приведем проверочные тесты:

Tecт1. (Основной случай)

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

точки пересечения

0.5

Тест 2. (Основной случай)

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

точки пересечения:

отсутствуют

Тест3. (Наложение вершины)

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

точки пересечения

0

Тест4. (Наложение ребра)

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

отрезок пересечения:

[0.2, 0] - [0.8, 0]

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

Сценарий

           точек:

координаты точек:               

                                                                    : <у> 

                                                                                …….. 

           точки пересечения:

отрезок: -       *

                                                                отрезок: <1> - <1+1>

    точка: <х> <у>

                ………

     отсутствуют

Метод решения данной задачи может быть основан на вычислении точек пересечения отрезков (х1, у1) - (x2, у2) и (х3, y3) - (х4, y4) как точек пересечения линий, проходящих через заданные отрезки, с помощью системы уравнений:

 (y2 – y1 )×( x – x1) - (x2 – x1)×(y – у1) = 0;

 (у4 – у3)×(x – x3) - (x4 – x3)×(у – y3) = 0.

Решение этих уравнений может быть проведено вычислением определителей D, Dx, Dy приведенной системы уравнений:

 (у2 – у1)×х - (х2 – х1)×у = (у2 – y1)×х1 - (x2 – x1)×y1;

 (у4 – y3)×х - (х4 – х3) ×у = (у4 – у3)×х3- (x4 – x3)×y3,

для которой будет справедлив следующий набор расчетных формул:

х = Dx/D;

у = Dy/D;

D = (у2 - у1)×(х4 - x3) - (x2 - x1)×(y4 -  y3);

 Dx = [(y2 - yl)×xl - (х2 – x1)×y1] - (x4 – х3) - (x2 – x1)×[(y4 – y3)×x3 - (х4 – х3)×y3];

Dy = (у2 - у1)×[(у4 – у3)×х3 - (x4 - x3)×у3] - [(у2 – y1)×x1 - (х2 – x1)×y1]×(y4 – y3).

Факт пересечения пар отрезков может быть установлен из этих же уравнений подстановкой в правые части координат точек альтернативного отрезка и сравнением значений этих выражений. А именно отрезок [(х3, у3) - (х4, у4)] пересекает линию, проходящую через отрезок [(x1, y1) - (х2, у2)], если эти выражения имеют разные знаки:

(у2 - у1)×(х3 – x1) - (х2 – х1)×(y3 – у1) ´ (у2 - у1)×(х4 – x1) - (х2 – x1)×(y4 – y1) £ 0.

Соответственно, отрезок [(х1, у1) - (х2, у2)] пересекает линию, проходящую через отрезок [(х3, у3) - (х4, у4)], если аналогичные выражения имеют разные знаки:

(у4 – у3)×(х1 – х3) - (х4 – х3)×(у1 – у3)´(у4 – у3)×(х2 – х3) - (х4 – х3)×(у2 – у3) £ 0.

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

В последнем случае общая часть отрезков находится из взаиморасположения отрезков [(х1, у1) - (х2, у2)] и [(х3, у3) - (х4, у4)] на прямой. В данной ситуации взаиморасположение вершин отрезков можно выяснить, вычислив взаиморасположение между ними на прямой относительно отрезка [(х1, у1) - (х2, у2)] по следующим формулам:

d1 = 0;                                             

d2 = (х2 – х1)×(х2 – х1) + (у2 – у1)×(у2 - 1);

d3 = (х3 – х1)×(x2 – х1) + (у3 - у1)×(у2 - 1);

d4 = (х4 – х1)×(х2 – х1) + (у4 – y1)×(y2 - 1).

Если d2 < min (d3, d4) или max (d3, d4) < 0, то отрезки не пересекаются. В противном случае необходимо выделить и отбросить две крайние точки, и тогда оставшиеся две точки зададут общую часть этих отрезков.

Опираясь на эти математические факты можно приступить к составлению алгоритмов и программы. Приведем программу, в которой установлено максимальное число точек nt = 200. Реальное число точек устанавливается при вводе исходных данных из перечня операторов data, записанных в конце текста программы.

¢ самопересечение ломаной

nt = 200

dim x(nt), y(nt)

gosub wod 'ввод данных

? «точки пересечения:»

np = 0 'число пересечении

for k = 1 to nt - 1

xl = x(k): yl = y(k)

x2 = x(k + I): y2 = y(k + 1)

for 1 = k + 1 to nt - 1

x3 = x(I): y3 = y(I)

х4 = x(I + 1): y4 = y(I + 1)

gosub pint 'пересечение

next 1

next k

if np = 0 then ? «отсутствуют»

end

pint: ¢ точка пересечения:

d213 = (у2 - yl)*(x3 - х1) - (х2 - х1)*(у3 - у1)

d214 = (у2 - у1)*(х4 - х1) - (х2 - х1)*(у4 - у1)

d431 = (у4 - у3)*(х1 - хЗ) - (х4 - х3)*(у1 - уЗ)

d432 = (у4 - у3)*(х2 - хЗ) - (х4 - х3)*(у2 - уЗ)

if d213*d2l4 > 0 or d431*d432 > 0 then

' нет пересечения

elseifd213*d214 < 0 or d431*d432 < 0 then

gosub tchki ' расчет точки

else ' отрезки на одной прямой

gosub lin 1

end if

return

tchki: ' расчет точки пересечения

np = np+1

? «отрезок:»; k; k + 1

? «отрезок:»; I; I + 1

D = (у2 - yl)*(x4 - хЗ) - (х2 - х1)*(у4 - уЗ)

Dx = [(у2 - у1)*х1 - (х2 - х1)*у1]*(х4 - хЗ)

Dx = Dx - (х2 - х1)*[(у4 - у3)*х3 - (х4 - х3)*у3]

Dy = (у2 - у1)*[(у4 - у3)*х3 - (х4 - х3)*у3]

Dy = Dy - [(у2 - yl)*xl - (х2 - х1)*у1]*(у4 - уЗ)

х = Dx/D

у = Dy/D

? х; у

return

lin 1: 'отрезки на одной прямой

d2 = (х2 - х1)*(х2 - х1) + (у2 - у1)*(у2 - 1)

d3 = (хЗ - х1)*(х2 - х1) + (уЗ - у1)*(у2 - 1)

d4 = (х4 - xl)*(x2 - х1) + (у4 - у1)*(у2 - 1)

if d3 > d2 and d4 > d2 then

' нет пересечения

Iseif d3 < 0 and d4 < 0 then

' нет пересечения

else ' отрезки пересекаются:

gosub otrеz ' общий отрезок

end if

return

otrez: 'расчет общего отрезка

np = np + 1

? «отрезок пересечения:»

if d3 < 0 or d4 < 0 then

? х1; у1; «-»

elseif d3 < d4 then

? х3; у3; «-»

else                                    

? х4; у4; «-»

end if

if d2 < d3 or d2 < d4 then

? х2; у2

elseif d3 < d4 then