Підготовка олімпіадника з програмування

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

· Изучение новых форм проведения олимпиад.

·                    Знание алгоритмов решения олимпиадных задач.

·                    Наличие самих задач.

·                    Знание языков программирования.

·                    Время на изучение, отладку и проверку задач.

·                    Обучение учащихся правильной организации деятельности на олимпиаде.

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

Большинству учителей это не по силам. Наиболее правильный выход в этой ситуации - повышение связей между школой и ВУЗом.

Вот некоторые особенности подготовки школьников к олимпиадному программированию:

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

2.                 Постоянные тренировки идут почти на спортивном уровне.

3.                 Большие затраты времени, длительность олимпиады с разбором часто превышает 6 часов.

4.                 Алгоритмы и формулы, применяемые при решении большинства задач, изучаются только в ВУЗах.

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

·                    Возможно второе образование, профильный ВУЗ по программированию.

·                    ИПК учителей, курсы по изучению языков программирования, по олимпиадному программированию.

·                    Самостоятельная подготовка с использованием материалов из дополнительных источников.

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

Педагогическая идея  

Основным стимулом к участию в олимпиадах для школьника является мотивация.

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

В 1964 г. В. Врум предложил «теорию ожиданий». Он считал, что стимул к эффективному и качественному труду зависит от сочетания трех факторов - ожиданий человека:

1.                 Ожидание того, что усилия приведут к желаемому результату.

2.                 Ожидание того, что результаты повлекут за собой вознаграждение.

3.                 Ожидание того, что вознаграждение будет иметь достаточную ценность.

Технология использования 

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

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

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

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

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

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

Третий шаг. «Обучающая рефлексия». Учащийся обучает решению задач других. Обычно это происходит при разборе задач. Это помогает учащемуся определить признаки оптимальности (краткость, понятность), научиться четко прослеживать и объяснять работу программы.

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

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

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

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

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

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

·                    динамическое программирование;

·                    алгоритмы перебора с возвратом;

·                    алгоритмы на графах;

·                    вычислительная геометрия;

·                    комбинаторные алгоритмы;

·                    моделирование.

Достаточно часто среди олимпиадных задач по информатике встречаются задачи, не подпадающие под упомянутые выше разделы. Можно выделить две группы таких задач. Первая группа — это так называемые задачи «на идею», когда основная сложность решения заключается в придумывании нестандартного, неожиданного алгоритма их решения. Чисто техническая сложность таких задач обычно невелика. Трудно дать какие-либо рекомендации по решению такого рода задач; необходима интуиция, вырабатываемая только частыми тренировками на задачах повышенной сложности и олимпиадных задачах. Кроме того, необходим талант алгоритмиста.

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

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

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

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

Поделюсь находками.

   http://info.rusolymp.ru/default.asp?trID=99

Чигиринский Александр Самойлович, учитель информатики, ныне проживающий в Германии, создал проект с целью дистанционной поддержки своих  учеников  http://homepages.compuserve.de/chasluebeck/

http://www.is.svitonline.com/plot/

В мире сегодня существует множество сайтов с системами Online Judge. Зарегистрировавшись и получив пароль, Вы можете решать задачу и код решения отправлять на автоматическую проверку. Через несколько секунд Вы получаете один из ответов на ваше решение: Accepted (Задача решена верно), Time Limit (Ваше решение не прошло по времени, оно слишком долгое), Wrong Answer (Неверный ответ), Compile Error (Ошибка компиляции программы). Из сегодняшних таких страничек хочется отметить:

·                    http://acm.timus.ru/ – Уральский университет.

·                    http://acm.uva.es/problemset, http://acm.uva.es/contest – университет Вальядолид (Испания).

·                    http://ace.delos.com/usacogate - Подготовка к школьным олимпиадам в США.

·                    http://dl.gsu.unibel.by/ – Беларусский сайт дистанционного образования.

·                    http://acm.baylor.edu/ – Официальный сайт ACM соревнований.

·                    http://www.topcoder.com/ – еженедельные соревнования, США

·                    http://acm.sgu.ru/ – Саратовский государственный университет

·                    http://acm.zju.edu.cn/ - Университет ЖеЙанг, Китай

На сегодняшний день автор содержит страничку по подготовке к олимпиадам по программированию. Страничка находится на сайте кафедры математической информатики Киевского национального университета имени Тараса Шевченко, www.mi.unicyb.kiev.ua, далее следует выбрать «Библиотека», раздел «ACM олимпиады по программированию».

http://www.olympiads.ru/problems/8v-03/index.shtml

http://www.olympiads.ru/sng/index.shtml

Для начинающих. Набор задач.

Числа. Целые числа. Операции с ними. ( mod, div)

1.      Найти цифры двузначного, трехзначного, четырехзначного…. числа.

2.      Сумму его цифр. Поменять местами цифры ( в трехзначном – крайние, в четырехзначном – крайние, внутренние, в пятизначном…

3.      Ветвление.   Заменить цифры числа. Например, все цифры – единицы заменить цифрой 3, или, суммой всех цифр числа. Сначала работаем с определенным количеством цифр в числе.  Например с трехзначным числом. Потом  увеличиваем число разрядов, тем самым усложняем задачи.

4.      Заменить первую цифру на цифру а.

5.      Циклы с параметром Найти все двузначные (трехзначные) числа сумма цифр которых равна N.

6.      Найти все двузначные числа, которые делятся на N или содержат цифру N.

7.      Определить количество трехзначных чисел, сумма цифр, которых равна N

8.      Среди двузначных чисел найти такие, сумма квадратов цифр которых делится на 13.

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

10.  Квадраты некоторых трехзначных чисел заканчиваются тремя цифрами, которые составляют искомое число.

11.  найти четырехзначные числа, которые при делении на 133 дает остаток 125, а при делении на 134 дает остаток 111

12.  Найти сумму целых положительных чисел из отрезка  от А до В, которые кратны 4. Найти все симметричные числа из этого отрезка (палиндромы)

13.  Циклы с уловием. Вычислить количество цифр заданного натурального числа N. Найти сумму цифр числа.

14.  Найти старшую цифру числа.

15.  Дописать по 1  в начало и конец записи числа N. Поменять местами первую и последнюю цифры числа.

16.  Найти количество четных цифр числа. Найти наибольшую цифру числа. Сколько раз данная цифра встречается в заданном числе?

17.  Проверить, является ли заданное число палиндромом.,т.е. таким, десятичная запись которого читается одинаково слева направо и справа налево.

18.  Алгоритм Эвклида вычисления наибольшего общего делителя двух чисел.

19.  Найти НОД трех чисел.

20.  Проверить, являются ли два числа взаимно простыми (НОД=1)

21.  Дано число. Дописать к нему такое же число.

22.  Из числа удалить цифры А.

23.  Вложенные циклы. Сколько можно купить быкок, коров,и телят, если бык стоит -10 рублей, корова 5 рублей, теленок – 50 копеек, и на 100 рублей нужно купить 100 голов скота?

24.  Дано натуральное число. Можно ли его представить в виде суммы квадратов трех натуральных чисел.

25.  Найти натуральное число от 1 до 10000 с максимальной суммой делителей.

26.  Найти все трехзначные числа, которые удовлетворяют таким условиям: а) лубые две цифры числа разные; б) число равно среднему арифметическому всех трехзначных чисел (включая данное), которое состои из этих же цифр.

Разбор и решение задачи 11-той Кировской олимпиады "Прямоугольники"

На плоскости задано N (1.. 300) прямоугольников со сторонами, параллельными координатным осям (см. рисунок). Координаты вершин прямоугольников – вещественные числа, заданные с точностью до двух знаков после запятой. Написать программу определения площади фигуры, получающейся в результате объединения прямоугольников.




