Если бы у меня было больше времени,
я бы написал короче…
Блейз Паскаль
Ни для кого не секрет, что по сравнению с другими дисциплинами школьного курса, олимпиадная информатика имеет ряд своих особенностей. А именно:
- задачи по информатике находятся на стыке нескольких дисциплин;
- учащиеся разного возраста решают одни и те же задачи;
- виртуозное знание языка программирования не является гарантом успешного выступления (даже на олимпиаде муниципального уровня).
Все эти аспекты должны быть учтены учителем при подготовке учащихся к олимпиадным соревнованиям.
В этой статье речь пойдет о системе подготовки школьников 7-8 классов к выступлению на олимпиаде по информатике. С чего начать? На что сделать акцент при работе с учащимися 7-8-х классов, для того, чтобы они могли успешно начать свое выступление на олимпиадах по информатике? Как известно, первый успех является сильнейшей мотивацией, которая поможет ученикам не свернуть с пути программирования, заложит хороший фундамент, на котором в дальнейшем будет возможно воспитать победителей и призеров всех этапов всероссийской олимпиады школьников по информатике.
Итак, олимпиадная подготовка учащихся 7 класса направлена на выступление их на олимпиаде муниципального уровня. Класс олимпиадных задач этого уровня имеет свою специфику. Здесь не обязательно виртуозно владеть техникой программирования на каком-либо из языков. Олимпиадные задачи составлены таким образом, что главным является нахождение оригинальной идеи решения, а технически такие задачи решаются достаточно просто (линейный алгоритм или вложенные циклы), даже без использования массивов. Эту основную идею я и применяю на начальном этапе подготовки школьников среднего звена.
Основной этап – развитие логики. (Приложение 1)
На этом этапе приоритетным направлением считаю решение большого количества интересных логических задач. Логические задачи очень нравятся ученикам такого возраста, при условии, что каждую из них учитель постарается облечь в форму какого-либо игрового интерактивного пособия. Конечно, это требует больших затрат времени самого учителя, но тем не менее эту работу необходимо проделать с целью повышения интереса учащихся. Когда задача оживает и превращается в увлекательную компьютерную игру, скучной математику уже не назовешь. Таким образом, задача учителя на этом этапе упаковать знания в интересную и актуальную для современных детей форму. Естественно, задачи подбираются не случайно, каждая должна скрывать один из базовых олимпиадных алгоритмов программирования, намеченных учителем для изучения на конкретном занятии. Приведу пример фрагмента такого занятия с использованием логической игры «В гостях у Льюиса Кэрролла».
Фрагмент занятия: «Числа Фибоначчи. Динамическое программирование»
Отправляясь вслед за белым кроликом и Алисой, мы попадаем в страну чудес, где в качестве разминки пройдем небольшой интерактивный логический тест по мотивам книги Льюиса Кэрролла «История с узелками». Как уже говорилось, важнейшим навыком этого этапа является выработка умения нестандартно мыслить, избавиться от каких-либо стереотипов, а кто как не этот писатель, математик, логик и философ поможет нам в этом.
Имеется десять мешков с золотыми монетами, в каждом мешке 10 монет. Все монеты весят по 10 граммов. Один мешок из десяти с фальшивыми монетами. Фальшивые монеты весят по 11 граммов. Как за одно взвешивание на весах со стрелками определить мешок с фальшивыми монетами?
После разминки, которая включает решение веселой логической задачи (Приложение 2), мы добираемся наконец до темы нашего занятия: «НАХОЖДЕНИЕ N-НОГО ЧИСЛА ФИБОНАЧЧИ»
Цель: Объяснить метод динамического программирования на примере известной ранее задачи. Найти оптимальный способ ее решения, оценить быстродействие различных методов решения. (Приложение 1)
Учащимся предлагается решить задачу, и отгадать ее автора. Так как ранее уже писался алгоритм нахождения n-ного числа Фибоначчи (без использования массивов, рекурсии и динамического программирования, то узнать известный алгоритм в новой формулировке (что собственно и является главным отличием класса олимпиадных задач), не составит большого труда.)
Некто приобрел пару кроликов и поместил их в огороженный со всех сторон загон. Сколько кроликов будет через год, если считать, что каждый месяц пара дает в качестве приплода новую пару кроликов, которые со второго месяца жизни также начинают приносить приплод? Кроме того отгадать кто же является автором задачи?
Ответ: 377 пар. В первый месяц кроликов окажется уже 2 пары: 1 первоначальная пара, давшая приплод, и 1 родившаяся пара. Во второй месяц кроликов будет 3 пары: 1 первоначальная, снова давшая приплод, 1 растущая и 1 родившаяся. В третьем месяце - 5 пар: 2 пары, давшие приплод, 1 растущая и 2 родившиеся. Продолжая рассмотрение по месяцам, можно установить связь между количествами кроликов в текущий месяц и в два предыдущих. Если обозначить количество пар через N, а через m - порядковый номер месяца, то Nm = Nm-1 + Nm-2 . С помощью этого выражения рассчитывают количество кроликов по месяцам года: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377.
Эта задача придумана итальянским ученым Фибоначчи, жившим в 13-м веке.
Числа Фибоначчи
Вычислить N-е число в последовательности Фибоначчи, — 1, 1, 2, 3, 5, 8, ... — в которой первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих.
Формат входных данных
Одно число 0 < N < 47.
Формат выходных данных
Одно число — N-й член последовательности.
Вспомним, что цель нашего урока на простом и известном примере разобрать, в чем состоит принцип динамического программирования, но не найти самое простое и эффективное решение задачи. Т.О. сейчас нам важен именно подход.
Напишем рекурсивной функцию следующего вида:
Function F(X:integer):longint;
Begin
if (X = 1) or (X = 2)
then F := 1
else F := F(X - 1) + F(X - 2)
end;
В этом случае примерно в середине четвертого десятка программа “подвешивает” самый быстрый компьютер, в то время как по правилам олимпиад редко отводится более 10 секунд на прохождение теста. Учащимся предлагается ответить на вопрос, почему так происходит? После того, как мы выясняем, что наша основная ошибка в том, что значение функции при одном и том же значении аргумента считается очень много раз, предлагается переписать данную функцию с использованием массивов, чтобы сделать ее заметно эффективнее, исключив повторный счет одних и тех же значений.
Var D : Array [1..50] of LongInt;
Опять срабатывает золотой закон программирования — выигрывая в скорости, проигрываем в памяти. Сначала массив заполняется значениями, которые заведомо не могут быть значениями нашей функции (пусть это будет ноль). При попытке вычислить какое-то значение, программа смотрит, не вычислялось ли оно ранее, и если да, то берет готовый результат. Функция принимает следующий вид.
Function F(X : integer) : LongInt;
Begin
if D[X] = 0
then
if (X = 1) or (X = 2)
then D[X] := 1
else D[X] := F(x - 1) + F(x - 2);
F := D[X]
End;
Упростим и это решение, избавившись от рекурсии вообще:
D[1] := 1; D[2] := 1;
For i := 3 to X do D[i] := D[i-1] + D[i-2];
Этот способ в несколько раз быстрее предыдущих.
Итак, метод динамического программирования часто помогает эффективно решить задачу, переборный алгоритм для которой потребовал бы экспоненциального времени. Идея метода состоит в сведении исходной задачи к решению некоторых ее подзадач с меньшей размерностью и использованием табличной техники для сохранения уже найденных ответов. Решение подзадач при этом происходит в порядке возрастания их размерности — от меньшей к большей. Преимущество динамического программирования заключается в том, что любая подзадача решается один раз, ее решение сохраняется и никогда не вычисляется заново. И конечно, очень важно, на каждом занятии показать, что существует множество способов решения одной задачи, и пусть вы не знаете какого-то сложного метода, секрет программирования в том, что всегда найдется альтернативный способ решения даже самой сложной задачи важно только проявить настойчивость. И даже в 7 классе, не зная совершенно ничего про динамическое программирование, классическую задачу этого метода можно решить несколькими вложенными операторами цикла или некой формулой. Например, задача о подсчете количества равносторонних треугольников, когда на вход программы подается количество уровней в фигуре (1 ≤ N ≤ 105) На рисунке приведена фигура, состоящая из 4-х уровней треугольников.
Приведем два примера:
Пример 1 (язык программирования Delphi (Pascal)):
Begin
readln(n);
k:=n*n;
if n>1 then
for i:=2 to n do
for j:=i to n do
if j<2*i then k:=k+j-i+1
else k:=k+2*j-3*i+2;
writeln(k);
end.
Пример 2(язык программирования Delphi (Pascal)):
Begin
readln(N);
a:=0; o:=0;
for i:=1 to N do begin
inc(a, i);
if((N mod 2=0) and (i mod 2<>0)) or ((N mod 2<>0) and (i mod 2=0)) then inc(o, a*2)
else inc(o, a); end;
writeln(o);
end.
Сложная задача, решена очень просто: без использования каких-либо специальных методов, т.е альтернативный путь есть всегда! Как говорил известный математик Д.Пойя: «Не делайте при помощи большего то, что можно сделать при помощи меньшего».
Сегодня информационные технологии направлены на то, что бы упростить и облегчить использование всех программных продуктов, олимпиадная же информатика направлена именно на то, чтобы научить детей думать и решать не простые задачи. Следовательно, уделяя особое внимание олимпиадной подготовке, мы сохраняем традиции классической информатики профильного уровня.
Источники информации:
- Картинки Flash- пособий заимствованы из фильма: «Alice in Wonderland»-2010 г. (Tim Burton)
- Рисунки и материалы свободно распространяемые в сети Internet.
- http://compsciences.ru/WebPage/p1.htm
- http://otherreferats.allbest.ru/mathematics/00126552_0.html
- Логические задачи с сайта: www.nazva.net
- Брудно А.Л., Каплан Л.И. — Московские олимпиады по программированию.
- http://www.math.ru/lib/files/pdf/alfutova.pdf