Основные типы алгоритмических структур
Основы алгоритмизации и объектно-ориентированного программирования
Алгоритм и его формальное исполнение
Алгоритм и его свойства. Алгоритмы могут описывать процессы преобразования самых разных объектов. Широкое распространение получили вычислительные алгоритмы, которые описывают преобразование числовых данных. Само слово «алгоритм» происходит от algorithmi — латинской формы написания имени выдающегося математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических операций.
Выберем в качестве объекта текст и построим алгоритм, описывающий процесс его редактирования.
Для того чтобы изменить состояние объекта (значения его свойств), необходимо выполнить над ним определенную последовательность действий (операций). Выполняющий такие операции объект называется исполнителем. Исполнителем редактирования текста может быть человек, компьютер и др.
Алгоритмы состоят из отдельных команд, которые исполнитель выполняет одну за другой в определенной последовательности. Разделение информационного процесса в алгоритме на отдельные команды является важным свойством алгоритма и называется дискретностью.
Процесс преобразования текста необходимо разбить на отдельные операции, которые должны быть записаны в виде отдельных команд исполнителю.
Каждый исполнитель обладает определенным набором, системой команд, которые он может выполнить. Алгоритм должен быть понятен исполнителю, то есть должен содержать только те команды, которые входят в систему его команд.
|
|
|
В процессе редактирования текста возможны различные операции: удаление, копирование, перемещение или замена его фрагментов. Исполнитель редактирования текста должен быть в состоянии выполнить эти операции.
Запись алгоритма должна быть такова, чтобы, выполнив очередную команду, исполнитель точно знал, какую команду необходимо исполнять следующей. Это свойство алгоритма называется детерминированностью.
Должны быть определены начальное состояние объекта и его конечное состояние (цель преобразования). Алгоритм должен обеспечивать преобразование объекта из начального состояния в конечное за конечное число шагов. Такое свойство алгоритма называется результативностью.
Следовательно, для текста необходимо задать начальную последовательность символов и конечную последовательность, которая должна быть получена после редактирования.
Формальное выполнение алгоритма. Алгоритм позволяет формализовать выполнение информационного процесса. Если исполнителем является человек, то он может выполнять алгоритм формально, не вникая в содержание поставленной задачи, а только строго выполняя последовательность действий, предусмотренную алгоритмом.
|
|
|
Каждая команда алгоритма должна однозначно определять действие исполнителя, для этого необходимо формализовать запись алгоритма и заменить содержательную модель текста на его формальную модель. Формальная модель представляет текст делящимся на страницы, состоящие из определенного количество строк, которые, в свою очередь, включают определенное количество знакомест (символов).
Компьютер — автоматический исполнитель алгоритмов.
Представление информационного процесса в форме алгоритма позволяет поручить его автоматическое исполнение различным техническим устройствам, среди которых особое место занимает компьютер. При этом говорят, что компьютер исполняет программу (последовательность команд), реализующую алгоритм.
Развитие языков программирования. Информацию в компьютере обрабатывает процессор, следовательно, алгоритм должен быть записан на языке, «понятном» для процессора, то есть на машинном языке, представляющем собой логические последовательности нулей и единиц.
На заре компьютерной эры, в 50-е годы XX века, программы писались на машинном языке и представляли собой очень длинные последовательности нулей и единиц. Составление и отладка таких программ было чрезвычайно трудоемким делом.
|
|
|
В 60-70-е годы для облегчения труда программистов начали создаваться языки программирования высокого уровня, формальные языки, кодирующие алгоритмы в привычном для человека виде (в виде предложений). Такие языки программирования строились на основе использования определенного алфавита и строгих правил построения предложений (синтаксиса).
Наиболее широко распространенным типом языков программирования высокого уровня являются процедурные языки. В таких языках широко используются управляющие конструкции (операторы), которые позволяют закодировать различные алгоритмические структуры (линейную, ветвление, цикл).
Одним из первых процедурных языков программирования был известный всем Бейсик (Basic), созданный в 1964 году. В течение последующего времени Бейсик развивался, появлялись его различные версии (MSX-Basic, Бейсик-Агат, QBasic и др.). Другим широко распространенным языком программирования алгоритмического типа является Pascal.
В настоящее время наибольшей популярностью пользуются системы объектно-ориентированного визуального программирования Microsoft Visual Basic и Borland Delphi. Для создания приложений в среде Windows&Office используется язык программирования Visual Basic for Applications (VBA).
|
|
|
Основные типы алгоритмических структур
Линейный алгоритм
Существует большое количество алгоритмов (например, рассмотренный выше алгоритм «Редактирование»), в которых команды должны быть выполнены последовательно одна за другой. Такие последовательности команд будем называть сериями, а алгоритмы, состоящие из таких серий, линейными.
Для того чтобы сделать алгоритм более наглядным, часто используют блок-схемы.
Различные элементы алгоритма изображаются с помощью различных геометрических фигур: для обозначения начала и конца алгоритма используются прямоугольники с закругленными углами, а для обозначения последовательности команд — прямоугольники (рис. 4.2).
На блок-схеме хорошо видна структура линейного алгоритма, по которой исполнителю (человеку) удобно отслеживать процесс его выполнения.
4.2.2. Алгоритмическая структура «ветвление»
В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в алгоритмическую структуру «ветвление» входит условие, в зависимости от выполнения или невыполнения которого реализуется та или иная последовательность команд (серия).
Будем называть условием высказывание, которое может быть либо истинным, либо ложным. Условие, записанное на формальном языке, называется условным или логическим выражением.
Условные выражения могут быть простыми и сложными. Простое условие включает в себя два числа, две переменных или два арифметических выражения, которые сравниваются между собой с использованием операций сравнения (равно, больше, меньше и пр.). Например: 5>3, 2*8=4*4 и т. д.
Сложное условие — это последовательность простых условий, объединенных между собой знаками логических операций. Например, 5>3 And 2*8=4*4.
Алгоритмическая структура «ветвление» может быть зафиксирована различными способами: графически, с помощью блок-схемы;
• на языке программирования, например на языках Visual Basic и VBA с использованием специальной инструкции ветвления (оператора условного перехода). После первого ключевого слова (if) должно быть размещено условие. После второго ключевого слова ( Then ) последовательность команд (серия 1), которая должна выполняться, если условие принимает значение «истина». После третьего ключевого слова ( Else ) размещается последовательность команд (серия 2), которая должна выполняться, если условие принимает значение «ложь» (рис. 4.3).
Оператор условного перехода может быть записан в мно гострочной форте или в однострочной форме.
В многострочной форме он записывается с помощью инструкции If ... Then . . . Else . . . End If (Если ... To ... Иначе ... Конец Если). В этом случае ключевое слово Then размещается на той же строчке, что и условие, а последовательность команд (серия 1) — на следующей. Третье ключевое слово Else размещается на третьей строчке, а последовательность команд (серия 2) — на четвертой. Конец инструкции ветвления End If размещается на пятой строчке.
В однострочной форме он записывается с помощью инструкции If ... Then . . . Else . . . (Если ... То ... Иначе ...). Если инструкция не помещается на одной строке, она может быть разбита на несколько строк. Такое представление инструкций более наглядно для человека. Компьютер же должен знать, что разбитая на строки инструкция представляет единое целое. Это обеспечивает знак «переноса», который задается символом подчеркивания после пробела « _».
Третье ключевое слово Else в сокращенной форме инструкции может отсутствовать. (Необязательные части оператора записываются в квадратных скобках — см. табл. 4.3.) Тогда, в случае если условие ложно, выполнение оператора условного перехода заканчивается и выполняется следующая строка программы.
4.2.3. Алгоритмическая структура «выбор»
Алгоритмическая структура «выбор» применяется для реализации ветвления со многими вариантами серий команд. В структуру выбора входят несколько условий, проверка которых осуществляется в строгой последовательности их записи в команде выбора. При истинности одного из условий выполняется соответствующая последовательность команд.
На языках программирования Visual Basic и VBA инструкция выбора начинается с ключевых слов Select Case, после которых записывается выражение (переменная, арифметическое выражение и так далее). После ключевых слов Case заданное выражение сравнивается с определенными значениями — записываются условия, при истинности одного из которых начинает выполняться серия команд. Заканчивается инструкция ключевыми словами End Select (рис. 4.4).
4.2.4. Алгоритмическая структура «цикл»
В алгоритмическую структуру «цикл» входит серия команд, выполняемая многократно. Такая последовательность команд называется телом цикла.
Циклические алгоритмические структуры бывают двух типов:
• циклы со счетчиком, в которых тело цикла выполняется
определенное количество раз;
• циклы с условием, в которых тело цикла выполняется,
пока условие истинно.
Алгоритмическая структура «цикл» может оыть зафиксирована различными способами:
• графически — с помощью блок-схемы;
• на языке программирования, например на языках Visual
Basic и VBA с использованием специальных инструкций,
реализующих циклы различного типа.
Цикл со счетчиком. Когда заранее известно, какое число повторений тела цикла необходимо выполнить, можно воспользоваться циклической инструкцией (оператором цикла со счетчиком) Рог . . . Next (рис. 4.5).
Синтаксис оператора For . . . Next следующий: строка, начинающаяся с ключевого слова Рог, является заголовком цикла, а строка с ключевым словом Next — концом цикла, между ними располагаются операторы, являющиеся телом цикла.
В начале выполнения цикла значение переменной Счетчик устанавливается равным НачЗнач. При каждом проходе цикла переменная Счетчик увеличивается на величину шага. Если она достигает величины, большей КонЗнач, то цикл завершается и выполняются следующие за ним операторы.
Циклы с условием. Часто бывает так, что необходимо повторить тело цикла, но заранее неизвестно, какое количество раз это надо сделать. В таких случаях количество повторений зависит от некоторого условия. Такой цикл реализуется с помощью инструкции Do ... Loop .
Условие выхода из цикла можно поставить в начале, перед телом цикла. Такой цикл называется циклом с предусловием (рис. 4.6).
Проверка условия выхода из цикла проводится с помощью ключевых слов While или Until . Эти слова придают одному и тому же условию противоположный смысл. Ключевое слово While обеспечивает выполнение цикла, пока выполняется условие, то есть пока условие имеет значение «истина». Как только условие примет значение «ложь», выполнение цикла закончится. В этом случае условие является условием продолжения цикла.
Ключевое слово Until обеспечивает выполнение цикла, пока не выполняется условие, то есть пока условие имеет значение «ложь». Как только условие примет значение «истина», выполнение цикла закончится. В этом случае условие является условием завершения цикла.
Условие выхода из цикла можно поставить в конце, после тела цикла. Такой цикл называется циклом с постусловием. Этот цикл реализуется также с помощью инструкции Do . . . Loop (рис. 4.7).
Проверка условия выхода из цикла проводится с помощью ключевых слов While или Until.
Цикл с постусловием, в отличие от цикла с предусловием, выполняется обязательно как минимум один раз, независимо от того, выполняется условие или нет.
Дата добавления: 2020-12-12; просмотров: 217; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!