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

124
ход  к  конструированию  и  оформлению  алгоритмов,  позволяющий
уменьшить количество ошибок в алгоритмах, упрощающий их кон-
троль и модификацию.
По своей сути структурный подход есть отказ от беспорядочного
стиля в алгоритмизации и программировании (в частности, отказ от
оператора  goto)  и  определение  ограниченного  числа  стандартных
приемов построения легко читаемых алгоритмов и программ с ясно
выраженной структурой.
Теоретическим  фундаментом  этого  подхода  является  теорема  о
структурировании, из которой следует, что алгоритм решения любой
практически вычислимой задачи может быть представлен с исполь-
зованием трех элементарных базисных управляющих структур: струк-
туры  следования  или  последовательности  (рис.  9.7,
а);  структуры
ветвления (рис. 9.7,
б ); структуры цикла с предусловием (рис. 9.7, в),
где
P — условие, S — оператор.
Базисный набор управляющих структур является функционально
полным, т. е. с его помощью можно создать любой сколь угодно слож-
Рис. 9.7. Базисные
управляющие
структуры
Рис.  9.8.  Дополнительные  управляющие
структуры (
а — в)

125
ный алгоритм. Однако для создания более компактных и наглядных
алгоритмов  дополнительно  используются  следующие  управляющие
структуры: структура сокращенного ветвления (рис. 9.8,
а); структу-
ра выбора (рис. 9.8,
б ); структура цикла с параметром (рис. 9.8, в);
структура цикла с постусловием (рис. 9.8,
г).
В разных языках программирования реализация базовых управ-
ляющих структур может быть различной. В языке Паскаль реализо-
ваны все рассмотренные структуры.
Любой алгоритм может быть построен посредством композиции
базисных и дополнительных структур:
их последовательным соединением
•
- образованием последова-
тельных конструкций;
их вложением друг в друга
•
- образованием вложенных конструкций.
Например,  алгоритм  Евклида,  описанный  ранее,  представляет
собой  комбинацию  из  трех  управляющих  структур:  последователь-
ности, цикла и ветвления (рис. 9.9).
Рис. 9.9. Алгоритм Евклида как композиция базисных структур

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

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

128
Каждая из структур может рассматриваться как один блок с одним
входом и одним выходом. Таким образом, мы можем ввести преоб-
разование любой структуры в функциональный блок. Тогда всякий
алгоритм, составленный из стандартных структур, поддается после-
довательному  преобразованию  к  единственному  функциональному
блоку, и эта последовательность преобразований может быть исполь-
зована как средство понимания алгоритма и доказательства его пра-
вильности.
Обратная  последовательность  преобразований  может  быть  ис-
пользована в процессе проектирования алгоритма по нисходящей
схеме с постепенным раскрытием единственного функционально-
го блока в сложную структуру основных элементов. В области ав-
томатизированной  обработки  данных  такой  подход  называют
нисходящим  проектированием  или  проектированием  «сверху
вниз».
Разработка алгоритма по нисходящей схеме начинается с разбие-
ния сложной исходной задачи на отдельные более простые подзадачи,
решение которых может быть представлено в общей структуре алго-
ритма  функционально  независимыми  блоками.  Разработку  логиче-
ской  структуры  каждого  такого  блока  и  ее  модификацию  можно
осуществлять независимо от остальных блоков. На первом этапе про-
екта раскрываются наиболее важные и существенные связи в иссле-
дуемой  задаче,  составляется  укрупненная  схема  алгоритма,  опреде-
ляются  функциональное  назначение  каждого  блока,  его  входные  и
выходные данные. На последующих этапах проектирования уточня-
ется логическая структура отдельных функциональных блоков общей
схемы, строятся схемы алгоритмов, выделенных ранее подзадач. Раз-
работка алгоритма каждой подзадачи также может осуществляться в
несколько этапов детализации. На каждом этапе проекта выполня-
ются многократные проверки и исправления алгоритма. Подобный
подход  является  рациональным,  позволяет  значительно  ускорить
процесс разработки сложных алгоритмов и в значительной мере из-
бежать ошибочных решений.
В  качестве  примера  рассмотрим  задачу  табулирования  функции
одной переменной, т. е. вычисление значений функции
у 
= f(x) для
всех  значений
х,  изменяющихся  от  х
0
до
х
n
 с  шагом
h
x
,  сокращен-
но:
x
= х
0
(
h
x
)
х
n
.
Пусть
y
z
x
x
z
x
x a
x
a x b
x
x
=
+
+
=
≤
< <
≥
2
2
2
ln(
)
,
sin ,
;
cos ,
;
,
где
если
если
если
tg
bb,





где
a, b, x
0
,
h
x
,
x
n
— исходные данные.

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

жүктеу/скачать 4,7 Mb.

Достарыңызбен бөлісу: