Методика и содержание подготовки учащихся к олимпиадам по программированию. Дистанционный курс. Занятие №1


Скачать 102.41 Kb.
НазваниеМетодика и содержание подготовки учащихся к олимпиадам по программированию. Дистанционный курс. Занятие №1
Дата22.04.2013
Размер102.41 Kb.
ТипДокументы

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

Занятие №1.



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

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

Какие бывают олимпиады по программированию?



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


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

Схема проверки выглядит так: программа (чаще в виде исходного текста) предъявляется тестирующей системе, которая:

а) эту программу компилирует (если это невозможно, то решение данной задачи не засчитывается, то есть по ней школьник получает 0 баллов);

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

Второе. Напрямую вытекает из первого. Поскольку проверяется исполняемый файл, то крайне желательно, чтобы школьник пользовался системой программирования, которая способна такой файл создать (см. например, список допустимых компиляторов на www.olympiads.ru в разделе «Московская командная олимпиада»).

Третье. Гарантируется, что исходные данные всех задач корректны. Участникам не надо тратить время на проверку правильности поступивших данных, им необходимо сосредоточиться на решении основной задачи.

Четвертое. Весь ввод и вывод необходимо строго ограничить тем, что написано в условии задачи. Автоматическая тестирующая система не обладает достаточным искусственным интеллектом, чтобы отсеивать фразы навроде «Введите массив из 10 элементов». Эта фраза может быть принята за начало вывода ответа, и в результате правильная программа может получить 0 баллов.

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


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


Командные олимпиады:

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

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

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

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


Личные олимпиады:


1. Количество баллов по задаче зависит от количества успешно пройденных программой тестов.
То есть неполное решение, к примеру на небольшом массиве или не предусматривающее всех частных случаев – тоже способно принести участнику какие-то баллы. Отсюда соображение, что если осталось время - надо постараться написать даже неполное решение от тех задач, которые в общем случае школьник решить не может. Даже 3-5 баллов способны сыграть довольно большую роль при подведении итогов.
2. Решения проверяются один раз – по окончании тура.
От школьников требуется значительно более высокое умение самим проверять свои программы, нежели на командных олимпиадах. Соответственно, никакого общего протокола в реальном времени просто не существует. Это означает, что от школьника требуется еще умение выбрать себе задачи «по силам», чтобы не сидеть полтура над задачей, которую он в итоге не решит.


Примечание о частичных решениях (оно же – уточнение, когда жюри читает тексты программ)


Есть отдельные задачи, в которых требуется ответ типа «Да/Нет». Есть умные школьники, которые понимают, что некоторые тесты будут с ответом «Да», а некоторые – с ответом «Нет», и эти школьники пишут программы, которые всегда выводят «Да» или всегда «Нет». Такие решения часто не засчитываются даже в качестве неполных. Поэтому иногда в правилах встречаются оговорки типа «если программа выводит одно и то же при разных исходных данных, то она считается не прошедшей ни одного теста». Это как раз для таких школьников.


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

Что должен знать школьник перед началом серьезной подготовки к олимпиадам?





  1. Основные типы данных (целые, вещественные, символьные, строковые) и операции над ними.

  2. Условия. Сложные условия. Порядок действий в сложных условиях.

  3. Циклы.

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

  5. Массивы. Двумерные массивы.
    На уровне «найти наибольший/наименьший», «подсчитать количество элементов, равных X», «найти сумму элементов по условию».



Что дальше (чему учить школьника)?



Олимпиадные задачи по программированию включают следующие темы (с той или иной степенью подробности и сложности)

  1. Признаки делимости

  2. Перебор

  3. Рекурсия

  4. Сортировки и поиск

  5. Динамическое программирование

  6. Геометрические задачи
    (тригонометрия, уравнение прямой, пересечение прямых, пересечение отрезков, площадь треугольника, площадь многоугольника, выпуклые оболочки)

  7. Графы и алгоритмы на графах.

  8. Длинная арифметика.

