Алгоритмизация в инженерных задачах

С. В. Степошина, О. Н. Федонин, С. Ю. Съянов





            АЛГОРИТМИЗАЦИЯ
            В ИНЖЕНЕРНЫХ ЗАДАЧАХ



Учебное пособие























Москва Вологда
« Инфра-Инженерия» 2023

УДК 004.421
ББК 30.2
      С79

Рецензенты:
доктор технических наук С. Я. Алибеков; кандидат технических наук А. А. Медяков




    Степошина, С. В.
С79 Алгоритмизация в инженерных задачах : учебное пособие / С. В. Степошина, О. Н. Федонин, С. Ю. Съянов. - Москва ; Вологда : Инфра-Инженерия, 2023. - 116 с. : ил., табл.
          ISBN 978-5-9729-1456-2

          Описаны основные конструкции языка программирования высокого уровня С++. Рассмотрены численные методы и алгоритмы их программирования для решения инженерных и прикладных задач.
          Для студентов направлений подготовки 15.03.04 «Автоматизация технологических процессов и производств», 15.03.06 «Мехатроника и робототехника» и 27.03.04 «Управление в технических системах».

УДК 004.421
ББК 30.2















ISBN 978-5-9729-1456-2

     © Степошина С. В., Федонин О. Н., Съянов С. Ю., 2023
     © Издательство «Инфра-Инженерия», 2023
                            © Оформление. Издательство «Инфра-Инженерия», 2023

            ОГЛАВЛЕНИЕ



ПРЕДИСЛОВИЕ.................................................5

ГЛАВА 1. ОСНОВНЫЕ КОНСТРУКЦИИ ЯЗЫКА C++.....................6
1.1. Понятие алгоритма......................................6
1.2. Понятие типа данных...................................10
1.3. Знаки операций в C++..................................12
1.4. Применение функций....................................15
1.5. Базовые конструкции структурного программирования.....16
1.6. Операторы языка C++...................................18
1.7. Разработка алгоритмов.................................24
1.8. Статические структуры данных..........................25
1.9. Применение графов.....................................29
1.10. Примеры решения задач................................42
Контрольные вопросы........................................45

ГЛАВА 2. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ УРАВНЕНИЙ................46
2.1. Метод деления отрезка пополам.........................47
2.2. Метод касательных.....................................48
2.3. Метод простых итераций................................49
2.4. Примеры решения задач.................................50
Контрольные вопросы........................................57

ГЛАВА 3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ.........................................58
3.1. Метод матриц..........................................58
3.2. Метод итераций (последовательных приближений).........59
3.3. Примеры решения задач.................................60
Контрольные вопросы........................................64

ГЛАВА 4. ОПТИМИЗАЦИЯ ЦЕЛЕВЫХ ФУНКЦИЙ.......................65
4.1. Классификация методов оптимизации.....................65
4.2. Градиентные методы для оптимизации функции нескольких переменных......................................68
4.3. Условная оптимизация функции нескольких переменных. Метод штрафных функций.....................................72
4.4. Примеры решения задач.................................73
Контрольные вопросы........................................80

ГЛАВА 5. ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ И ИНТЕГРИРОВАНИЕ...........................................81
5.1. Методы численного дифференцирования функций...........81
5.2. Методы численного решения дифференциальных уравнений..84


3

5.3. Примеры решения задач.................................88
Контрольные вопросы........................................90

ГЛАВА 6. ИНТЕРПОЛЯЦИЯ И ЭКСТРАПОЛЯЦИЯ ФУНКЦИЙ..............91
6.1. Аппроксимация, интерполяция и экстраполяция функций...91
6.2. Методы интерполирования функций полиномом.............93
6.3. Примеры решения задач.................................94
Контрольные вопросы........................................95

ГЛАВА 7. ЧИСЛЕННОЕ РЕШЕНИЕ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ ПЕРВОГО ПОРЯДКА.................96
7.1. Метод Эйлера..........................................97
7.2. Метод Эйлера-Коши (Метод Рунге-Кутта второго порядка).98
7.3. Метод Рунге-Кутта четвертого порядка..................99
7.4. Примеры решения задач................................100
Контрольные вопросы.......................................101

