Программирование, Python, C++, часть 3, Поляков К.Ю., 2019

Программирование, Python, C++, Часть 3, Поляков К.Ю., 2019.

   Книга представляет собой третью часть серии учебных пособий по программированию. В отличие от большинства аналогичных изданий, в ней представлены два языка программирования высокого уровня — Python и C++.
Пособие посвящено способам организации данных и алгоритмам их обработки. Рассмотрены различные методы сортировки массивов, сравнивается их эффективность. Изучается работа с текстовыми и двоичными файлами. Приведены примеры использования структур данных - словарей, стеков, очередей, деревьев, графов - при решении практических задач. Рассматривается метод динамического программирования и его применение в задачах комбинаторики, оптимизации и теории игр.
После каждого параграфа приводится большое число заданий для самостоятельного выполнения разной сложности и вариантов проектных работ.
Пособие предназначено для учащихся средней школы.




Что такое сортировка?
Сортировка — это перестановка элементов массива (списка) в заданном порядке.
Данные, которые сортируются, могут размещаться как в оперативной, так и в долговременной памяти (на жёстких дисках или флэш-накопителях).

Порядок сортировки может быть любым; числа обычно сортируют по возрастанию или убыванию значений, а символьные строки — по алфавиту.

Для массивов, в которых есть одинаковые элементы, используются понятия «сортировка по неубыванию» и «сортировка по невозрастанию».

Возникает естественный вопрос: «Зачем сортировать данные?». На него легко ответить, вспомнив, например, работу со словарями: сортировка слов по алфавиту ускоряет поиск нужного слова.

Программисты изобрели множество способов сортировки. В целом их можно разделить на две группы: 1) простые, но медленно работающие на больших массивах и 2) сложные, но быстрые. В этом параграфе мы изучим два классических метода из первой группы.

Содержание.
Предисловие.
Глава 1. Программирование на языке Python.
§1. Простые алгоритмы сортировки.
Что такое сортировка?.
Метод пузырька (сортировка обменами).
Метод выбора.
Выводы.
§2. Быстрые алгоритмы сортировки.
Сортировка слиянием.
Быстрая сортировка.
Сортировка в языке Python.
Выводы.
§3. Двоичный поиск.
Поиск в массиве.
Что такое двоичный поиск?.
Двоичный поиск в массиве данных.
Какой алгоритм поиска лучше?.
Двоичный поиск по ответу.
Выводы.
§4. Обработка файлов.
Какие бывают файлы?.
Принцип сэндвича.
Чтение данных.
Запись данных.
Вывод файла на экран.
Суммирование данных из файла.
Обработка массивов.
Обработка строк.
Выводы.
§5. Целочисленные алгоритмы.
Решето Эратосфена.
Квадратный корень.
Выводы.
§6. Словари.
Что такое словарь?.
Алфавитно-частотный словарь.
Перебор элементов словаря.
Выводы.
§7. Структуры.
Зачем нужны структуры?.
Классы.
Создание структур.
Что можно делать с полями структуры?.
Работа с файлами.
Сортировка.
Выводы.
§8. Стек, очередь, дек.
Что такое стек?.
Использование списка.
Вычисление арифметических выражений.
Скобочные выражения.
Как вызываются подпрограммы?.
Очередь.
Дек.
Выводы.
§9. Деревья.
Что такое дерево?.
Деревья поиска.
Обход дерева.
Использование связанных структур.
Вычисление арифметических выражений.
Модульность.
Выводы.
§10. Графы.
Что такое граф?.
Как описать граф?.
«Жадные» алгоритмы.
Минимальное остовное дерево.
Алгоритм Дейкстры.
Алгоритм Флойда-Уоршелла.
Использование списков смежности.
Некоторые задачи.
Выводы.
§11. Динамическое программирование.
Числа Фибоначчи.
Что такое динамическое программирование?.
Кошки и собаки.
Количество программ для исполнителя.
Двумерная задача.
Поиск оптимального решения.
Выводы.
§12. Игровые модели.
Выигрышные и проигрышные позиции.
Кто выиграет?.
Динамическое программирование.
Игра с фишками.
Выводы.
Глава 2. Программирование на языке C++.
§13. Простые алгоритмы сортировки.
Метод пузырька (сортировка простыми обменами).
Сортировка вставками.
Массивы в подпрограммах.
Выводы.
§14. Быстрые алгоритмы сортировки и поиска.
Сортировка слиянием.
Быстрая сортировка.
Стандартная сортировка в языке C++.
Двоичный поиск.
Выводы.
§15. Обработка файлов.
Принцип сэндвича.
Файловые потоки.
Неизвестное количество данных.
Обработка массивов.
Чтение файлов по словам.
Построчная обработка файлов.
Как передать имя файла программе?.
Выводы.
§16. Целочисленные алгоритмы.
Решето Эратосфена.
«Длинные» числа.
Выводы.
§17. Динамические массивы и словари.
Зачем это нужно?.
Динамические массивы.
Тип vector из библиотеки STL.
Итераторы.
Зачем нужны итераторы.
Словари.
Перебор элементов словаря.
Выводы.
§18. Структуры.
Структуры в C++.
Обращение к полям структуры.
Работа с файлами.
Сортировка.
Выводы.
§19. Стек, очередь, дек.
Стек.
Очередь.
Хранение очереди в массиве.
Дек.
Выводы.
§20. Деревья.
Деревья в C++.
Обходы дерева.
Деревья поиска.
Вычисление арифметических выражений.
Дерево в массиве.
Модульность.
Выводы.
§21. Графы.
Графы в языке C++.
Задача коммивояжёра.
Задача коммивояжёра: жадный алгоритм.
Задача коммивояжёра: случайные перестановки.
Как избавиться от глобальных переменных?.
Передача данных по ссылке.
Выводы.
§22. Динамическое программирование.
Одномерные задачи.
Редактирование строк.
Оптимальная стратегия.
Выводы.

Купить .





Теги: учебник по программированию :: программирование :: Поляков