Базовые алгоритмические структуры

Понятие структурного подхода

Структурный подход к разработке алгоритмов

Структурный подход при разработке алгоритмов заключается в разложении вычислительного процесса на возможные составные части, установлении порядка их следования, описании содержания каждой такой части в той или иной форме и последующей проверке, которая должна показывать, обеспечивается ли реализация выбранного метода.

В большинстве случаев не удается сразу получить удовлетворительный результат. По этому составление алгоритма проводиться методом «проб и устранения ошибок» и получения окончательного варианта требуется несколько шагов коррекции и анализа.

Как правило, в процессе разработки алгоритм проходит несколько этапов детализации. Первоначально составляется схема алгоритма, в которой отражаются наиболее важные и существенные связи между исследуемыми процессами (или частями процесса). На следующих этапах раскрываются (детализируются) выделенные на предыдущих этапах части вычислительного процесса, имеющие некоторое самостоятельное значение. Кроме того, на каждом этапе детализации выполняется многократная проверка и исправление (отработка) схемы алгоритма. Подобный подход позволяет избежать возможных ошибок решений.

Ориентируясь на крупноблочную структуру алгоритма можно быстрее и проще разработать несколько различных его вариантов, провести их анализ, оценку и выбрать наилучший.

Опыт практической алгоритмизации, накопленный в связи с составлением программ» привел к формированию особой методики структурной организации алгоритмов, использование которой уменьшает вероятность ошибок в процессе разработки и записи алгоритмов. Эту методику называют структурным подходам.

В основу структурного подхода положены следующие положения:

1. Алгоритм и программа должны составляться поэтапно (по шагам).

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

3.Логика алгоритма и программы должна опираться на минимальное число достаточно простых базовых алгоритмических структур.

При структурном подходе к разработке алгоритмов они как бы «собираются» из трех основных (базовых) структур: ПОСЛЕДОВАТЕЛЬНОСТЬ (СЛЕДОВАНИЕ), РАЗВЕТВЛЕНИЕ, ЦИКЛ.

При словесном описании записи алгоритма указанных структур имеют соответственно следующий смысл: «выполнить S1; выполнить S2», «если Р, то выполнить S1, иначе выполнить S2», «до тех пор, пока Р, выполнять S», где Р -условие; S, S1, S2 -действия.

Базовая структура ПОСЛЕДОВАТЕЛЬНОСТЬ состоит из двух функциональных блоков S1 и S2, каждый из которых в простейшем случае может быть арифметическим элементом. Структура ПОСЛЕДОВАТЕЛЬНОСТЬ означает, что два функциональных блока могут быть размещены друг за другом.

Базовая структура РАЗВЕТВЛЕНИЕ (ВЕТВЛЕНИЕ) состоит яз логического элемента с проверкой некоторого условия Р и функциональных блоков S1, S2, которые в простейшем случае являются арифметическими элементами. Разветвление может быть двух видов: полная запись разветвлений (рис.2 б) и сокращённая запись (рис.2 г). Расстановка значений истинности логического выражения Р «да» и «нет» на приведенном рисунке условна, на практике она вытекает из смысла конкретной задачи.

Структура ветвление существует в четырех основных вариантах:

если-то	если-то-иначе
Выбор	выбор-иначе

Примеры команды если

Базовая структура ЦИКЛ может быть трех видов: структура цикла с параметром, с предусловием, с постусловием. в состав цикла входит логическийэлемент с проверкой условия Р и функциональный блок S, называемый тело цикла.

В простейшем случае S является обычным арифметическим элементом.

В структуре цикла с параметром блок S размещен после специального блока организации цикла I в котором задается параметр выполнения цикла и осуществляется проверка условия завершения цикла.

В структуре цикла с предусловием блок S размещен после проверки условия Р так, что может оказаться, что тело S при определенных условиях не выполниться ни разу. Этот вариант базовой структуры ЦИКЛ, управляемый предусловием, называют ЦИКЛ-ПОКА.

В структуре цикла с постусловием блок S расположен до проверки условия Р так, что в этом варианте цикла тело S в любом случае будет выполнено по крайней мере один раз. Этот вариант базовой структуры ЦИКЛ называют ЦИКЛ-ДО.

Основой методики структурного подхода являются следующие соглашения, которые для построения более сложных алгоритмов из указанных простейших базовых структур разрешают:

1) подсоединять одну структуру к другой, образуя последовательность структур.

2) заменять функциональные блоки S1 и S2 любой из базовых структур.

Сформулированные выше правила позволяют строить сколь угодно сложные по структуре алгоритмы, развивая их не только «вширь», но и «вглубь».

Какие циклы называют итерационными?

Особенностью итерационного цикла является то, что число повторений операторов тела цикла заранее неизвестно. Для его организации используется цикл типа пока. Выход из итерационного цикла осуществляется в случае выполнения заданного условия.

На каждом шаге вычислений происходит последовательное приближение и проверка условия достижения искомого результата

Алгоритм, в состав которого входит итерационный цикл, называется итеpационным алгоpитмом. Итерационные алгоритмы используются при реализации итерационных численных методов.

В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса). В противном случае произойдет зацикливание алгоритма, т.е. не будет выполняться основное свойство алгоритма - результативность.

Что такое вложенные циклы?

Возможны случаи, когда внутри тела цикла необходимо повторять некоторую последовательность операторов, т. е. организовать внутренний цикл. Такая структура получила название цикла в цикле или вложенных циклов. Глубина вложения циклов (то есть количество вложенных друг в друга циклов) может быть различной.

При использовании такой структуры для экономии машинного времени необходимо выносить из внутреннего цикла во внешний все операторы, которые не зависят от параметра внутреннего цикла.

Вычислить сумму элементов заданной матрицы А(5,3).

Матрица А

p(p-a)(p-b)(p-c);

Дата добавления: 2014-01-07