А. А. АНДРИАНОВА, Л. Н. ИСМАГИЛОВ, Т. М. МУХТАРОВА АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ ПРАКТИКУМ Учебное пособие Издание третье, стереотипное •САНКТПЕТЕРБУРГ•МОСКВА•КРАСНОДАР• 018я723 А 65 Андрианова А. А. Алгоритмизация и программирование. Прак тикум : учебное пособие для СПО / А. А. Андрианова, Л. Н. Исма гилов, Т. М. Мухтарова. — 3е изд., стер. — СанктПетербург : Лань, 2024. — 240 с. : ил. — Текст : непосредственный. !5!507!50372!8 В пособии будут рассмотрены базовые приемы алгоритмизации, которые являются основой для решения более сложных задач программирования: проиллюстрированы основные понятия алгоритмизации (ветвление, циклы различных видов), базовые алгоритмы работы с основными структурами данных (массивами, символьными строками, матрицами). Отдельные главы учебного пособия посвящены структурированию программ (созданию поль зовательских функций), а также работе с более сложными структурами данных (списками, деревьями, графами). Приведенные в учебном пособии примеры программ написаны на языках программирования C++ и C#, которые на данный момент являются одними из самых популярных универ сальных языков программирования. Соответствует современным требованиям Федерального государствен ного образовательного стандарта среднего профессионального образования и профессиональным квалификационным требованиям. Данное учебное пособие предназначено для обучающихся по направ лениям группы «Информатика и вычислительная техника» среднего профессионального образования, начинающих изучать программирование. 018я723 Обложка П. И. ПОЛЯКОВА © Издательство «Лань», 2024 © Коллектив авторов, 2024 © Издательство «Лань», художественное оформление, 2024 Оглавление Введение ................................................................................................ 5 . Простейшие алгоритмические конструкции ....................... 9 1.1. Блок условия .................................................................................. 9 Домашнее задание .............................................................................. 22 1.2. Цикл ПОКА (цикл с условием) .................................................. 24 Домашнее задание .............................................................................. 31 1.3. Цикл ДЛЯ (цикл с параметром) ................................................. 33 Домашнее задание .............................................................................. 41 . Основные структуры данных.............................................. 43 2.1. Массивы........................................................................................ 43 Домашнее задание .............................................................................. 66 2.2. Символьные строки ..................................................................... 68 Домашнее задание .............................................................................. 84 2.3. Двумерные массивы (матрицы).................................................. 85 Домашнее задание ............................................................................ 106 . Структура программы ....................................................... 108 3.1. Функции...................................................................................... 108 Домашнее задание ............................................................................ 135 3.2. Рекурсивные функции ............................................................... 139 Домашнее задание ............................................................................ 147 3 / 24 . Линейные динамические структуры данных .................. 150 4.1. Односвязные списки.................................................................. 150 Домашнее задание ............................................................................ 166 4.2. Стеки и очереди ......................................................................... 169 Домашнее задание ............................................................................ 175 4.3. Двусвязные списки .................................................................... 181 Домашнее задание ............................................................................ 188 . Нелинейные структуры данных ....................................... 190 5.1. Деревья ....................................................................................... 190 Домашнее задание ............................................................................ 206 5.2. Графы .......................................................................................... 207 Домашнее задание ............................................................................ 233 Литература......................................................................................... 235 4 / 24 Введение Алгоритм – это точно определенное описание способа решения задачи в виде конечной последовательности действий, ведущей от варьируемых начальных данных к искомому результату. Основное требование при составлении алгоритма заключается в его применимости для решения всех частных случаев решаемой задачи. Алгоритмы реализуются на языках программирования. Все языки программирования являются искусственными языками, т. е. оперируют очень небольшим количеством команд, которые являются своеобразными «кирпичиками» программирования. В способности строить алгоритмы любой сложности из этих «кирпичиков» и заключается искусство программирования. Помимо языков программирования существует еще целый ряд способов записи алгоритма, к числу которых относятся, в частности, блок-схемы и псевдокод. В данном учебном пособии для целей пояснения алгоритмов в первых двух главах пособия мы будем использовать блок-схемы, поскольку они являются наиболее наглядной и понятной формой записи алгоритма. Блок-схема – это графическая интерпретация алгоритма. Каждый вид действия в ней обозначается с помощью некоторой геометрической фигуры (блока), внутри которой делается запись, конкретизирующая его смысл. Блоки блок-схемы связаны с помощью линий потока, определяющих ход выполнения вычислительного процесса. Поток начинается в специальном блоке начала алгоритма и заканчивается в блоке конца алгоритма. Обозначения основных блоков, используемых в блок-схеме, приведены в таблице 1. Учебное пособие состоит из пяти глав. Первая глава посвящена рассмотрению основных конструкций построения алгоритмов. Она разделена на три раздела: «Блок условия», «Цикл ПОКА (цикл с условием)», «Цикл ДЛЯ (цикл с параметром)». Во второй главе приводятся основные алгоритмы работы с основными составными структурами данных. Эта глава также разделена на три раздела, посвященных работе с массивами, символьными строками и двумерными массивами (матрицами). Третья глава посвящена принципам структурного программирования. Решение сложных задач обычно заключается в составлении большого алгоритма и соответственно в написании длинного программного кода его реализации. Для более эффективной разработки осуществляется разбиение этого алгоритма на небольшие и относительно независимые составные части, каждая из которых решает менее сложную отдельную подзадачу. Каждая из этих составных частей оформляется в 5 / 24 виде отдельной подпрограммы, которая называется функцией. Таким образом, третья глава учебного пособия посвящена разбору основных приемов декомпозиции программы и разработки функций. Она состоит из двух разделов – «Функции» и «Рекурсивные функции». Таблица 1. Обозначения основных блоков блок-схемы Блок начала блок-схемы Блок конца блок-схемы Блок действия. Обычно обозначает присваивание значения некоторой переменной, например на основе вычисления ее значения Блок ввода значений. Значения вводятся в перечисленные в блоке переменные Блок вывода значений перечисленных в блоке переменных Условный блок, или блок ветвления. В зависимости от условия алгоритм разделяется на две ветви – ветвь выполнения условия (ветвь «ДА») и ветвь нарушения условия (ветвь «НЕТ») Блок цикла. Это блок повторения некоторой последовательности действий (итерации цикла). В блоке цикле должно быть предусмотрено указание условия выхода из цикла 6 / 24 Четвертая глава учебного пособия посвящена использованию линейных динамических структур данных. Их главная особенность – нефиксированный размер данных, в отличие от массивов и матриц, при создании которых явно указывается их размер. Глава состоит из трех разделов, каждый из которых посвящен отдельным видам линейных динамических структур: односвязным спискам, стекам и очередям, двусвязным спискам. Для рассмотренных структур данных описываются основные операции работы с ними и приводится ряд приложений их использования. Пятая глава учебного пособия посвящена построению и использованию нелинейных структур данных на примере деревьев и графов. Рассматриваются принципы создания, хранения и работы с ними. Глава состоит из двух разделов – «Деревья» и «Графы». В каждом разделе пособия приведено теоретическое описание приемов работы с рассматриваемыми конструкциями, подробно разбирается несколько задач, а также приводится список задач для самостоятельного решения в виде домашнего задания (в некоторых случаях с методическими указаниями). Задачи имеют собственную нумерацию внутри разделов. Номера рисунков имеют нумерацию вида «Номер_главы.Номер_раздела.Номер_рисунка». Аналогичным образом строится нумерация приведенных листингов программного кода «Номер_главы.Номер_раздела.Номер_листинга». При разборе каждой задачи приводится ее постановка, краткое обсуждение используемого алгоритма решения, блок-схема алгоритма для задач из первых двух глав, а также программный код с комментариями, написанный на двух языках программирования – С++ и C#. Программы были созданы и отлажены с помощью оболочки проектирования Microsoft Visual Studio 2017. Отметим, что в пособии намеренно не используется большинство объектно-ориентированных возможностей выбранных языков программирования, а также не рассматриваются подробно синтаксические особенности языков. Это сделано, чтобы акцентировать внимание читателя на алгоритмических аспектах решения задач. Большинство описаний решаемых задач будет содержать программный код лишь на одном из выбранных языков программирования. Это обусловлено незначительными отличиями этих языков при реализации алгоритмов, которые в основном заключаются в способах организации ввода и вывода информации. Тем не менее мы не будет уделять одному языку больше внимания, чем другому, чтобы предоставить читателю примеры реализации сходных алгоритмов на разных языках программирования. Это позволит также провести сравнительную характеристику языков программирования, оценить их технологические особенности. В тех случаях, когда языки программирования имеют технологические 7 / 24 особенности, которые можно использовать при решении задачи, примеры программного кода будут приведены на обоих языках программирования. При формировании блок-схем в первых двух главах мы будем пользоваться некоторыми обозначениями, принятыми для языка программирования C++. Некоторые из них используются также и в других языках программирования. Эти обозначения приведены далее в таблице 2. Таблица 2. Обозначения некоторых операций и символов, используемые в блок-схемах Операция вычисления остатка от деления Операция деления, также операция целочисленного деления в случае целых операндов Операция сравнения «не равно» Получение элемента массива по индексу ‘\0’ EOL – признак конца строки sqrt(x) Функция вычисления квадратного корня из числа x 8 / 24 . Простейшие алгоритмические конструкции 1.1. Блок условия Достаточно часто возникает ситуация, когда результат работы алгоритма зависит от выполнения того или иного условия. В этом случае требуется выполнить одну из нескольких альтернативных последовательностей действий. Для задания возможных альтернатив используется блок условия (или, как его еще называют, блок ветвления, логический блок). Основой этой конструкции является логическое условие. Если условие истинно, выполняются команды, следующие по ветви «Да» (+). В противном случае – команды из ветви «Нет» (–). Блок условия завершен, когда обе ветви соединяются для продолжения единого вычислительного процесса алгоритма. Например, пусть даны две переменные и . Если < , переменная должна принимать значение 1, иначе – значение 2. Фрагмент блок-схемы с таким условным блоком приведен на рис. 1.1.1. Рис. 1.1.1. Пример блока условия (логического блока) Задача 1. Вычислить значение функции 1, если > 0 ( ) = −1, если < 0 0, если = 0 Алгоритм решения данной задачи очень прост. Сначала требуется ввести значение переменной x, которая является аргументом функции. Далее следуют два блока условия для выделения трех вариантов вычисления функции. Результат вычислений распечатывается. Блок-схема решения задачи 1 приведена на рис. 1.1.2, а программный код – в листинге 1.1.1. 9 / 24 Рис. 1.1.2. Блок-схема для задачи вычисления функции sign(x) #include #include using namespace std; int main() // включение русских букв setlocale(LC_CTYPE, "rus"); // ввод исходных данных задачи double x, y; cout << "Введите x: "; cin >> x; // вычисление функции sign(x) if (x > 0) y = 1; else if (x < 0) y = -1; else y = 0; cout << "y = sign(" << x << ") = " << y << endl; return 0; Листинг 1.1.1. Программный код решения задачи 1 на языке C++ Нередко бывает необходимо осуществить выбор, заданный группой условий. Эти условия можно объединить с помощью логических операций. Существуют три основные логические операции – логическое НЕ, логическое ИЛИ и логическое И. С их помощью можно комбинировать несколько условий в блоке ветвления. Приоритет выполнения операций можно изменить с помощью круглых скобок. Следующие задачи демонстрируют применение этих логических операций в алгоритмах. 10 / 24