Технология разработки алгоритмов

⇐ ПредыдущаяСтр 11 из 25Следующая ⇒

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

Какими качествами должен обладать хороший алгоритм?

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

По своей сути структурный подход есть отказ от беспорядочного стиля в алгоритмизации и программировании (в частности, отказ от оператора go to) и определение ограниченного числа стандартных приемов построения легко читаемых алгоритмов и программ с ясно выраженной структурой. Теоретическим фундаментом этого подхода является теорема о структурировании, из которой следует, что алгоритм решения любой практически вычислимой задачи может быть представлен с использованием трех элементарных базисных управляющих структур: а) структуры следования или последовательности; б) структуры ветвления; в) структуры цикла с предусловием (рис. 9.7, соответственно а, б, в, где P – условие, S – оператор).

Рис. 9.7. Базисные управляющие структуры

Базисный набор управляющих структур является функционально полным, то есть с его помощью можно создать любой сколь угодно сложный алгоритм. Однако с целью создания более компактных и наглядных алгоритмов дополнительно используются следующие управляющие структуры: а) структура сокращенного ветвления; б) структура выбора; в) структура цикла с параметром; г) структура цикла с постусловием (рис. 9.8, соответственно а, б, в, г).

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

Рис. 9.8. Дополнительные управляющие структуры

Любой алгоритм может быть построен посредством композиции базисных и дополнительных структур:

- путем их последовательного соединения - образования последовательных конструкций;

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

Например, алгоритм Евклида, описанный ранее, представляет собой комбинацию из трех управляющих структур: последовательности, цикла и ветвления (рис. 9.9).

Рис. 9.9. Алгоритм Евклида как композиция базисных структур

Каждая из структур может рассматриваться как один блок с одним входом и одним выходом. Таким образом, мы можем ввести преобразование любой структуры в функциональный блок. Тогда всякий алгоритм, составленный из стандартных структур, поддается последовательному преобразованию к единственному функциональному блоку и эта последовательность преобразований может быть использована как средство понимания алгоритма и доказательства его правильности. Обратная последовательность преобразований может быть использована в процессе проектирования алгоритма по нисходящей схеме с постепенным раскрытием единственного функционального блока в сложную структуру основных элементов. В области автоматизированной обработки данных такой подход называют нисходящим проектированием или проектированием «сверху вниз».

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

В качестве примера рассмотрим задачу табулирования функции одной переменной, то есть вычисление значений функции у = f(x) для всех значений х, изменяющихся от х₀до х_n с шагом h_x, сокращенно:
x = х₀(h_x) х_n.

Пусть

где

a, b, x₀, h_x, x_n – исходные данные.

Процесс проектирования алгоритма табулирования функции у = f(x) показан на рис. 9.10, а. На первом уровне детализации схема отражает процесс табулирования функции в общем виде (блоки 1.1-1.5). Далее осуществляется детализация блока 1.4 в виде последовательности блоков 2.1-2.3 второго уровня. Функция z = z(x), входящая в определение исходной функции, представлена разветвляющейся структурой третьего уровня детализации (блоки 3.1-3.5).

Рис. 9.10. Нисходящая схема проектирования
алгоритма вычисления сложной функции

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

Рис. 9.10. Окончание. Алгоритм вычисления сложной функции

Структуры алгоритмов

⇐ Предыдущая 6 7 8 9 101112 13 14 15 Следующая ⇒