План подготовки к олимпиадам по информатике

Вот примерный план подготовки к олимпиадам по информатике

Соревнования и турниры

Яндекс.Алгоритм-2018

Яндекс.Алгоритм-2017

Яндекс.Алгоритм-2016

Яндекс.Алгоритм-2015

Яндекс.Алгоритм-2014

Курс Цегельного Виталия

Целочисленная арифметика
1.Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация

Рекрсия
2. Определение простоты числа.
3. Нахождение всех простых чисел из промежутка (a,b).
4. Разложение данного натурального числа на простые множители.
5. Дано разложение данного натурального числа на простые множители. Найти все делители этого числа.
6. Нахождение всех делителей натурального числа.
7. Нахождение цифрового корня натурального числа.
8. Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация
9. Длинная арифметика:
a) Считывание длинного числа из файла.
b) Запись длинного числа в файл.
c) Сложение двух длинных чисел
d) Умножение длинного числа на короткое в системе счисления с основанием 1000.
e) Умножение длинного числа на длинное.
f) Деление длинного на короткое
g) Вычисление n! и степени an при маленьких и больших значениях a и n, рекурсивная и нерекурсивная реализация.
h) Индийский алгоритм вычисления an
i) Дано натуральное число N. Найти последнюю ненулевую цифру суммы a1+a2+…+ak, где N=p1a1*p2a2*…*pkak.
j) Дано натуральное число N. Найти последнюю ненулевую цифру числа N!
k) Даны натуральные числа N и M. Найти последнюю ненулевую цифру числа сочетаний C из N по M.
l) Даны натуральные числа N и M. Вычислить число сочетаний C из N по M.
m) Найти все натуральные числа, не превосходящие данного натурального N, десятичная запись которых есть строго убывающая или строго возрастающая числовая последовательность. (длинная арифметика).

Одномерные массивы
1. Объявление и использование массивов.
2. Создание массивов:.вручную, по формуле, генератором случайных чисел, чтение из файла
3. Виды сортировок. Внешняя и внутренняя сортировка
4. Сортировка выбором.
5. Сортировка «пузырьком».
6. Сортировка Шелла.
7. Сортировка слиянием.
8. Внешняя сортировка слиянием.
9. Кучи. Сортировка с помощью кучи.
10. Сортировка подсчётом.
11. Хэширующая сортировка.
12. Цифровая сортировка
13. Сквозной поиск элемента в массиве.
14. Бинарный поиск элемента в массиве.
15. Извлечение корня n-ой степени из данного натурального числа.
16. Вычисление значения многочлена по схеме Горнера.
Двумерные массивы
Создание двумерных массивов.
Задачи на двумерные массивы:
1 Нахождение максимального и минимального элементов массива.
2 Сортировка массива по возрастанию и убыванию в строках и столбцах.
3 Поменять местами первую и последнюю строки (столбцы).
4 Отобразить массив симметрично относительно горизонтальной оси.
5 Отобразить массив симметрично относительно вертикальной оси.
6 Отобразить массив n*n симметрично относительно главной диагонали
7 Отобразить массив n*n симметрично относительно побочной диагонали
8 Повернуть массив n*n против часовой стрелки на 90 градусов.
9 На шахматной доске стоит слон и еще несколько фигур. Сколько клеток контролирует слон?

Создание трехмерных массивов.

Генерация комбинаторных объектов
1. Понятие «комбинаторных» алгоритмов.
2. Получение комбинаторных объектов.
3. Задачи:
— Сгенерировать все последовательности длины n из чисел от 1 до k.
— Сгенерировать все подмножества n-элементного множества.
— Сгенерировать все перестановки чисел от 1 до N.
— Сгенерировать все k-элементные подмножества n-элементного множества.
— Сгенерировать все представления числа N в виде суммы натуральных чисел.
— Код Грея и сходные задачи.
— Генерация перестановок методом транспозиции соседних элементов.
— Числа Каталана. Расстановка скобок.
Обработка текста
1.Процедуры и функции обработки текста на Паскале
2. Функции eof и eoln.
3. Функции seekeof и seekeoln.
4. Посимвольная обработка текста.
5. Отличие процедур read и readln.
5. Поиск заданной подстроки в тексте. Алгоритм Бойера-Мура.
7. Использование хэш-функции для поиска произвольной подстроки в строке.
8. Рекурсивный синтаксический анализ скобочных выражений.
Динамическое программирование
Концепция динамического программирования Сохранение решений, подзадач, которые приходится решать повторно или несколько раз. Построение динамических таблиц промежуточных результатов.
Структуры данных
1. Элементарная структура данных — запись.
Линейный список.
2. Специальные структуры данных: стек, очередь, дек.
3. Деревья. Упорядоченные деревья.
4. Обходы деревьев.
5. Двоичные деревья, деревья поиска.
6. Обходы двоичных деревьев.
7. Поиск элемента в дереве поиска.
8. Добавление/удаление элемента.

Объяснение на все задания планирую размещать на своём канале

Подписывайтесь и следите за новыми публикациями

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *