Информатика

       

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


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

Согласно приказу министра образования Российской Федерации № 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 абитуриентов, сдававших экзамены по информатике, математике и языку, выбрать всех отличников и всех учащихся, на­бравших в сумме не меньше проходного балла. Данные о проходном балле вводятся с клавиатуры, а данные о результатах сдачи экзаме­нов представлены таблицей:



фамилия

имя

информатика

математика

язык

Иванов

Саша

4

4

3

Петрова

Катя

5

5

5

Сидоров

Алеша

5

3

3

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

Тест 1:

 

Иванов

Саша

4

4

3

Петрова

Катя

5

5

5

Сидоров

Алеша

5

3

3

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

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

 

отличники:

Петрова Катя

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

Иванов Саша

Петрова Катя

Тест 2:

 

Иванов

Саша

4

4

3

Сидоров

Алеша

5

3

3

 

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

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

 

отличники:

отсутствуют

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

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

Тест 3:

 

Сидоров

Алеша

5

3

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

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 точки».

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



х

у

0

0

0

3

4

0

5

10

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

Сценарий



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

<х1> <у1>

… … …

<х4> <у4>

      

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

<ml> <m2> <m3> <m4>

длина = <mх>

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

<n1> <n2> <n3> <n4>

длина = <mn>

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

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

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

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. «Ломаная».



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

х

у

0

1

1

0

0

1

1

1

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

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

Tecт1.

(Основной случай)

0

0

0

1

1

0

1

1

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

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

0.5              0.5

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

0

0

0

1

1

1

1

0

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

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

отсутствуют

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

0

0

0

1

0.5

0

1

1

1

0

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

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

0.5              0

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

0

0

0

1

0.2

0

0.8

0

1

1

1

0

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

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

[0.2, 0] - [0.8, 0]

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

 

Сценарий



           точек: <n>

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

                                                    <k>: <x> <у> 

                                                            …….. 

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

отрезок: <k> - <k+l>      *

                                                отрезок: <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

? x3; y3

else

? х4; у4

end if

return

 

vvod: ' ввод данных

restore test1

read n

? «точек:»;nt

for k = 1 to nt

read x(k), y(k)

? x(k); y(k)

next kn

t = nt + 1

x(nt) = x(l)

y(nt) = y(l)

return

test1: 'точки ломаной:

data 4

data 0, 0

data 1, 0

data 0, 1

data 1, 1

test2: 'точки ломаной:

data 4

data 0, 0

data 1, 0

data 0, 1

data 1, 1

В тексте данной программы записаны два варианта тестовых данных, смена которых может быть проведена изменением имени метки

test1 или test2 в операторе перезагрузки restore в подпрограмме ввода данных.


Содержание раздела