Основные структуры алгоритмов — это ограниченный набор стандартных способов соединения отдельных блоков или структур для выполнения типичных последовательностей действий.
Приводимые ниже структуры рекомендуются при использовании так называемого структурного подхода к разработке алгоритмов и программ. Структурный подход предполагает использование только нескольких основных структур, комбинация которых дает все многообразие алгоритмов и программ.
К основным структурам относятся (см. рис. 6.2.): следование а, две разновидности цикла б, в, три разновидности разветвления г, д, е. Отметим вначале особенности трех основных типов структур.
Следование —это последовательное размещение блоков и групп блоков, такая структура называется также линейной.
Если некоторая часть программы (на схеме группа блоков) выполняется многократно и после проверки некоторого условия в какой-то момент осуществляется выход из нее, то такую часть называют циклом.
Если после проверки некоторого условия выбирается один из двух (или более) путей вычислительного процесса и после выполнения любого из них вычислительный процесс опять сводится в одно русло, то возникает разветвление.
Сложность алгоритмов и методы оптимизации программ
Теперь рассмотрим особенности каждого вида цикла и разветвления.
Цикл До применяется при необходимости выполнить какие-либо вычисления нескольких раз до выполнения некоторого условия (блок 3). Особенность этого цикла в том, что он всегда выполняется хотя бы один раз, так как первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено. Тело цикла (блок 2)—та последовательность действий, которая выполняется многократно (в цикле). Начальные присвоения (блок 1) задание начальных значений тем переменным, которые используются в теле цикла. Цикл такого типа называют также итеративным циклом в том случае, когда количество повторений неизвестно до начала выполнения цикла.
Цикл Пока отличается от цикла До тем, что проверка условия (блок 3) производится до выполнения тела цикла (блок 2), и, если при первой проверке условие выхода из цикла выполняется, то тело цикла не выполняется ни разу. Цикл такого типа называется также циклом по условию.
Замечание. В некоторых случаях проверка условия осуществляется внутри тела цикла, т.е. тело цикла разбивается на две последовательности операторов: одна выполняется до проверки условия, вторая — после.
Существует еще одна важная разновидность цикла: цикл по счетчику. Для него существует специальное обозначение и специальный оператор в различных алгоритмических языках программирования (оператор цикла). Для организации цикла по счетчику используется управляющая переменная цикла, изменяющаяся в заданных пределах с постоянным шагом. Разветвление применяется, когда в зависимости от условия нужно выполнить либо одно, либо другое действие. Действие 1 (блок 1) или действие 2 (блок 2) могут, в свою очередь, представлять собой одну из типовых структур.
Обход — частный случай разветвления, когда одна ветвь не содержит никаких действий. Множественный выбор является обобщением разветвления, когда в зависимости от значения переменной (i) выполняется одно из нескольких действий. При i = 1 выполняется действие S1, при i = 2 — действие S2 и т. д.
Миронов А.М.-Методы ИИ в задачах анализа данных — Лекция 1. Верификация алгоритмов вычисления суммы
Особенностью всех приведенных структур является то, что они имеют один вход и один выход и их можно соединить друг с другом в любой последовательности. Каждая структура может также содержать в качестве одного из блоков любую другую структуру.
Обычно при составлении схемы блоки размещаются друг под другом в порядке их выполнения. Возврат назад осуществляется только на циклах. Это дает простую и наглядную структуру алгоритма, по которой далее легко составлять программу.
Если для разработки алгоритма используется метод пошаговой детализации, то первоначально продумывается и фиксируется общая структура алгоритма без детальной проработки отдельных его частей, но при этом используются, лишь основные структуры алгоритмов. Блоки, требующие дальнейшей детализации, обозначаются пунктирной линией. Далее прорабатываются (детализируются) отдельные блоки, не детализированные на предыдущем шаге, т.е. на каждом шаге разработки уточняется реализация фрагмента алгоритма (или программы), и, таким образом, на каждом шаге мы имеем дело с более простой задачей. Полностью закончив детализацию всех блоков, мы получим решение всей задачи в целом. Описанный метод пошаговой детализации называется также программированием сверку вниз.
В некоторых случаях, стремление, во что бы то ни стало, остаться в рамках структурного подхода приводит к необоснованному усложнению программы и потере ее наглядности и естественности. Если учесть, что структурное программирование имеет целью не подчинить программы каким-то правилам, а сделать их более удобными для восприятия, то в ряде случаев оказывается целесообразным отдать предпочтение ясности и естественности программы.
Если разработка алгоритма выполнена хорошо, то программирование принципиальных трудностей не вызывает.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник: studopedia.ru
Циклический вычислительный процесс
Если некоторая часть программы (на схеме группа блоков) вычисляется многократно и после проверки некоторого условия в какой-то момент осуществляется выход из нее, то такую часть называют циклом.
Цикл “До” применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнения некоторого условия (см. рисунок 3.5,а). Особенность этого цикла в том, что он всегда выполняется хотя бы один раз, так как первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено.
Цикл “Пока” (см. рисунок 3.5, б) отличается от цикла “До” тем, что проверка условия производится до выполнения тела цикла, и, если при первой проверке условие выхода из цикла выполняется, то тело цикла не выполняется ни разу.
а) Цикл “До” б) Цикл “Пока”
Рисунок 3.5 – Структура циклов
Существует еще одна важная разновидность цикла – цикл по счетчику. Для него имеется специальное обозначение и специальный оператор (оператор цикла). Для организации цикла по счетчику используется управляющая переменная цикла, изменяющаяся в заданных пределах с постоянным шагом.
Для изображения этого цикла на блок-схемах обычно используется структура “а” (цикл “До”), по которой работают операторы цикла на алгоритмических языках Фортран, Бейсик и пр. Однако при составлении блок-схем следует помнить, что, если может возникнуть ситуация, когда условие выхода из цикла выполняется уже в начале первого цикла, то на алгоритмических языках таких, как Паскаль, Delphi, цикл не будет выполняться ни разу, поскольку операторы цикла в данном случае работают по алгоритму “б” (цикл “Пока”).
Составим в качестве примера алгоритм вычисления суммы элементов одномерного массива длиной n
Из алгоритма видно (см. рисунок 3.6), что суммирование элементов хi осуществляется по рекуррентной формуле n раз
поэтому перед началом выполнения цикла у0 присваивается значение нуль.
В результате, в первом цикле, когда i = 1,
Рисунок 3.6 – Блок-схема алгоритма циклического вычислительного
Поскольку после определения переменной y в n циклерасчет завершается, т.е. массив X больше не нужен, то в алгоритме формирование данного массива не требуется и, таким образом, с целью экономии памяти в ЭВМ при вводе элементов массива xi в алгоритме отводится лишь одна ячейка памяти x (см. блок у = у + x, где вместо элементов массива xi с адресами в количестве n используется лишь один адрес x , отведенный как под обычную переменную). Таким образом, после завершения работы алгоритма от массива X сохранится только последний его элемент xn.
Вопросы для самопроверки
1 Что такое алгоритм?
2 Зачем нужно составлять алгоритмы?
3 Какие существуют способы изображения алгоритмов?
4 Блок-схемы типовых задач.
5 Обычно выделяют следующие этапы решения задач на ЭВМ:
– выбор или разработку методов решения задачи;
– написание и ввод программы в ЭВМ;
– отладку и тестирование программы;
– подготовку данных и выполнение расчетов на ЭВМ.
Источник: megaobuchalka.ru
21 Управляющие конструкции алгоритмы языка. Основные структуры алгоритмов
Большинство алгоритмических языков относится к так называемым процедурным языкам в которых основной единицей является оператор. Оператор представляет собой команду на выполнение некоторого действия. Язык таким образом состоит в основном из фраз в повелительном наклонении. Альтернативной оператоам яввляются описания, определяющие объекты или типы объектов и их взаимосвязи.
Всякий алгоритм предназначен исполнителю, который однозначно понимает команды алгоритма.
Строки алгоритма представляют собой фразы в повелительном наклонении, которые предназначены исполнителю алгоритма.
Строки алгоритма вполняются последовательно (считается, что исполнитель алгоритма способен не задумываясь выполнить каждую его команду).
Большинство алгоритмов не сводится, однако, к последовательному выполнению команд, в них присутствуют ветвления и циклы. При ветвлении в зависимости от условия выполняется одна из ветвей программы; для этого используется оператор «если… то… иначе… конец если»
Цикл пока — цикл с предусловием, поскольку условие продолжения цикла проверяется перед выполнением тела цикла, а не после него. Иногда используют циклы с постусловием (do … while), когда тело цикла высегда выполняется хотя бы 1 раз.
Запись алгоритма на неформальном языке представляет собой последовательность команд исполнителю алгоритма. Запись может также включать управляющие конструкции: ветвление, или условные ойператор, и цикл «пока».
— Если условие
— то последовательность действий 1
— иначе последовательность действий 2
— конец если
Основные структуры алгоритмов
Основные структуры алгоритмов — это ограниченный набор стандартных способов соединения отдельных блоков или структур для выполнения типичных последовательностей действий.
Структурный подход предполагает использование только нескольких основных структур, комбинация которых дает все многообразие алгоритмов и программ.
Следование — это последовательное размещение блоков и групп блоков, такая структура называется также линейной.
Если некоторая часть программы выполняется многократно и после проверки некоторого условия в какой-то момент осуществляется выход из нее, то такую часть называют циклом.
Если после проверки некоторого условия выбирается один из двух или более путей, вычислительного процесса и после выполнения любого из них вычислительный процесс опять сводится водно русло, то возникает разветвление.
Цикл до — применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнеия некоторого условия. Особенность этого цикла в том, что он всегда выполняется хотя бы один раз, т.к. первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено.
Тело цикла, — та последовательность действий, которая выполняется многократно, в цикле.
Цикл пока — отличается от цикла до тем, что проверка условия производится до выполенния тела цикла — такой цикл называется циплом по условию.
Обход — частный случай разветвления, когда одна ветвь не содержит никаких действий. Множественный выбор является обобщением разветвления, когда в зависимости от значения переменной выполняется ОДНО ИЗ нескольких действий.
Источник: konyakov.ru