ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

ЗАНЯТИЕ 1 (doc)

1. Чемпионат мира по программированию под эгидой ACM.

1.1. Соревнования в интернете. Правила участия.

1.2. Задача, решение, тест. Правила оформления.

1.3. Командный и индивидуальный принципы соревнования на олимпиадах.

2. Введение в язык Си.

2.1. Создание консольного приложения в MICROSOFT VISUAL C++ 6.0.

2.2. Программа HELLO WORLD!

2.3. Переменные и их объявления

2.4. Вычисление суммы двух чисел. Формат ввода-вывода.

2.5. Биты. Байты. Слова.

2.6. Оператор присваивания.

2.7. Условный оператор.

3. Задачи.

http://acm.timus.ru: 1000 (A + B Problem).

http://acm.sgu.ru: 100 (A + B).

ЗАНЯТИЕ 2 (doc)

1. Арифметические и логические операции в языке Си.

1.1. Арифметические операции.

1.2. Логические операции.

1.3. Условный оператор и логические операции.

2. Системы счисления: двоичная, восьмеричная, десятичная и шестнадцатеричная системы счисления. Перевод чисел из одной системы счисления в другую.

3. Задачи.

http://www.topcoder.com/tc: SRM 195 (Rounder), SRM 325 (SalaryCalculator).

ЗАНЯТИЕ 3 (doc)

1. Операторы цикла: синтаксис и семантика.

1.1. Оператор for.

1.2. Оператор while.

1.3. Оператор do-while.

2. Многократный ввод-вывод. Понятие однократного и многократного ввода-вывода. Чтение данных до конца файла. Возвращаемое значение функции scanf.

3. Форматированный ввод-вывод. Формат целочисленных и вещественных данных.

4. Математические функции. Библиотека <math.h>. Алгебраические и тригонометрические функции. Функции округления. Вычисление степени числа. Константа .

5. Задачи

http://acm.uva.es/problemset: 113 (Сила криптографии), 408 (Однородный генератор), 10633 (На редкость простая задача), 10683 (Десятичные часы), 10783 (Сумма нечетных чисел).

http://acm.timus.ru: 1068 (Sum).

http://www.topcoder.com/tc: SRM 326 (AdditionCycles), SRM 343 (PersistentNumber), TCHS 29 (ReverseSums).

ЗАНЯТИЕ 4 (doc)

1. Массивы: определение, инициализация, обработка. Строка как массив символов.

2. Элементарные вычисления: набор задач.

3. Задачи

http://acm.uva.es/problemset: 591 (Коробка с кирпичами), 10035 (Простая арифметика), 10055 (Хашмат – смелый воин), 10071 (Назад к школьной физике), 10300 (Экологическая премия), 10302 (Суммирование полиномов), 10370 (Больше среднего), 10499 (Земля праведности), 11172 (Операторы сравнения).

ЗАНЯТИЕ 5 (doc)

1. Тернарный условный оператор: синтаксис, семантика, примеры.

2. Адреса, ссылки и указатели: определение и использование. Физические и логические адреса. Массивы и ссылки. Выделение памяти, функция malloc.

3. Функции: определение, структура, возвращаемое значение. Формальные и фактические параметры. Передача параметров по значению и по ссылке.

4. Рекурсия и итерация: факториал числа, степень числа aⁿ за линейное O(n) и логарифмическое O(log₂n) время, сумма цифр числа, биномиальный коэффициент , количество единиц в бинарном представлении числа n, функция Аккермана.

5. Задачи

http://acm.uva.es/problemset: 374 (Большой модуль), 10696 (f91), 10774 (Повторяющийся Иосиф), 10994 (Простое сложение).

ЗАНЯТИЕ 6 (doc)

1. Шаблоны: определение и использование.

2. Именованные области. Оператор расширения видимости. Директива using.

3. Стандартная библиотека шаблонов (STL). Алгоритмы. Контейнеры. Итераторы.

4. Векторы. Конструкторы. Вставка-удаление элементов. Использование итераторов для доступа к элементам.

5. Задачи.

http://www.topcoder.com/tc: SRM 193 (SwimmingPool), SRM 194 (Soccer), SRM 212 (YahtzeeScore), SRM 217 (FuelConsumption), SRM 253 (ObjectPacking), SRM 315 (RosePetals), SRM 322 (DerivativeSequence).

ЗАНЯТИЕ 7 (doc)

1. Наибольший общий делитель. Наименьшее общее кратное. Методы вычисления, свойства.

2. Расширенный алгоритм Евклида. Описание алгоритма. Примеры.

3. Диофантовы уравнения. Решение уравнения ax + by = c в целых неотрицательных числах. Теорема о существовании решения.

4. Обработка строк. Библиотека <string.h>. Длина строки. Конкатенация и копирование строк. Ввод-вывод строк при помощи функций gets и puts.

5. Задачи.

http://acm.uva.es/problemset: 10104 (Задача Евклида), 10407 (Простое деление), 10548 (Найти правильный размен), 10673 (Игра с округлением вниз и вверх), 10717 (Монетный завод).

ЗАНЯТИЕ 8 (doc)

1. Числа Фибоначчи. Рекурсивный и циклический методы вычисления. Рекурсивный метод вычисления с запоминанием. Формула Бине. Свойства чисел Фибоначчи.

2. Класс string. Обработка строк с помощью класса string: инициализация, конкатенация, ввод-вывод, вставка, удаление, поиск. Обработка подстрок. Потоковое чтение из строки.

3. Задачи

http://acm.uva.es/problemset: 495 (Замораживание Фибоначчи), 900 (Кирпичная стена), 10450 (Шум мирового кубка), 11000 (Пчела).

http://www.topcoder.com/tc: SRM 178 (Простой калькулятор), SRM 210 (Заглавная строка), SRM 246 (Склеивание), SRM 257 (Код замены), SRM 305 (Мультичтение).