Входные данные
В первой строке файла INPUT.TXT записано число N. В следующих N строках записано по четыре числа – координаты левого нижнего и правого верхнего углов прямоугольника.

Выходные данные
В файле OUTPUT.TXT записывается одно число – площадь фигуры с точностью до четырех знаков.

Пример входных данных
4
0  0  10.1  5.2
-3  3  5.36  7
1  6  9  15
8  3  20  8

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

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



Поэтому для нахождения площади достаточно отсортировать точки на оси X, рассмотреть все сечения и добавить к площади <длину интервала>•<длину сечения>. Для поиска длины сечения используем следующий метод. Началу каждого отрезка присвоим значение признака, равное 1, а его концу –1 и отсортируем точки по значению координаты Y. Подсчитаем сумму значений признаков. Если она не равна нулю, то соответствующий интервал “плюсуем” к длине сечения.

Const InputFile='Input.TxT';
OutputFile='Output.TxT';
MaxN=300;
Eps=1e-5;
Tochn=4;
Type TPoint=Record X,Y: Real;End;
MasPnt=Array[1..MaxN] Of TPoint;
BMasPnt=Array[1..MaxN*2] Of Real;
BMasSSt=Array[1..MaxN*2] Of LongInt;
Var PrM: Array[1..2] Of MasPnt;
N: LongInt;
Res: Real;
Ox, Oy: BMasPnt;
FOy: BMasSSt;


Процедура инициализации и ввода данных
Координаты вершин прямоугольников храним в массиве PrM, причем в PrM[1] (это массив) – координаты первой вершины, а в PrM[2] – второй. Вершина прямоугольника с меньшими значениями (X, Y) записывается в PrM[1]. Кроме того, значения X запоминаются в массиве Ox.

Procedure ReadPoint(Var A: TPoint);
Begin
Read(A.X, A.Y);
End;

Procedure More(Const a, b: Real): Boolean;
Begin
More:=a-b>Eps;
End;

Procedure Swap(Var a, b: Real);
Var t: Real;
Begin
  t:=a; a:=b; b:=t;
End;

Procedure Init;
Var i: LongInt;
Begin
  Res:=0;
  FillChar(Ox, SizeOf(Ox), 0);
  FillChar(Oy, SizeOf(Oy), 0);
  FillChar(Foy, SizeOf(FoY), 0);
  FillChar(PrM, SizeOf(PrM), 0);
  Assign(Input, InputFile);Reset(Input);
  Read(N);
  For i:=1 To N Do Begin
   ReadPoint(PrM[1,i]);ReadPoint(PrM[2,i]);
   If More(PrM[1,i].X, PrM[2,i].X)
     Then Swap(PrM[1,i].X, PrM[2,i].X);
   If More(PrM[1,i].Y, PrM[2,i].Y)
     Then Swap(PrM[1,i].Y, PrM[2,i].Y);
   Ox[i*2-1]:=PrM[1,i].X;Ox[i*2]:=PrM[2,i].X;
  End;
  Close(Input);
End;

Процедура вывода результата и основная программа очевидны
Procedure Done;
Begin
  Assign(Output, OutputFile);
  Rewrite(Output);
  WriteLn(Res:0:Tochn);
  Close(Output);
End;

Begin
Init;
Solve;
Done;
End.

Вспомогательные процедуры

Function Eq(Const a, b: Real): Boolean;
  Begin
    Eq:=Abs(a-b)   End;

Procedure SwapInt(Var a, b: LongInt);
  Var t: LongInt;
  Begin
   t:=a; a:=b; b:=t;
  End;

Для решения задачи потребуется сортировка элементов массива. Используем метод Хоара
Sort(Var Ox:BMasPnt; Const lf,rg:LongInt);
Var i,j:LongInt;
x:Real;
Begin
  i:=lf;j:=rg;x:=Ox[(lf+rg) Div 2];
  Repeat
  While More(x, Ox[i]) Do Inc(i);
  While More(Ox[j], x) Do Dec(j);
  If i<=j Then
    Begin
      Swap(Ox[i], Ox[j]);Inc(i); Dec(j);
    End;
  Until i>j;
  If lfThen Sort(Ox, lf, j);
  If iThen Sort(Ox, i, rg);
End;

Та же самая сортировка, но с одновременной перестановкой элементов другого массива

Procedure FstSort(Var Ox: BMasPnt;
Var SOx: BMasSSt;
Const lf, rg: LongInt);
Var i, j: LongInt;
x: Real;
  Begin
   i:=lf;j:=rg;x:=Ox[(lf+rg) Div 2];
   Repeat
    While More(x, Ox[i]) Do Inc(i);
    While More(Ox[j], x) Do Dec(j);
    If i<=j Then
      Begin
       Swap(Ox[i],Ox[j]);
       SwapInt(SOx[i],SOx[j]);
       Inc(i);Dec(j);
      End;
   Until i>j;
   If lfThen FstSort(Ox, Sox, lf, j);
   If iThen FstSort(Ox, Sox, i, rg);
End;

Перейдем к основной процедуре – вычислению площади объединения прямоугольников

Procedure Solve;
Var i: LongInt; m: Real;
Begin
   Sort(Ox, 1, N*2); {сортируем по неубыванию значения координаты X прямоугольников}
   m:=0; Res:=0; {m – длина сечения, Res – значение площади объединения прямоугольников}
   For i:=1 To N*2 Do Begin
    If i<>1 Then Res:=Res+Abs((Ox[i]-Ox[i-1])*m);
     {прибавляем площадь очередного сечения}
    If (i=1) Or Not(Eq(Ox[i], Ox[i-1]))
           Then Change(Ox[i], m);
          {определяем новое значение длины сечения}
   End;
End;

Продолжим уточнение
Function Peres(Const k: LongInt;
Const x: Real): Boolean;
Begin
  Peres:=Not More(PrM[1,k].X,x) And
  More(PrM[2,k].X,x);
End;

Procedure Change(Const x: Real; Var rs: Real);
Var i, M: LongInt;
  Begin
    M:=0;FillChar(Oy,SizeOf(Oy),0);
    FillChar(FOy,SizeOf(Foy),0);
    For i:=1 To N Do
      If Peres(i, x) Then Begin
       {если есть пересечение?}
       Oy[M+1]:=PrM[1,i].Y;Oy[M+2]:=PrM[2,i].Y;
       {формируем массив ординат для данной координаты X}
       FOy[M+1]:=1;FOy[M+2]:=-1;
       {признаки начала и конца отрезка}
       Inc(M, 2);
      End;
      If M=0 Then rs:=0
       Else Begin FstSort(Oy,FOy,1,M);
       rs:=Abs(Calc(Oy,FOy,M));
      End;
      {изменяем значение признака пересечения интервалов, например, для значения 8 на рисунке оно будет  равно нулю и длина от 8 до 10 не войдет в результат}
End;
И, наконец, последнее уточнение: функция вычисления длины сечения. Для примера на рисунке длина сечения будет равна 10


Function Calc(Const Ox: BMasPnt;
Const SOx: BMasSSt;
Const N: LongInt): Real;
Var sc: Real;
i, bb: LongInt;
Begin
   sc:=0;bb:=0;
   If SOx[1]>0 Then Inc(bb);
   For i:=2 To N Do Begin
      If bb>0 Then sc:=sc + Ox[i] - Ox[i-1];
      Inc(bb, SOx[i]);
      {изменяем значение признака пересечения интервалов, например, для значения 8 на рисунке оно будет
       равно нулю и длина от 8 до 10 не войдет в результат}
  End;
Calc:=sc;
End;