ГЛАВА 8. СОСТАВЛЕНИЕ КОМПРОМИССНЫХ ЦЕЛЕВЫХ ФУНКЦИЙ...................................................102
8.1. Методы составления комплексных критериев оптимизации.102
8.2. Определение ограничений..............................104
8.3. Примеры решения задач................................109
Контрольные вопросы.......................................110

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ..........................111


4

            ПРЕДИСЛОВИЕ



     Обработка числовых данных в последние годы связана с использованием различных специализированных математических программ и систем программирования численных методов как инструмента решения прикладных задач. Широкое внедрение математических методов в самые разнообразные сферы профессиональной деятельности человека требует создания и использования инструмента математического моделирования для решения вычислительных задач. Современные численные методы в совокупности с возможностью их автоматизации при использовании персональных компьютеров превращаются в универсальный инструмент для решения вычислительных задач.
     В учебном пособии рассмотрены математические основы численных методов, применяемых для решения инженерных и научных задач, - методы приближенных вычислений, оптимизации условных и безусловных целевых функций, численного дифференцирования и интегрирования.
     Учебное пособие состоит из восьми глав. В первой главе представлены сведения об основных конструкциях языка программирования высокого уровня C++. Во второй-восьмой главах рассмотрены численные методы и алгоритмы для решения инженерных и научных задач. В каждой из этих глав имеются примеры реализации численных методов (алгоритм и программный код на языке C++).
     Учебное пособие может быть использовано студентами при подготовке к практическим работам по дисциплинам «Программирование и основы алгоритмизации», «Структуры и алгоритмы обработки данных», «Алгоритмизация инженерных и научных задач».
     Учебное пособие предназначено для студентов всех форм обучения по направлениям подготовки 15.03.04 «Автоматизация технологических процессов и производств», 15.03.06 «Мехатроника и робототехника» и 27.03.04 «Управление в технических системах».

5

            ГЛАВА 1 ОСНОВНЫЕ КОНСТРУКЦИИ ЯЗЫКА C++


        1.1. Понятие алгоритма

     Алгоритм - это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.
     ПЭВМ приходится не только считывать и выполнять определенные алгоритмы, но и хранить значительные объемы информации, к которой необходимо быстро обращаться. Эта информация в некотором смысле представляет собой абстракцию того или иного фрагмента реального мира и состоит из определенного множества данных, относящихся к какой-либо теме.
     Независимо от содержания и сложности любые данные в памяти ПЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы.
     Основной целью вычислительного процесса является исполнение алгоритма с заданными исходными данными и получение результата.
     Если выбранный для решения задачи численный метод уже реализован в стандартной библиотеке программ, то алгоритмом будет только описание и ввод данных, обращение к стандартной программе, вывод результатов на печать или экран дисплея. Однако при решении научных и инженерных задач более часты случаи, когда с помощью стандартных программ решают только какую-то часть задачи.
     Разработка схемы алгоритма в общем случае состоит в чёткой структуризации задачи, разбиении её на последовательность подзадач (шагов) и построении алгоритма для каждого шага.
     Алгоритм должен иметь следующие свойства:
     -       дискретность. Весь вычислительный процесс разбит на мелкие этапы (шаги, дискреты). Решение задачи сводится к решению простых задач, при этом каждое действие выполняется только после того, как закончится исполнение предыдущего.
     -       детерминированность (определённость), которая заключается в том, что чётко определён порядок выполнения алгоритма. Это обеспечивает однозначность результата при заданных исходных данных.
     -       результативность. Получение вполне определённого результата за определённое число шагов.
     -       конечность. При работе с численными методами строится итерационный, сходящийся к искомому решению процесс. Процесс обрывается, когда очередное приближённое решение достигает заданной точности. Таким образом, за конечное число шагов достигается решение задачи.

