В начале … Задача ! Потерялся бочонок из игры в русское лото ( всего в игре 90 бочонков ). А у нас нет ни карандаша, ни бумаги, ни места, чтобы разложить. - презентация

1 В начале … Задача ! Потерялся бочонок из игры в русское лото ( всего в игре 90 бочонков ). А у нас нет ни карандаша, ни бумаги, ни места, чтобы разложить бочонки в ряд. Есть только самый простой калькулятор. Как определить, какого номера не хватает ?

2 Не совсем обычный курс компьютерных технологий Ильин Владимир Владимирович, преподаватель программирования лицея « Вторая школа », преподаватель Летней компьютерной школы

3 Мой первый компьютер БК Быстродействие Не менее 0,3 млн. операций в секунду Ёмкость оперативного запоминающего устройства ( ОЗУ ) 32 к Байт Скорость обмена информацией с кассетным магнитофоном 1200 бит в секунду Ёмкость накопителя на компакт - кассете типа МК -60 не более 0.5 Мбайт

4 Сейчас собираюсь покупать Lenovo ThinkPad Edge E120 Частота процессора 1200 МГц ( БК x 4000 ) Память ОЗУ 2048 Мб ( БК х 65536) Жёсткий диск HDD 320 Гб ( БК х )

5 Важно понимать : при этом мало что изменилось ! Не изменился основной принцип : компьютеры стали намного быстрее, « вместительнее », но не умнее. Думать по - прежнему приходится человеку - программисту ! Иначе ни памяти, ни быстродействия будет по - прежнему не хватать.

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

7 Памяти по - прежнему не хватит, чтобы записать число А ответить на вопрос, какими цифрами оно заканчивается – вполне можно !

8 Компьютер с легкостью может хранить карту пробок Но научить компьютер отыскивать маршрут объезда по - прежнему должен программист !

9 Олимпиадники занимаются решением подобных задач « в чистом виде » ! * Конечно многие алгоритмы находят серьёзные практические применения ! Им очень нужно перевезти на меленькой лодке на другой берег волка, козу и капусту и их не волнует вопрос « зачем ?».*

10 Курс ^^^^ Практически без наглядности Длинные лекции без компов Много самостоятельной работы

11 Курс ^^^^ Практически без наглядности Длинные лекции без компов Много самостоятельной работы

12 Математика Даны натуральные числа a и b. Каждое до миллиарда. Сколько нулей содержит произведение всех простых чисел от a до b? Собственно, алгоритмы Дан список из миллиона чисел, упорядоченный по возрастанию : 2, 7, 28, 135… Сколько нужно сделать проверок, чтобы определить, есть ли в списке данное число ?

13 Во многих случаях в курсе будет рассказываться как применить мощные языковые средства Java и классы стандартной библиотеки для упрощения кодирования. out.println(str.trim().split( ).length)

14 Занятия рассчитаны на 4 модуля (4 семестра, 2 года ). Первый модуль – базовые простые алгоритмы. Второй модуль – более сложные базовые алгоритмы. Цель первых двух модулей – формирование умелого использования управляющих конструкций для записи алгоритмов. Третий и четвёртый модули – сложные алгоритмы. Цель третьего и четвёртого модулей – изучение нетривиальных алгоритмов и применение их в решении олимпиадных задач.

15 Специфика решения олимпиадных задач Правила участия в личных и командных олимпиадах Работа с отладчиком

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

17 Разбор задачи Сложим номера всех оставшихся бочонков. А сумму чисел от 1 до 100 посчитал в своё время еще Гаусс. У нас 90. Вычтем наше полученное на калькуляторе число из 4095!

18 if (x > 0) sgn = 1; if (x == 0) sgn = -1; if (x < 0) sgn=0; Написать программу, вычисляющую знак числа без if! 1, если x > 0 F(x) = 0, если x = 0 -1, если x < 0 sgn = x / Math. abs(x); не работает для нуля !

19 IMHO (In My Humble Opinion) « Профессиональным » « олимпиад ником » становиться вовсе необязательно, но попробовать, « приобщиться к этому миру », стоит однозначно !