основы алгоритмизации. Глава 1. Основы алгоритмизации. Основы алгоритмизации
 Скачать 0.65 Mb.
|
|
ГЛАВА 1. ОСНОВЫ АЛГОРИТМИЗАЦИИ Алгоритмизация является основным, базовым компонентом компьютерной грамотности в динамично развивающемся современном компьютерном мире. Для достижения положительных результатов важную роль играет умение разрабатывать оптимальный алгоритм решения поставленной задачи, что требует от исполнителя наличия определённых навыков алгоритмизации и системного анализа. А также знание математики, общей физики, механики и других инженерных дисциплин. Алгоритмизация – это общая последовательность действий, которые необходимо выполнить для построения алгоритма решения задачи, в том числе – выделение конкретных шагов алгоритмического процесса, определение вида формальной записи для каждого шага и установление определённого порядка выполнения каждого шага. Процесс подготовки решения задачи и её непосредственная реализация на компьютере происходит за некоторое количество самостоятельных этапов: 1. Постановка задачи. 2. Математическая формулировка задачи. 3. Выбор метода решений. 4. Разработка алгоритма. 5. Составление программы на алгоритмическом языке. 6. Отладка и решение задачи на ПК. 7. Анализ полученных результатов. 1.1 Постановка задачи На этом этапе на основе информационной модели (словесной постановки) задачи формируется цель решения задачи и подробно описывается её содержание. Проводится анализ характера и сущности известных и неизвестных данных, рассматривается область их существования, определяются условия, при которых задача может быть решена. Таким образом, процесс формулировки задачи сводится к постановке следующих основных вопросов: 1. Что дано? 2. Что нужно вычислить? 3. Что представляют собой неизвестные и сколько их? 4. Какие данные необходимо ввести в ПК, чтобы получить ответ? 5. Как определить решение? 6. Какие следует сделать допущения? 7. Каковы требования к точности решения? И т.д. Иногда формулировка задачи допускает неточности и много толкований. В этом случае нужно сделать условия более точными, чтобы четко изложить, что должен сделать алгоритм. При постановке задачи определяются не только характеристики заданных величин, их свойства и отношения между ними, но и требования к решению задачи. От правильности постановки задачи зависит успех ее решения. 1.2 Математическая формулировка задачи Задача, предназначенная для решения на персональном компьютере (ПК), должна быть задана в математической формулировке, т.е. выражена в терминах понятий, формально определённых в математике, имеющих точно определённые свойства и находящихся между собой в строго определённых отношениях. Условие задачи записывается либо в виде уравнений, либо в виде последовательности формул или логических соотношений, необходимых для решения задачи. На этом этапе могут добавляться некоторые дополнительные по сравнению с постановкой задачи условия, выделяющие единственное решение. Основным компонентом этого этапа является построение математической модели. Построением модели называется формализация описания задачи с использованием математических, логических и других методов, при которых существующие соотношения между величинами, определяющие результат, выражаются с использованием математических формул и логических соотношений. Выбор модели существенно влияет на остальные этапы процесса решения. В зависимости от содержания задачи построение её модели может быть областью исследования различных дисциплин (например: методы оптимизации, численный анализ и др.). При построении модели в первую очередь следует рассмотреть следующие вопросы. 1. Существует ли опыт решения аналогичных задач? 2. Какие известные математические и другие методы формализации подходят для решения поставленной задачи? Затем следует рассмотреть математическое описание того, что мы знаем и что нужно найти. На выбор модели влияют такие факторы, как простота и однозначность вычислений, удобство представления и уровень знаний. При этом следует определить следующее. 1. Вся ли информация, необходимая для решения задачи, полностью описана математически? 2. Существует ли математическая величина, соотносимая с результатом? 3. Все ли соотношения между характеристиками модели описаны? Метод решения задачи следует из принятой модели. 1.3 Выбор метода решений Выбрать метод решения задачи значит преобразовать математическую формулировку задачи, включающую символы математического анализа (например:∑, max, min, 𝑑𝑥 𝑑 , ∫…, dx и т.д.) в последовательность действий и логических связей между ними. Если одна и та же задача может быть решена с помощью различных методов, выбирают тот, который наилучшим образом удовлетворяет её требованиям. При этом учитывается точность решения, быстрота получения результата, объём памяти для сохранения исходных и промежуточных данных, результатов и сложность программой реализации. Существует два типа методов: точные и численные. Сущность точных методов состоит в последовательности выполнения арифметических и логических действий, позволяющих получить точное решение. Например: вычисление корня квадратного уравнения. Однако для большинства задач, встречающихся в инженерной практике, точные методы неизвестны. Для решения таких задач используются численные методы, которые обеспечивают отыскание приближенного значения с требуемой точностью. В некоторых случаях пригодность (или непригодность) избранного метода может выявиться только на последующих этапах. Тогда нужно возвратиться к этапу выбора метода. 1.4 Разработка алгоритма Понятие алгоритма относится к числу основных понятий современной вычислительной математики и информатики. Если задача содержит вычисления, то алгоритм – это последовательность указаний, содержащих расчётные формулы и сведения о том, как ими пользоваться. По мере развития параллельности в работе компьютеров слово последовательность стали заменять более общим словом порядок. Единого общепринятого определения алгоритм нет. Разные авторы, в том числе Д.Э. Кнут, А. Колмогоров и др., дают различные толкования. Нет определения алгоритма и в ГОСТ 19781–90. Проанализировав все известные определения можно сказать, что в общем случае алгоритм – это система формальных правил, определяющая порядок действий и приводящая к решению поставленной задачи. И если различные исполнители будут действовать в соответствии с этой системой правил, то все они будут получать одинаковые результаты, т.е. Алгоритмом решения задачи называется путь решения задачи (определенный порядок действий), который необходимо выполнить для достижения результата. Основной целью вычислительного процесса является исполнение алгоритма с заданными исходными данными и получение результата. Если выбранный для задачи численный метод уже реализован в стандартной библиотеке программ, то алгоритмом будет описание и ввод данных, обращение к стандартной программе, вывод результатов на печать или экран дисплея. В инженерной практике более часты случаи, когда стандартные программы решают лишь какую-то часть задачи. Разработка схемы алгоритма в общем случае состоит в чёткой структуризации задачи, разбиении её на последовательность подзадач (шагов) и построении алгоритма для каждого шага. Алгоритм должен обладать следующими свойствами. Дискретность. Весь вычислительный процесс разбит на мелкие этапы (шаги, дискреты). И решение задачи сводится к решению простых задач, при этом каждое действие выполняется только после того, как закончится исполнение предыдущего. Детерминированность (определённость), которая заключается в том, что чётко определён порядок выполнения алгоритма. Это обеспечивает однозначность результата при заданных исходных данных. Результативность. Получение вполне определённого результата за определённое число шагов. Конечность. При работе с численными методами строится бесконечный, сходящийся к искомому решению процесс. Процесс обрывается, когда очередное приближённое решение достигает заданной точности. Таким образом, за конечное число шагов получается решение задачи. Массовость. С помощью выбранного алгоритма можно получать вполне определённый результат при различных исходных данных для некоторого класса задач. Формальность. Исполнитель, незнакомый с содержанием алгоритма, но правильно выполнивший его предписание, получает искомый результат. Современные методы программирования, основанные на структурном подходе, предусматривают использование различных специальных приёмов. Например, пошаговая детализация до команд решателя. На первом этапе разработки алгоритм рассматривается как некоторая совокупность действий для обработки исходной информации, а все последующие этапы – это уточнение (выявление) всё более частных особенностей. При записи алгоритма на любом этапе нужно учитывать, что исполнителем будет компьютер, который сможет выполнять только вполне определённые действия – присваивание, ветвление, циклическое повторение, безусловный переход. Поэтому любая детализация должна приводить к реализации таких конструкций. При этом следует обратить внимание на исполнение алгоритма. Пошаговое выполнение последовательности операторов позволит получить результат. В итоге процесс разработки алгоритма должен быть направлен на получение четкой структуры алгоритмических конструкций. 1.5 Способы описания алгоритмов Для строгого задания различных структур данных и алгоритмов их обработки нужно иметь такую систему формальных обозначений и правил их использования, чтобы всякое действие трактовалось точно и однозначно. Соответствующие системы правил называют языками описаний. В настоящее время используются следующие языки описания: словесная запись; псевдокод; схемы. В больших коллективах программистов при разработке сложных проектов работают со специальными программными средствами для автоматизированного проектирования алгоритмов и программ. 1.5.1 Словесная запись алгоритма Способ основан на использовании общепринятых средств общения между людьми и содержит набор фраз, который не допускает лишних слов, повторений и неоднозначностей. Действия, предусмотренные алгоритмом, нумеруются, что даёт возможность на них ссылаться. Допускается использование математической символики. Задача 1. Записать алгоритм нахождения наибольшего делителя двух натуральных чисел (X и Y). Решение. 1. Сравнить данные числа (X равно Y, X меньше, больше Y) и перейти к следующему пункту. 2. Если числа равны, то необходимо взять любое из них в качестве ответа и перейти к пункту 6. 3. Если числа не равны, то перейти к следующему пункту. 4. Определить большее из чисел. 5. Заменить большее число разностью большего и меньшего чисел. Перейти к началу к пункту 1. 6. Конец алгоритма. Описанный алгоритм применим к любым числам и должен приводить к решению поставленной задачи. Задача 2. Заданы координаты двух точек. Координаты 1-й точки – X1, Y1, координаты 2-й точки – X2, Y2. Определить, какая из точек наиболее удалена от начала координат. Решение. 1. Вычисляем расстояние 1-й точки до начала координат: 𝑅1 = √𝑋1 2 + 𝑌1 2 2. Вычисляем расстояние 2-й точки до начала координат: 𝑅2 = √𝑋2 2 + 𝑌2 2 3. Определяем большее из расстояний. Если R1 больше R2, то переход к следующему пункту, если R1 меньше, то переход к пункту 5. 4. Печать сообщения «Первая точка лежит ближе к началу координат». Переход к пункту 6. 5. Печать сообщения «Вторая точка лежит ближе к началу координат». 6. Конец алгоритма. Действия (пункты) алгоритма выполняются в естественной последовательности. Вид действий не формализован. Такой вид записи алгоритма имеет серьёзный недостаток – отсутствие наглядности. Поэтому этот способ записи алгоритма не имеет широкого распространения. 1.5.2 Псевдокод Псевдокод – это язык записи структурированных алгоритмов. Псевдокод основан на формализованном представлении предписаний, задаваемых с помощью ограниченного набора типовых синтаксических конструкций. Набор конструкций состоит из смеси алгоритмического языка высокого уровня и фраз родного языка исполнителя. Как правило, стандартов на псевдокод не существует. Псевдокод используется для облегчения разработки программ. Так же, как и программа, псевдокод имеет все достоинства структурированной записи, поэтому алгоритм, написанный на псевдокоде, достаточно легко преобразовать в программный код. Пример псевдокода для нахождения наибольшего элемента из двух натуральных чисел (А и В). Обозначим наибольший элемент – Z. Решение. Начало Ввод А, В Если А≥В, то Z=A Иначе Z=B Конец Если Вывод Z Конец Основными достоинствами псевдокода являются: близость к языкам программирования; возможность разобраться в самом длинном и сложном алгоритме, поэтому псевдокод используется чаще всего для документирования программ. 1.5.3 Схемы алгоритмов Наиболее распространенным является описание алгоритма в виде схемы из графических символов. Схема алгоритма – это графическое представление метода решения задачи, в котором используются символы, отображающие операции (действия) и данные. В схеме алгоритма каждому типу действий (например: ввод исходных данных, вычисление значений выражений, проверка условий и т.д.) соответствует геометрическая фигура, представленная символом действия. Символы действия соединяют линиями переходов, которые определяют очерёдность выполнения действий. Форма символов и правила составления схем установлены Единой Системой Программной Документации (ЕСПД) ГОСТ 19701-90. Наиболее часто употребляемые символы действий указанного стандарта приведены в таблице. Применение символов Название символа Обозначение Пояснение Процесс Выполнение определенной операции или группы операций. Предопределенный процесс Вычисления по подпрограмме, стандартной подпрограмме. Решение Проверка условий. Граница цикла Символ состоит из двух частей и отображает начало и конец цикла. Обе части имеют один и тот же идентификатор. Подготовка Модификация команды или группы команд на некоторую последующую функцию. Например, модификация параметров цикла. Используется для циклов с параметром. Терминатор Начало и конец программы, вход и выход из подпрограммы. Данные Символ отображает ввод данных, носитель которых не определен. Документ Символ отображает данные, представленные на носителе в удобочитаемой форме. Используется как символ печати результатов. Линия __________ Символ отображает поток данных или управления. При необходимости могут быть добавлены стрелки-указатели. Соединитель Символ отображает выход в часть схемы и вход из другой части схемы. Используется для обрыва линии и продолжения её в другом месте. Комментарий Используется для добавления описательных комментариев или пояснительных записей в целях объяснений примечаний. Пунктирная линия связана с соответствующим символом или может обводить группы символов. Текст помещается около ограничивающей фигуры. Символы Данные и Документ используются для обозначения операций ввода- вывода. Символ Процесс применяется для обозначения выполнения одной или группы операций, приводящих к изменению значения, формы или размещения информации. Представление операций достаточно свободно. Например, для обозначения вычислений можно использовать математические выражения или текст. Символ Решение используется для обозначения переходов управления по условию. Имеет один вход и ряд выходов, при этом только один из них может быть активизирован после вычисления условий, определённых внутри этого символа. Результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути. Символ Граница цикла используется для организации циклических вычислительных процессов. Параметр цикла записывается в обеих частях символа. Начальное значение, граничное условие и правило изменения параметра цикла указывается в начале или в конце в зависимости от расположения операции, проверяющей условие. Символ Подготовка используется, как правило, для организации цикла с параметром. Внутри символа записывается параметр цикла, указывается его начальное значение, граничное условие и правила изменения значения параметра. Символ размещается в начале циклической конструкции. Линии переходов используются для обозначения порядка выполнения действий. Соединители используются в том случае, когда схема алгоритма разделяется на автономные части, особенно если она не умещается на одном месте, или когда необходимо избежать излишних пересечений линий переходов. Комментарий позволяет включать в схемы алгоритмов пояснения к функциональным блокам. Частое использование комментариев нежелательно, так как это усложняет схему, делает её менее наглядной. Алгоритм начинается и заканчивается символами Начало и Конец. Основные правила применения символов и выполнения схем алгоритмов: 1. Символы в схеме должны быть расположены равномерно. Нужно придерживаться разумной длины соединений и минимального числа длинных линий. 2. Символы должны быть по возможности одного размера и, предпочтительно, горизонтальной ориентации. 3. Внутри символа помещается минимальное количество текста, необходимое для понимания функции символа. Для записи используется естественный язык с элементами математической символики. Если объем текста превышает размер символа, то нужно использовать символ Комментарий. 4. Потоки данных и потоки управления в схемах показываются линиями. Направление потока слева направо и сверху вниз считается стандартным. Если поток имеет направление, отличное от стандартного, стрелки должны указывать это направление. 5. Линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа. 6. Каждый символ имеет один вход и один выход. Исключением является символ Решение, который имеет один вход и несколько выходов. При этом каждый выход должен сопровождаться значениями условий, чтобы указать логический путь, который он представляет. Схема алгоритма является самым наглядным способом представления алгоритма, при этом нет никаких ограничений на степень детализации. 1.5.4 Реализация алгоритмов После разработки алгоритма встает задача его реализации в виде программы, которую можно выполнить на вычислительной машине (компьютере). В ГОСТ 19781–90 дано следующее определение программы. Программа – это данные, предназначенные для управления конкретными компонентами обработки информации в целях реализации определенного алгоритма. Для написания программы необходимо в первую очередь выбрать язык программирования (алгоритмический язык). В общем случае алгоритмический язык – это набор символов с заданными правилами образования из этих символов конструкций, с помощью которых описывается процесс выполнения алгоритма. В ГОСТ 19781–90 дано следующее определение алгоритмического языка. Алгоритмический язык – искусственный язык, предназначенный для выражения алгоритмов. Основная цель любого алгоритмического языка – дать пользователю удобные средства для реализации алгоритмов. Выбор языка определяется: типом решаемой задачи; предпочтениями и привычками пользователя; требуемыми затратами времени на разработку; операционной системой и доступными средами программирования. Например, для программирования сложных задач выбирают язык Ассемблер или С++, а для решения инженерных задач предпочтение отдают Fortran (Visual Fortran), Basic (Visual Basic) или Pascal (Delphi или Lazarus). Во вторую очередь необходимо перевести исходную программу, написанную на алгоритмическом языке, в исполняемую программу для вычислительной машины (процессора) или промежуточной исполняемой среды. Этапы подготовки исполняемой программы. 1. Трансляция (компиляция) – это преобразование (перевод) исходного текста программы в объектный модуль, представляющий из себя набор машинных инструкций (команд) без стандартных программ функций (программ вычисления синуса, логарифма и т.д.), модулей ввода исходных данных и вывода результатов или активных элементов управления, представляющих элементы современных операционных систем. При этом выполняется проверка правильности синтаксиса исходной программы. Если в программе будут обнаружены ошибки, то обработка программы прекращается. Если ошибок нет, то программа передается на следующий этап. Трансляция выполняется специальной программой (Транслятор, Компилятор), которая может входить в среду программирования. 2. Компоновка (или редактирование связей) – это сборка объектного модуля программы, модулей ввода-вывода и компонентов стандартной библиотеки объектных модулей в один модуль, который называется выполняемым файлом или загрузочным модулем. 3. Выполнение файла загрузочного или исполняемого модуля. На этом этапе получаем решение поставленной задачи. При этом возможно прерывание решения (аварийный останов, например, деление на ноль), зацикливание или неправильные результаты. Это возможно по следующим причинам. Ошибки в исходных данных. Во избежание этой ошибки рекомендуется проверять исходные данные путем их вывода, печати или любым другим способом. Ошибки в алгоритме – в этом случае необходимо вернутся к начальным этапам разработки алгоритма. Для выявления этих ошибок рекомендуется выполнить тестирование алгоритма. Схема этапов подготовки программы представлена ниже. 1.5.5 Тестирование алгоритмов Это важный этап при решении алгоритмических задач. На этом этапе выявляются ошибки реализации алгоритма. В общем случае отсутствуют универсальные правила проведения тестирования. При решении физических и инженерных задач общее правило тестирования заключается в необходимости знания или результатов решения задачи для одного или нескольких наборов данных или оценки достоверности полученных результатов любыми доступными математическими или экспертными методами. Это дает предварительную оценку правильности работы программы. Для более детального анализа правильности алгоритма и программы необходимо при отладке программы предусмотреть вывод этапов прохождения алгоритма, промежуточных переменных и переменных цикла. 1.6 Величины в алгоритмах Современные компьютеры могут получать, накапливать и хранить большие объемы информации, содержащие формализованные сведения о реальном мире. И при постановке задачи пользователь сознательно или невольно должен выбрать некоторое абстрактное представление предмета рассмотрения, т.е. определить множество данных, отражающих реальную ситуацию и зафиксировать их. Применение компьютера для хранения и обработки данных приводит к разделению данных и их смыслового содержания. Компьютер имеет дело с данными как таковыми, а интерпретирующая информация в явной форме не фиксируется. В алгоритмах для данных используются специальные символические обозначения, которые аналогичны обозначениям в математике, представляют имена величин или их идентификаторы и при выполнении алгоритма заменяются конкретными для данной задачи числовыми значениями. В зависимости от вида задачи используются данные разных типов. Типы данных: целые, вещественные, логические, текстовые (символьные) и другие. Мы определили только те типы, которые будут использоваться в этом учебном пособии. В алгоритмах и программах используются два вида величин: константы и переменные. Константа – это величина, значение которой не изменяется в процессе выполнения алгоритма и программы. Переменная – это величина, значение которой изменяется в процессе выполнения алгоритма и программы. Используются простые и индексные переменные (переменные с индексом). Переменная с индексом – это элемент некоторой заданной последовательности значений, которые называются массивом. Массив состоит из компонентов одного типа, поэтому структура массива однородна. Индекс или порядковый номер элемента имеет значение целого типа. С помощью индекса можно выделить любой элемент в массиве. Имена массивов выбираются по тому же правилу, что и имена простых переменных. При этом следует учесть, что имя массива не должно совпадать с именем ни одной простой переменной, используемой в этом же алгоритме. Массивом называется совокупность однотипных данных, связанных общим именем. Массив может быть одномерным (вектор), количество индексов – один; двумерным, количество индексов – два и т.д (матрицы). Количество индексов определяет размерность массива. Первый компонент одномерного массива – это элемент с номером 1, второй – элемент с номером 2 и т.д., запись в математике – X1, X2, … При программировании запись более формализована: X(1), X(2), … (в некоторых языках программирования допускается использование нулевых и отрицательных индексов). Двумерный массив – это матрица из горизонтальных строк и вертикальных столбцов. Первый из индексов определяет номер строки, второй – номер столбца. Номер строки изменяется от 1 до N, где N – полное число строк, номер столбца от 1 до M, где М – полное число столбцов. При программировании элементы двумерного массива по имени Y будут записаны Y(1,1), Y(1,2), Y(1,3) и т.д. Индексы отделяются запятыми. При работе с элементами массивов необходимо задать соответствующие значения индекса (для одномерного массива) или индексов (для двумерного массива). Текущие значения индексов не должны выходить за пределы заданного диапазона, иначе переменная с индексами не может быть определена. Основными характеристиками массива являются: имя массива; тип элементов массива; размерность, равная количеству индексов (измерений) массива; значения верхней и нижней границы для каждого индекса; размер (длина) массива – количество компонентов. Вопросы для самопроверки 1. Назовите основную цель вычислительного процесса. 2. При подготовке задачи к решению, какой этап реализуется раньше: Выбор метода решения или Разработка алгоритма? 3. На каком этапе подготовки задачи к решению определяются требования к точности решения? 4. Назовите методы решения задач. Что между ними общего и в чём отличия? 5. Если задача может быть решена с помощью различных методов, то какой метод следует выбрать? 6. Назовите свойства алгоритмов. 7. Назовите способы записи алгоритма. 8. На чём основана словесная запись алгоритма? В чём недостаток этого способа? 9. На чём основан псевдокод? 10. Назовите наиболее распространенный способ описания алгоритма. 11. Назовите символы, без которых схема алгоритма невозможна. 12. Какой символ используется для проверки условия? 13. Сколько символов Решения будет в схеме вычисления выражения) 𝑍 = 𝑚𝑖𝑛(𝐴, 𝐵) + 𝑚𝑎𝑥(𝐶, 𝐷) ? 14. Сколько символов Процесс будет в схеме вычисления выражения, приведенного выше? 15. Как называется величина, значение которой не изменяется в процессе выполнения алгоритма и программы? 16. Что такое массив? 17. В чём отличие между простыми переменными и переменными с индексами? 18. Этапы подготовки исполняемой программы. |