Методика подготовки к районному этапу Всероссийской олимпиады школьников по информатике.
статья по информатике и икт на тему

Разбор задач олимпиадного характера.

Методика подготовки к районному этапу Всероссийской олимпиады школьников по информатике.

Материалы мастер-класса (презентация)

на РМО  учителей информатики.

учителя информатики и ИКТ

МОУ «Лицей №23»

Шуваловой Светланы Юрьевны.

В данной работе обобщены материалы, представленные мною на РМО учителей информатики в 2011, 2012 годах по итогам школьных этапов Всероссийской олимпиады школьников по информатике.

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

Слайд 1.

Цель олимпиады по информатике — способствовать поиску наиболее одаренных школьников.

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

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

Слайд 2.

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

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

Слайд 3.

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

Из опыта  олимпиад можно выделить наиболее часто встречающиеся разделы информатики, к которым с можно отнести тематику задач:

•   комбинаторика;
•   сортировка и поиск;
•   обработка последовательностей;
•   алгоритмы на графах;
•   элементы вычислительной геометрии.
•   перебор вариантов и методы его сокращения;
•   динамическое программирование.

Слайд 4.

Этапы решения олимпиадных задач:

• Разбор условия задачи.
• Формализация условия задачи.
• Разработка алгоритма решения задачи.
• Программная реализация алгоритма.
• Отладка и тестирование программы.
• Отправка решения на проверку.

Слайд 5.

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

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

Необходимо помнить при написании программы, — это сохранение редактируемых файлов во время тура.

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

Слайд 6.

Часто  встречающиеся  ошибки:

• Не соответствует формат ввода-вывода данных условию задачи

• Рассмотрены не все возможные случаи

• Не правильно задан тип данных (размерность)

• Потеря редактируемых файлов во время тура

Слайд 7.

Минимальная база знаний для олимпиады по информатике.

Язык программирования:

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

Типовые алгоритмы.

Слайд 8.

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

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

Слайд 9.

Интернет-ресурсы для подготовки к олимпиадам по информатике:

http://www.olympiads.ru

http://olympiads.mccme.ru/

http://algolist.manual.ru/

Разбор задач школьного тура олимпиады 2011 года.

Задача №1     «Запись музыки» (15 баллов)

Проверить, поместится ли на диске компьютера музыкальная композиция, которая длится  m минут и  n секунд, если свободное дисковое пространство 6 мегабайт, а для записи одной секунды звука необходимо 16 килобайт.

Алгоритм решения:

Использование расчетной формулы и условного оператора

Задача №2     «Кодовый замок сейфа» (20 баллов)

Из 10 букв нужно набрать 3. Повторение букв допустимо. Подсчитать количество возможных комбинаций кодов.

Алгоритм решения:

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

Задача №3     «Прямоугольник» (30 баллов)

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

Алгоритм решения:

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

Используется типовой алгоритм нахождения максимального (минимального ) элемента массива.

Задача №4     «Магический квадрат» (35 баллов)

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

Алгоритм решения.  Задача на способ заполнения двумерного массива.

 (индийский способ):

1. В середине верхней строки ставим 1, в последней строке соседнего справа столбца 2.
2. Следующие числа ставят в диагональном направлении.
3. Дойдя до правого края квадрата, переходят к крайней левой клетке ближайшей вышележащей строки.
4. Дойдя до верхнего края квадрата, переходят к самой нижней клетке соседнего справа столбика. Примечание. Дойдя до правой верхней угловой клетки, переходят к левой нижней.
5. Дойдя до уже занятой клетки, переходят к клетке, лежащей непосредственно под последней заполненной клеткой.
6. Если последняя заполненная клетка находится в нижнем ряду квадрата, переходят к самой верхней клетке в том же столбце.

Разбор задач школьного тура олимпиады 2012 года.

Задача 1.

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

Алгоритм решения:

Один из вариантов решения перебором:

var a,b,c,n,k:integer;

begin

write('n=');  readln (n);

for a:=1 to 9 do

  for b:=0 to 9 do

    for c:=0 to 9 do

        if a+b+c=n then

begin

writeln (a,b,c,'   ');

k:=k+1;

end;

  writeln;

 writeln ('k=',k) ;

  writeln;

end.

Второй вариант решения перебором:

Var  a,b,c,n,k,m: integer;

begin

write('n='); readln(n);

for m:=100 to 999 do

begin

c:=m mod 10;

b:= m div 10 mod 10;

a:= m div 100;

if a+b+c=n then

begin

write(m:5);

k:=k+1;

end;

end;

writeln('k=',k)

end.

Задача 2.    «Малыш и Карлсон». 

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

 Алгоритм решения:

