Тематика вопросов по основам программирования Часть 2.
Тематика вопросов по основам программирования.
Часть 2.
- Повторение. УКАЗАТЕЛИ. Описание указателей. Операция взятия адреса: &. Операция косвенной адресации: * Адресная арифметика.
- Повторение. ПРОИЗВОДНЫЕ ОДНОРОДНЫЕ ТИПЫ ДАННЫХ. МАССИВЫ. Описание массивов. Инициализация массивов. Доступ к элементам массива. Символьные строки и массивы указателей. Приемы обработки массивов.
- ПРОИЗВОДНЫЕ СМЕШАННЫЕ ТИПЫ ДАННЫХ. Структуры. Описание структурных переменных. Операции над структурами. Указатели и структуры.
- ПЕРЕЧИСЛЕНИЯ. Описание перечислимого типа. Пример использования перечислений
- ВВОД-ВЫВОД ДАННЫХ. Ввод-вывод символа. Форматный ввод-вывод строк
- ФУНКЦИИ. Виды функций. Определение функции. Вызов функции. Аргументы функции. Передача аргументов и возврат значений. Указатели в качестве аргументов. Массивы в качестве аргументов. Описание типа возвращаемого значения.
- КЛАССЫ ПАМЯТИ. Понятие класса памяти. Автоматические переменные. Внешние переменные. Статические переменные. Регистровые переменные
- БИТОВЫЕ ПОЛЯ.
- СМЕСИ.
- СОБСТВЕННЫЕ ИМЕНА ТИПОВ.
- ФАЙЛЫ. Типы файлов. Работа с текстовыми и двоичными файлами. Открытие и закрытие файлов. Ввод-вывод символа . Ввод-вывод форматный. Ввод-вывод строк. Ввод-вывод в двоичных файлах. Позиционирование доступа к файлу. Пример отработки файла.
- ПРЕПРОЦЕССОР. Определение символических констант. Определение макрофункций. Включение файлов. Условная компиляция. Другие директивы.
- СПИСКИ. Использование списков: добавление, удаление, печать элементов списка.
- СТЕКИ . Реализация стека с помощью списка. Добавление элемента в стек. Извлечение элемента из стека. Преобразование выражения в обратную польскую запись (Полиз) с использованием стека. Вычисление выражения в обратной польской записи. Программа перевода и вычисления арифметического выражения в ОПЗ
- ОЧЕРЕДИ (queue). ДВУНАПРАВЛЕННЫЕ СПИСКИ (double ended queue – deck).Программа, демонстрирующая работу с очередью. Двусвязные списки (Doubly linked list).Двусторонняя очередь (Double-ended queue – deck). Циклические списки. Решение задачи Иосифа при помощи циклического списка. Понятие об очереди с приоритетом.
- МЕТОДЫ ПРОГРАММИРОВАНИЯ.
16.1. Метод рекурсии. Понятие рекурсии. Свойства рекурсивных алгоритмов. Задача о ханойской башне (Фрактальная природа, Бинарный алгоритм, Графическое представление игры). Опасности рекурсии. Другие примеры рекурсии.
16.2. Метод разделяй и властвуй (Divide et Impera algorithms). Задача о нахождении наибольшего и наименьшего элементов. Умножение двух n-разрядных двоичных чисел. Сортировка слиянием (рекурсивная). Сортировка слиянием (итеративная).
16.3. Метод перебора с возвратом (Backtracking algorithms). Задача о велосипедном замке. Общая схема алгоритма перебора с возвратом.
Задачи, решаемые методом исчерпывающего поиска - перебора с возвратом):
Головоломка 8
Задача об обходе конём шахматной доски
Задача о восьми ферзях
Генерация комбинаторных объектов
Оценка сложности алгоритмов с возвратом
Задача о паросочетаниях на примере задачи о стабильных браках
16.4. Метод жадных алгоритмов (Greedy algorithms).
16.5. Динамическое программирование.