Лекция
В соответствии с методологией структурного программирования метод последовательной детализации является основным подходом при проектировании сложных алгоритмов. Суть метода состоит в следующем:
1) анализируется исходная задача, в ней выделяются подзадачи, строится иерархия таких подзадач (см. рис.);
2) составляются алгоритмы (программы), начиная с основного алгоритма (основной программы), далее — вспомогательные алгоритмы (подпрограммы) с последовательным углублением уровня.
Проиллюстрируем применение метода последовательной детализации на несложном примере.
Пример 1
Вычислить площадь выпуклого N-угольника, заданного координатами своих вершин (см. рис.).
Метод решения задачи заключается в следующем: выпуклый N-угольник разбивается диагональными линиями, выходящими из одной вершины, на N - 2 треугольника. Площадь многоугольника вычисляется как сумма площадей треугольников. Площади треугольников вычисляются по формуле Герона:
где р — полупериметр треугольника, а, b, с — длины сторон треугольника. Длины сторон вычисляются по формуле, следующей из теоремы Пифагора. Например, длина отрезка между точками с координатами (x1, у1), (х2, у2) равна:
Основной задачей является вычисление площади многоугольника. Подзадачей для основной задачи является вычисление площади треугольника. Подзадачей вычисления площади треугольника является вычисление длины отрезка. Соотношение между этими задачами и соответствующими программами показано на рисунке.
Организация данных: исходные данные — координаты вершин N-угольника будут храниться в двух массивах: X[1..N], Y[1..N].
На первом шаге детализации составляется основная программа без подробного программирования используемых в ней подпрограмм первого уровня. Однако должны быть записаны интерфейсы подпрограмм первого уровня. Интерфейс здесь — это заголовок подпрограммы: имя и список формальных параметров. Интерфейсы необходимы для того, чтобы в основной программе можно было организовать обращения к подпрограммам первого уровня детализации.
В программе об N-угольнике подпрограмму Treugolnik сделаем процедурой.
На втором шаге детализации запрограммируем процедуру Treugolnik. В разделе подпрограмм этой процедуры запишем лишь интерфейс подпрограммы Line, которую сделаем функцией.
На третьем шаге детализации запрограммируем функцию Line. Формальные координаты концов отрезка заданы параметрами: (Ха, Yа) — первая точка, (Xb, Yb) — вторая точка.
Из составленных фрагментов собираем окончательный вариант программы
В этой программе значение N может быть любым, начиная с 3, т. е. N > 3. Константа N описана глобально в основной программе, поэтому область этого описания распространяется на все подпрограммы. Все остальные величины в подпрограммах определены локально.
Показанный в рассмотренном примере способ построения программы называют еще программированием «сверху вниз»: начиная с основной программы, последовательно переходя к подпрограммам все более глубокого уровня детализации.
Работу полученной программы можно проверить на простом примере. Пусть N = 4. Вычислим площадь квадрата с длинами сторон, равными 2 и следующими координатами вершин:
Х[1]=0, X[2]=0, Х[3]=2, Х[4]=2
Y[l]=0, Y[2]=2, Y[3]=2, Y[4]=0
После ввода этих значений в результате получим:
Площадь фигуры =4
Применение метода последовательной детализации позволяет разделить работу над большим программным проектом между несколькими программистами. Один человек — руководитель группы проектирует многоуровневую структуру алгоритма и составляет основную программу, а написание подпрограмм поручается другим членам группы. Для согласования работы программ договариваются лишь о интерфейсах: именах и параметрах подпрограмм. А внутреннее устройство подпрограммы — дело программиста, ее составляющего. При составлении больших проектов подпрограммы объединяются в модули.