Олимпиадное программирование для школьников
Тематический план
Введение в курс
Входное тестирование. Задачи на школьную математику и программирование.
Главное: ты учишься. Ошибки — часть пути. Каждый WA — это шаг к AC!
Целочисленная арифметика
Теория чисел — раздел математики, занимающийся изучением чисел непосредственно как таковых, их свойств и поведения в различных ситуациях. Тема «Целочисленная арифметика» в большей степени уделяет внимание целым числам, их свойствам и алгоритмам работы с ними, которые используются при решении олимпиадных задач.- Задачи на целочисленное деление. Деление с округлением вверх и вниз. Пересечение отрезков. Циклические процессы
⇓ Цифры, последовательности и формулы.
⇓ Делимость и делители. Простые числа и проверка простоты (O sqrt(n)). Решето Эратосфена (O(n log log n))
Пишем функцию проверки числа на простоту с временной эффективностью O(sqrt(n)). Основная теорема арифметики- ⇓ Факторизация (разложение на простые множители) числа O(sqrt(n)*log(n)). Каноническое разложение числа на простые множители: поиск всех делителей числа; нахождение количества делителей числа.
Рассматриваем алгоритм факторизации натуральных чисел с временной сложностью O(sqrt(n)). Пишем функцию канонического разложения на языках программирования Python и C++.
Линейные алгоритмы
Линейные алгоритмы представляют собой класс алгоритмов, позволяющих решать задачи за линейную сложность , где — размерность задачи.
- Линейные алгоритмы (теоретический материал) Файл документ PDF, 815.2Кбайт
ГОАОУ «Центр поддержки одаренных детей «Стратегия» Липецкой области, к.т.н., доцент Шуйкова И.А. – директор, ООО «Яндекс. Технологии», Полднев А.В. – руководитель службы, МАОУ СамЛИТ г.о. Самара, Панькова М.Г. – учитель информатики, Первеев М.В. – студент Университета ИТМО
⇓ ТРЕНИРОВКА №1 (задачи на частичные суммы и два указателя).
⇓ ТРЕНИРОВКА №2 (разные задачи + задачи на события на прямой).
Нелинейные структуры данных
Для некоторых задач линейное хранилище - не лучший способ организации данных. С помощью эффективных реализаций нелинейных структур данных, вы можете работать с данными быстрее, тем самым ускоряя алгоритмы, которые основываются на них.
В основе map и set лежит такая нелинейная структура данных, как сбалансированное двоичное дерево поиска. Используя данные структуры данных можно получить производительность ,эквивалентную ( O(logn) ) для операций вставка/поиска/удаления.
Set. Dictionaries
Stack. Queue. Priority queue