Презентация олимпиада по информатике (школьный этап)
презентация к уроку по информатике и икт на тему

Слайд 1

ВСЕРОССИЙСКАЯ ОЛИМПИАДА ШКОЛЬНИКОВ ПО ИНФОРМАТИКЕ школьный этап (программирование) в 2012-2013 учебном году

Слайд 2

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

Слайд 3

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

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

Задача 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.

Слайд 8

Второй вариантов решения перебором 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.

Слайд 9

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

Слайд 10

Программа на языке программирования Паскаль . 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 .

Слайд 11

Задача 3 . «Бактерии». Колония состояла из n бактерий (не более 30000). В нее попал вирус, который в первую минуту уничтожил одну бактерию, а затем разделился на два новых вируса. Одновременно каждая из оставшихся бактерий тоже разделилась на две новые. В следующую минуту возникшие два вируса уничтожили две бактерии, а затем все вирусы и бактерии снова разделились и так далее. Будет ли эта колония жить бесконечно долго или вымрет? Ваша программа должна: Запросить число бактерий n; Выяснить и сообщить, через сколько суток, часов и минут колония бактерий прекратит свое существование или выдать сообщение, что колония вечна. Пример ответа: Для n = A . Ответ – B суток C часов D минут (где A , B , C , D – числовые значения).

Слайд 12

Программа на языке программирования Паскаль . 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.

Слайд 13

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

Слайд 14

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) и продолжаем цикл.

Слайд 15

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.

Слайд 16

2 способ. Задачу можно решить с помощью стандартных функций PASCAL: Y DIV X и Y MOD X, используя алгоритм Евклида. Алгоритм решения : Организуем цикл, в котором формируем остатки от деления r 0 , r 1 , r 2 ,..., r n , r n+1 до тех пор, пока один из этих остатков не станет равен нулю r n+i = 0 . Таким образом, мы строим функцию порождения остатка от деления r n+i = r n mod r n-i , где r 0 = А и r i = В . Для той же самой системы остатков мы можем посчитать, сколько раз нацело укладывается остаток r n-i в r n .

Слайд 17

, {алгоритм Евклида} 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.