6

     -        массовость. С помощью выбранного алгоритма можно получать вполне определённый результат при различных исходных данных некоторого класса задач.
     -        формальность. Исполнитель, незнакомый с содержанием алгоритма, но правильно выполнивший его предписание, получает искомый результат.
     При записи алгоритма на любом этапе необходимо учитывать, что исполнителем будет компьютер, который сможет выполнять только вполне определённые действия - присваивание, ветвление, циклическое повторение, безусловный переход. В связи с этим любая детализация должна приводить к реализации таких действий.
     Используются следующие языки описания алгоритмов:
     -       словесная запись, например:
         скопировать значение X во вспомогательную переменную х; скопировать значение Y во вспомогательную переменную у; если хУс, перейти к п. 4, иначе - к п. 7;
         если х>у, перейти к п. 5, иначе - к п. 6;
         записать в х результат вычисления (x-y) и перейти к п. 3;
         записать в у результат вычисления выражения у-х и перейти к п. 3; конец. х - результат.
     -       псевдокод, например:
         НОД(Х, Y)
         пока (x#y) повторять
                если (x>y) то x: = x-y;
                иначе y: = y-x;
         конец цикла;
         вывести х;
         конец.
     -       блок-схемы.
     Наиболее распространенным является описание алгоритмов, программ, данных и систем в виде схемы из графических символов. Блок-схема - это графическое представление метода решения задачи, в котором используются символы, отображающие операции (действия) и данные.
     В блок-схеме каждому типу действий (например: ввод исходных данных, вычисление значений выражений, проверка условий и т. д.) соответствует геометрическая фигура, представленная символом действия. Символы действия соединяют линиями переходов, которые определяют очерёдность выполнения действий. Форма символов и правила составления блок-схем установлены Единой системой программной документации (ЕСПД) ГОСТ 19701-90 [5]. Наиболее часто употребляемые символы действий указанного стандарта приведены в таблице 1.

7

Таблица 1

Символы блок-схем алгоритмов

    Название     Обозначение           Пояснение       
    Процесс                       Выполнение операции  
                                  или группы операций  
Предопределенный                      Выполнение       
    процесс                      подпрограммы/функции  
    Решение                        Проверка условий    
                                Модификация команд для 
   Подготовка                    некоторой последующей 
                                 функции. Используется 
                                для циклов с параметром
                                    Начало и конец     
   Терминатор                   программы, вход и выход
                                    из подпрограммы    
                                 Ввод данных или вывод 
     Данные                         данных и печать    
                                      результатов      
    Документ                         Символ печати     
                                      результатов      
                                Указывает поток данных,
     Линия           ---           при необходимости   
                                 дополняется стрелками 
                                Применяется для обрыва 
                                линии и продолжения ее 
                                в другом месте (пример:
                                разделение блок-схемы, 
                                    не помещающейся    
  Соединитель       (^2)              на листе).       
                                    Соответствующие    
                                соединительные символы 
                                   должны иметь одно   
                                     (уникальное)      
                                      обозначение      

8

Окончание таблицы 1

  Название   Обозначение      Пояснение     
                             Применяется    
Комментарий      ---      для комментариев  
                             и пояснений    
Параллельный   _J---_    Начало параллельных
разветвитель     V V     ветвей деятельности
                         Конец параллельных 
                         ветвей деятельности

     Основные правила применения символов и выполнения блок-схем [2, 10]:
     1.      Символы в схеме должны быть расположены равномерно. Необходимо придерживаться разумной длины соединений и минимального числа длинных линий.
     2.      Символы должны быть по возможности одного размера и, предпочтительно, горизонтальной ориентации.
     3.      Внутри символа помещается минимальное количество текста, необходимое для понимания функции символа. Для записи применяется естественный язык с элементами математической символики. Если объем текста превышает размер символа, то необходимо применять символ Комментарий.
     4.      Потоки данных и потоки управления в схемах показываются линиями. Направление потока слева направо и сверху вниз считается стандартным. Если поток имеет направление, отличное от стандартного, стрелки должны указывать это направление.
     5.      Линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа.
     6.      Каждый символ имеет один вход и один выход. Исключением является символ Решение, который имеет один вход и несколько выходов. При этом каждый выход должен сопровождаться значениями условий, чтобы указать логический путь, который он представляет.
     В больших коллективах программистов при разработке сложных проектов работают со специальными программными средствами для автоматизиро


9

ванного проектирования алгоритмов и программ. Существует и свободное ПО, позволяющее упростить составление блок-схем алгоритмов (Draw.io, Dia, AFCE редактор блок-схем, Edraw MAX и др.).

        1.2. Понятие типа данных

     Для хранения информации в C++ применяются переменные. Переменная представляет собой ячейку в памяти ЭВМ, в которой хранится значение. Память представляет собой ряд ячеек, которые пронумерованы (адреса памяти).
     Компилятору программы необходимо заранее предоставить информацию о типе переменной, чтобы он мог зарезервировать для нее место.

        Базовые типы данных

     Основная цель любой программы состоит в обработке данных.
     Данные различного типа хранятся и обрабатываются по-разному. В любом алгоритмическом языке каждая константа, переменная, результат вычисления выражения или функции должны иметь определённый тип.
     Тип данных определяет:
     -  внутреннее представление данных в памяти компьютера;
     -  множество значений, которые могут принимать величины этого типа;
     -       операции и функции, которые можно применять к переменным этого типа.
     Язык программирования C++ поддерживает следующие типы данных (рис. 1):
     -       базовые типы (основные), которые представлены стандартом языка, указываются зарезервированными ключевыми словами. Базовые типы данных создают основу для построения более сложных типов;
     -       производные типы задаются пользователем, и переменные этих типов создаются как с применением базовых типов, так и типов классов. Производные типы данных бывают простые и составные (абстрактные). Абстрактный тип данных - это математическая модель данных с совокупностью операторов, определенных пользователем этой модели;
     -       типы класса применяются в объектно-ориентированном программировании, экземпляры этих типов называются объектами. Класс является частным случаем абстрактного типа данных [24, 25].


10

Рис. 1. Классификация типов данных

     Базовые типы данных содержат различные представления чисел, а также коды символов (табл. 2).


Таблица 2

Основные типы данных

Название     Обозначение  Размер Диапазон значений 
                          (байт)                   
Логический      bool        1        true/false    
Символьный      char        1       -128 до +127   
Символьный  unsigned char   1         0 до 255     
без знака                                          
Целое число      int        4    - 2 147 483 648 до
                                  + 2 147 483 647  
Целое число unsigned int    4    0 до 4 294 967 296
без знака                                          

11

Окончание таблицы 2

    Название      Обозначение Размер Диапазон значений 
                              (байт)                   
Вещественное                                           
число одинарной      float      4         ±3.4e±38     
точности                             (7 значащих цифр) 
Вещественное                                           
число двойной       double      8        ±1.7e±308     
точности                             (15 значащих цифр)
Вещественное                             ±1.2e±4932    
число увеличенной long double   10   (19 значащих цифр)
точности                                               

      Пример объявления переменной [7]:

      int x; // переменная, х целого типа
      long double y; // вещественная переменная у двойной точности
      float kontrol_sum; // вещественная переменная kontrol_sum

      Для создания псевдонима сложного названия типа данных применяют спецификатор typedef, который обозначает определение нового типа данных:
      typedef unsigned int USHORT; // создается новое имя типа данных USHORT, которое можно применять везде, где встречается переменная типа unsigned int.
      USHORT W = 5;
      USHORT K = 15;
      Тип данных void (пустой) применяется для объявления функции, которая не возвращает значения в программу. При этом оператор return в теле функции опускается.

void PrintArray(TMagazin &A, int n, int i1, int i2)
{
      printf("%19s %6s %10s %10s %9s\n", "ID", "SNasvanie", "Material", "Kolichestvo", "Cost");
      for (int i = i1; i< = i2; i++)
      printf("%19u %6s %10s %10u %9.2lf\n", A[i].ID, A[i].SNasvanie, A[i].Material, A[i].Kolichestvo, A[i].Cost);
}

        1.3. Знаки операций в C++

      В языке C/C++ применяются следующие основные операции: арифметические, логические, поразрядные и операции сравнения.
      Операции обозначаются специальными знаками (см. табл. 3-6).


12