Во внешнем цикле по одной из сторон комнаты (while p) резервируем место для ряда (р:=р+с), затем во внутреннем цикле по другой стороне (while m) проверяем, сколькими ковриками можно закрыть ряд, оператор m:=m+с резервирует место для коврика, а оператор kovrik:=kovrik+1 подсчитывает общее количество уложенных ковриков.

Программа на языке программирования Паскаль.

var   a, b, с, kovrik, m, p: integer;

begin

readln(a, b, с);

kovrik:= 0;

p:=  0;

while p < a do

begin

p:= p +  c;

m:=  0;

while m < b do

begin

m:= m + c;

kovrik:= kovrik + 1

end

end;

writeln (kovrik)

end.

Задача 3.    «Бактерии». 

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

 Ваша программа должна:

• Запросить число бактерий n;
• Выяснить и сообщить: через сколько суток, часов и минут колония бактерий прекратит свое существование или выдать сообщение, что колония вечна.

Пример ответа: Для n=A. Ответ – B суток C часов D минут (где A, B, C, D – числовые значения).

Алгоритм решения:

Программа на языке программирования Паскаль.

Var     a, b, c:   shortint;

t, n, v:   longint;

begin

Write (‘Начальная численность колонии  -');     readln ( n);

v:=1;

while n>0 do

        begin

t:= t + 1;                        { минуты}

n:= ( n - v ) * 2;             { бактерии}

v:= v * 2;                       { вирусы}

end;

a:= t div 1440;

b:= ( t – a * 1440) div 60;

c:= t – a - b;

Write ('Колония прекратит существование через  ',a, ' суток ', b, '  часов ', c , '   минут');

end.

Задача 4.

Дан прямоугольник со сторонами А и В, где А, В - натуральные числа. Начинаем отсекать от него квадраты (рис.1). Сколько таких квадратов можно отсечь, если каждый раз отсекается самый большой квадрат?

Алгоритм решения:

1 способ.

Для решения этой задачи нам нужны функции МАХ и MIN, для их определения используем подпрограммы-функции.

Введем:

• вспомогательные переменные X и Y (Y>=X), соответствующие уменьшающимся сторонам прямоугольника;
• вспомогательную переменную D, которая определяет уменьшение размеров прямоугольника после очередного отсечения наибольшего квадрата, сторона которого находится как X:=MIN(D,X).

Организуем цикл, в котором сторона Y уменьшается каждый раз на MIN(D,X) до тех пор, пока не останется последний квадрат или Y не станет меньше X. В последнем случае переименовываем стороны оставшегося прямоугольника как Y:=MAX(D,X) и X:=MIN(D,X) и продолжаем цикл.

Программа на языке программирования Паскаль.

var  a, b, d, k, x, y: integer;

function min ( i, j: integer): integer;

begin

if  i < j   then   min:=i

else min:=j

end;

function max ( i, j: integer): integer;

begin

if  i < j   then  max:=j      

else max:=i

end;

begin

repeat

Writeln ('vvedite dva naturalnix chisla');

Readln (a, b);

until (a>0) and (b>0);

k:=1;

x:=min(a,b);

y:=max(a,b);

while  x <> y  do

begin

k:=k+1;

d:=y-x;

y:=max(d,x);

x:=min(d,x);

end;

Writeln ( 'iskomoe chislo kvadratov:', k )

end.

2 способ.

Задачу можно решить с помощью стандартных функций PASCAL: Y DIV X и Y MOD X, используя алгоритм Евклида.

Алгоритм решения: 

Организуем цикл, в котором формируем остатки от деления r0, r1, r2,..., rn, rn+1 до тех пор, пока один из этих остатков не станет равен нулю rn+i =0. Таким образом, мы строим функцию порождения остатка от деления rn+i = rn mod rn-i, где r0= А и ri =В. Для той же самой системы остатков мы можем посчитать, сколько раз нацело укладывается остаток rn-i в rn.

{алгоритм Евклида}

var А, В, R0, R, R1, K: integer;

begin

repeat

Write ('ВВЕДИТЕ НАТУРАЛЬНОЕ ЧИСЛО   А = ');

Readln (А);

Write ('ВВЕДИТЕ НАТУРАЛЬНОЕ ЧИСЛО В<=А,  В = ');

Readln (В);

until (В > 0) and (А > 0) and (А >=В);

R0 := А;

R1 := В;

К := R0 div R1;

while  R0 mod R1 <> 0  do  

begin

R := R0 mod R1;

R0 := R1;

R1 := R;

К := К + R0 div R1

end;

Writeln ('ИСКОМОЕ ЧИСЛО КВАДРАТОВ  К = ',К);

end.