Собственно, обзору этих тем и примеров задач и будет посвящен данный курс.

Где можно получить дополнительную информацию?



Сайты (на момент написания статьи):

http://www.olympiads.ruна сайте сосредоточена информация о московских олимпиадах для школьников по программированию, имеются архивы прошлых лет. Также есть ссылка на дистанционные семинары для школьников, сайты других олимпиад.

http://acm.timus.ruархив задач разного уровня, правда, в основном из студенческих олимпиад по программированию. Имеется возможность послать на проверку свое решение той или иной задачи, есть форум с обсуждением оптимальных способов решения.


Основная литература (на момент написания статьи):

  1. Т. Кормен, Ч. Лейзерсон, Р. Ривест. «Алгоритмы. Построение и анализ». Издание второе. Книга содержит основные алгоритмы практически по всем «олимпиадным» темам. Помимо этого в ней даны теоретические сведения, необходимые для понимания алгоритмов и структур данных.

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

  3. А. Шень «Программирование: теоремы и задачи».

(электронные версии этих и многих других книг, в том числе и с задачами по программированию можно взять по следующей ссылке http://lib.kruzzz.com/1-65/etc.html)

Несколько простых задач



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


A+B. Даны целые числа A и B, по модулю не превышающие 32000. Найти их сумму.

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

Дело в ограничении на целые типы в системах программирования Borland Pascal 7.0 и Borland C++ 3.1, которые довольно часто используются школьниками. Тип Integer (Паскаль) или int (С++) имеют диапазон значений от -32768 до +32767. Формально, исходные данные вмещаются в тип, но никто не гарантирует что в этот тип поместится сумма. Дело в том, что во многих компиляторах тип результата определяется исключительно типом операндов. То есть если мы складываем два числа типа Integer (int), то и получается число типа Integer (int). И тут происходит переполнение. Школьникам неявно намекают, чтобы они были более внимательны при выборе типов данных внутри программ.

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

Что касается этой задачи, то необходимо для обоих исходных данных и результата использовать тип longint (long int).


. По заданным n и k найти .

Задача в таком виде, как она тут сформулирована, на олимпиадах практически не встречается. Однако, это неплохая иллюстрация ситуации, когда результат не переполняется, зато могут переполнится промежуточные данные. Если использовать формулу треугольника Паскаля , то возможно найти ответ до n=17. При n=18 у типа Integer (int) возникнет единственное переполнение на k=9. Однако, если использовать комбинаторную формулу , то попытка вычислить числитель этой дроби приведет к переполнению уже при n=8. Можно, конечно, использовать тут тип longint (long int), но все равно числитель комбинаторной формулы вызовет переполнение уже при n=13.


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


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



1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

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

(N-1; N+1, N-8 и N+8). Однако, когда эта задача дается на школьном или окружном туре олимпиады, то многие также забывают, что у доски есть края и их программы выводят по 4 числа даже для угловых ячеек, например с N=8.

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


Покраска стены. Дана стена со сторонами A и B (натуральные, не превышают 1000), которую необходимо покрасить. Сколько потребуется купить банок краски, если банки можно покупать только целиком, а одной банкой можно закрасить площадь стены, равную S (натуральное, не превышает 10000).


Во-первых, необходимо правильно подобрать типы данных, потому что при таких ограничениях исходных данных вычисление площади стены может вызвать переполнение типа integer (int). Во-вторых, в задаче необходимо предусмотреть два случая: либо A*B делится на S без остатка, тогда результат деления и будет ответом, либо получается какой-то остаток, тогда к результату целочисленного деления нужно прибавить 1.


Основная часть решения на Паскале:


sWall:=A*B;

if (sWall mod S=0) then write(sWall div S)

else write(sWall div S + 1);

Основная часть решения на Си:


sWall=A*B;

if (sWall % S ==0) printf(“%d”, sWall/S);

else printf(“%d”, sWall/S + 1);


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


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



МЦНМО, 2007/08 учебный год

Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница