Уроки по программированию

Тематика вопросов по основам программирования.

Часть 2.

1. Повторение. УКАЗАТЕЛИ. Описание указателей. Операция взятия адреса: &. Операция косвенной адресации: *  Адресная арифметика.
2. Повторение. ПРОИЗВОДНЫЕ ОДНОРОДНЫЕ ТИПЫ ДАННЫХ. МАССИВЫ. Описание массивов. Инициализация массивов. Доступ к элементам массива. Символьные строки и массивы указателей. Приемы обработки массивов.
3. ПРОИЗВОДНЫЕ СМЕШАННЫЕ ТИПЫ ДАННЫХ. Структуры. Описание структурных переменных. Операции над структурами. Указатели и структуры.
4. ПЕРЕЧИСЛЕНИЯ. Описание перечислимого типа. Пример использования перечислений
5. ВВОД-ВЫВОД ДАННЫХ. Ввод-вывод символа. Форматный ввод-вывод строк
6. ФУНКЦИИ. Виды функций. Определение функции. Вызов функции. Аргументы функции. Передача аргументов и возврат значений. Указатели в качестве аргументов. Массивы в качестве аргументов. Описание типа возвращаемого значения.
7. КЛАССЫ ПАМЯТИ. Понятие класса памяти. Автоматические переменные. Внешние переменные. Статические переменные. Регистровые переменные
8. БИТОВЫЕ ПОЛЯ.
9. СМЕСИ.
10. СОБСТВЕННЫЕ ИМЕНА ТИПОВ.
11. ФАЙЛЫ. Типы файлов. Работа с текстовыми и двоичными файлами. Открытие и закрытие файлов. Ввод-вывод символа . Ввод-вывод форматный. Ввод-вывод строк. Ввод-вывод в двоичных файлах. Позиционирование доступа к файлу. Пример отработки файла.
12. ПРЕПРОЦЕССОР. Определение символических констант. Определение макрофункций. Включение файлов. Условная компиляция. Другие директивы.
13. СПИСКИ.  Использование списков: добавление, удаление, печать элементов списка.
14. СТЕКИ . Реализация стека с помощью списка. Добавление элемента в стек. Извлечение элемента из стека. Преобразование выражения в обратную польскую запись (Полиз) с использованием стека. Вычисление выражения в обратной польской записи. Программа перевода и вычисления арифметического выражения в ОПЗ
15.  ОЧЕРЕДИ (queue). ДВУНАПРАВЛЕННЫЕ СПИСКИ (double ended queue – deck).Программа, демонстрирующая работу с очередью. Двусвязные списки (Doubly linked list).Двусторонняя очередь (Double-ended queue – deck). Циклические списки. Решение задачи Иосифа при помощи циклического списка. Понятие об очереди с приоритетом.
16. МЕТОДЫ ПРОГРАММИРОВАНИЯ.

16.1. Метод рекурсии. Понятие рекурсии. Свойства рекурсивных алгоритмов. Задача о ханойской башне (Фрактальная природа, Бинарный алгоритм, Графическое представление игры). Опасности рекурсии. Другие примеры рекурсии.

16.2. Метод разделяй и властвуй (Divide et Impera algorithms). Задача о нахождении наибольшего и наименьшего элементов.  Умножение двух n-разрядных двоичных чисел. Сортировка слиянием (рекурсивная). Сортировка слиянием (итеративная).

16.3. Метод перебора с возвратом (Backtracking algorithms). Задача о велосипедном замке. Общая схема алгоритма перебора с возвратом.

Задачи, решаемые методом исчерпывающего поиска - перебора с возвратом):

Головоломка 8

Задача об обходе конём шахматной доски

Задача о восьми ферзях

Генерация комбинаторных объектов

Оценка сложности алгоритмов с возвратом

Задача о паросочетаниях на примере задачи о стабильных браках

16.4. Метод жадных алгоритмов (Greedy algorithms).
16.5. Динамическое программирование.