Лекция 7. Основы алгоритмизации (продолжение)
Разработка алгоритма – это по сути дела составление плана решения задачи. В алгоритме надо тщательно спланировать все действия компьютера при решении задачи.
Правила разработки алгоритмов определены в теории структурного программирования, основу которой составляют следующие принципы (слайд 11):
1. Алгоритмы должны разрабатываться по шагам по принципу "сверху вниз", начиная с укрупненной схемы и заканчивая детализированной.
2. Сложную задачу целесообразно разбивать на подзадачи (простые блоки), а программу составлять из модулей (независимых частей), имеющих простую структуру и допускающих независимую отладку.
3. Логика алгоритма и программы должна опираться на минимальное число простых базовых конструкций, имеющих заранее определенную структуру.
4. В алгоритмах и программах базовые алгоритмические структуры могут быть вложены друг в друга произвольным образом.
5. Повторяющиеся фрагменты алгоритма (программы) следует оформлять в виде подпрограмм.
Применение этих положений позволяет систематизировать работу программиста, получать структурированные алгоритмы и программы, которые легко читать, проверять и использовать на практике.
Каждая алгоритмическая конструкция имеет фиксированную структуру, один вход и один выход, а также предполагает выполнение конкретного действия. В программах базовые алгоритмические структуры реализуются операторами алгоритмического языка.
Элементарной структурной единицей алгоритма является функциональный блок, а программы – оператор. Этот блок предполагает один шаг преобразования, обработки или отображения информации. Команда функционального блока является указателем на выполнение действия, а оператор алгоритмического языка – описанием этого действия в программе.
При разработке алгоритмов на основе принципов структурного программирования используют метод пошаговой детализации (слайд 12). Метод состоит в том, что алгоритм строится за один или несколько шагов в зависимости от сложности решаемой задачи.
На первом шаге процесс решения задачи делится на крупные действия. Каждое действие записывается в виде четкой инструкции, указывающей, что делать (но не как делать). Затем разрабатывается укрупненная схема алгоритма, показывающая общий порядок решения задачи. На этом этапе схема обычно имеет вид простой последовательности функциональных блоков или других базовых конструкций.
На втором и последующих шагах крупные действия уточняются и детализируются. Для каждого действия определяется своя последовательность более мелких действий, которая указывает, как должно выполняться это действие. Функциональные блоки укрупненной схемы алгоритма замещаются соответствующими последовательностями базовых алгоритмических структур.
Детализация заканчивается на том шаге, после которого алгоритм становится пригодным для программирования, т.е. когда каждая конструкция алгоритма может быть представлена в программе одним оператором алгоритмического языка.
На каждом шаге детализации используется метод замещения, который определяет правила построения алгоритма из базовых конструкций. В соответствии с этим методом сложные конструкции алгоритмов можно получить двумя способами (слайд 13):
1. Последовательным соединением конструкций, при котором выход одной конструкции соединяется с входом следующей за ней конструкции (рис. 10а). Благодаря этому образуется простая последовательность конструкций, и действия выполняются в естественном порядке.
2. Вложением конструкций друг в друга путем замены функциональных блоков другими конструкциями. Связи замещаемого блока должны сохраняться. На рис. 10б,в показано замещение функционального блока S2 в Последовательности конструкциями Выбор и Повторение. Таким образом, заменяемый функциональный блок при вложении может замещаться как последовательностью элементарных функциональных блоков, так и целыми алгоритмическими конструкциями.
| а) | б) в) |
Рис. 10. Способы получения сложных конструкций алгоритмов:
а) последовательное соединение конструкций
б,в) вложение конструкций Выбор и Повторение
Еще одним методом, применяемым при разработке сложных алгоритмов, является использование вспомогательных алгоритмов (подпрограмм). Вспомогательные алгоритмы рассматриваются как отдельные блоки, решающие вспомогательные задачи (слайд 14).
| В этом случае в основном алгоритме при замещении некоторого функционального блока указывается лишь ссылка на вспомогательный алгоритм, т.е. специальный функциональный бло к Предопределенный процесс (рис. 11). Сам же вспомогательный алгоритм оформляется как самостоятельный алгоритм. Таким образом, алгоритм решения всей задачи складывается из основного и множества вспомогательных алгоритмов. | 
Рис. 11. Использование вспомогательного алгоритма (подпрограммы)
|
6. Пример разработки алгоритма с использованием
метода пошаговой детализации и вспомогательных алгоритмов
Продемонстрируем применение положений, изложенных в предыдущем разделе, на примере следующей задачи (слайд 15):
Разработать алгоритм вычисления периметра p и площади s треугольника по заданным координатам трех его вершин: x1, y1; x2, y2; x3, y3.
Для решения задачи воспользуемся известными формулами:
Р = А + В + С;
S= 
( формула Герона);
A = 
; B = 
;
C = 
,
где Рр = Р/2 – полупериметр; A, B, C – длины сторон треугольника.
Начнем проектирование алгоритма методом “сверху вниз”. Так как решение задачи реализуется с помощью алгоритмов простейшей линейной структуры, вместо схем алгоритмов будем приводить словесные описания процедур и их параметров.
На самом верхнем (первом) уровне алгоритм решения задачи можно укрупненно представить в виде вызова процедуры с именем CalcPS (рис. 12, слайд 16):
Рис. 12. Укрупненная схема алгоритма решения задачи
На следующем, втором уровне, детализируем алгоритм процедуры CalcPS путем представления его в виде последовательности вызовов следующих трех процедур (рис. 13, слайд 17):
– процедуры ввода координат вершин треугольника с именем GetCoord;
– процедуры вычисления периметра и площади треугольника с именем PS;
– процедуры вывода вычисленных значений периметра и площади с именем PutPs.
Рис. 13. Результат второго уровня детализации алгоритма
Перейдем теперь к следующему, третьему уровню детализации. Процедуры GetCoord и PutPs дальнейшей детализации не требуют, так как средства ввода-вывода имеются в любом языке программирования. Поэтому на следующем, третьем шаге детализируем процедуру вычисления периметра и площади PS (слайд 18). Из расчетных формул видно, что для вычисления периметра и площади в первую очередь должны быть вычислены длины сторон по одной и той же формуле с разными параметрами. Поэтому на этом уровне детализации воспользуемся одной и той же процедурой LenS, которая будет вызываться из процедуры PS 3 раза.
Имеет смысл также выделить вычисление периметра и площади треугольника в отдельные процедуры, так как в каких–то других задачах они могут вычисляться не совместно, как в данной задаче, а порознь. Поэтому на данном уровне детализации используем еще две процедуры: процедуру вычисления периметра CalcP, и процедуру вычисления площади CalcS (рис. 14).
Наконец, на последнем уровне детализации разработаем схемы алгоритмов процедур LenS, CalcP и CalcS. Эти алгоритмы полностью определяются заданными расчетными формулами и представляются линейными алгоритмическими структурами. Схемы алгоритмов приведены на рис. 15-17 (слайды 19-21).
Рис. 14. Схема алгоритма Рис. 15. Схема алгоритма
процедуры PS процедуры LenS
Рис. 16. Схема алгоритма Рис. 17. Схема алгоритма
процедуры CalcP процедуры CalcS
При разработке алгоритмов решения сложных задач наряду со схемами алгоритмов полезной бывает схема иерархии процедур, показывающая их подчиненность, т.е. из каких процедур вызываются другие процедуры. Схема иерархии процедур рассмотренной задачи изображена на рис. 17 (слайд 22).
В заключение заметим, что разработанный алгоритм и схема иерархии процедур носит демонстрационный характер. На самом деле при разработке алгоритмов (и программ) решения различных задач в них всегда включаются процедуры контроля корректности входных данных. Это позволяет избежать ошибок при выполнении программы из-за выхода аргументов функций и выражений за границы области допустимых значений.
Рис. 18. Схема иерархии процедур для решения задачи
Так, в рассмотренной задаче после вычисления длин сторон треугольника необходимо проверить каждую из них на неравенство нулю и убедиться в том, что сумма любых двух его сторон больше третьей стороны. В случае нарушения какого-либо из этих условий следует выдать пользователю соответствующее сообщение и аварийно завершить выполнение программы.