2. Восходящее программирование

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

Восходящее программирование предполагает проектирование программы ‘‘снизу

вверх’’(bottom – up programming) [8]. Сначала отдельно проектируются и отлаживаются программы для каждой простой подзадачи, а затем разработанные модули последовательно (поочередным подключением) объединяются в единую программу.

Примером проектирования программного комплекса с известными подзадачами является выполнение расчетно‑графической работы (РГР) по дисциплине ‘‘Алгоритмические языки и программирование’’.

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

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

Отчет по РГР

печатается в текстовом редакторе Word

и включает следующие разделы:

1. Задание.

2. Математическая формулировка задачи.

3. Детальная схема общего алгоритма.

4. Текст программы.

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

6. Графики функций, напечатанные через Excel.

7. Заданное нелинейное уравнение и результат его

решения.

8. Интеграл, метод решения и результат.

Рис. 1.7. Схема алгоритма для РГР

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

возможности программной реализации проведем математический анализ этого метода и спроектируем алгоритм [6].

Пусть задано уравнение f(x)=0 и интервал [a,b], где функция f(x) непрерывна, имеет разные знаки на концах интервала.

Алгоритм нахождения корня на интервале методом половинного деле­ния (бисекции) сводится к следующей последовательности действий:

1) вычисляется середина интервала c= (a+b)/2;

2) если |f(c)|<e, где e= 10^-3 - 10^-5 определяет погрешность вы­числений, то c будет являться приближенным значением корня уравнения и выводится как результат расчетов;

3) если |f(c)|>e, то проверяются знаки функций f(a) и f(c) на концах отрезка [a,c], для чего вычисляется их произведение. Если f(a)f(c)<0, то функции будут иметь противоположные знаки и корень находится на отрезке [a,c]. В этом случае интервал [a,b] заменяется отрезком [a,c], для чего присвоим b=c;

4) иначе, если f(a)f(c)>0, корень уравнения находится на отрезке [c,b] и в расчетах интервал [a,b] заменяется [c,b], для чего прис­воим a=c;

5) вычисления по схеме п.1-п. 4 повторяются в итерационном цикле до тех пор, пока не выполнится условие п. 2 - |f(c)|< e.

В случае метода хорд схема алгоритма расчета корня уравнения ос­тается прежней за исключением п.1, в котором нужно использовать формулу

c= (af (b)-b f(a))/(f(b)-f(a)).

Для исключения зацикливания следует правильно определять начальный интервал [a,b], чтобы выполнялось условие f(a)f(b)<0. Схема алгоритма для метода половинного деления приведена на рис.1.8.

Рис. 1.8. Схема алгоритма решения нелинейного уравнения

Отладив программу для решения нелинейного уравнения, включим ее в общую программу для реализации задания по РГР.

Затем аналогичным образом проанализируем и разработаем программу для вычисления определенного интеграла.

Приближенное значение определенного интеграла вычисляется как сумма площадей N прямоугольников, построенных на интервале интегриро­вания [a,b]. Интервал [a,b] разбивается на N равных частей длиной h = (b-a)/N, на каждой из которых строится прямоугольник с высотой, рав­ной значению функции f(x_i) в центре участка с координатой

x_i = a+(i-0.5)h, где i=1,2,...,N

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

.

В методе трапеций интервал [a,b] разбивается на N равных частей длиной h=(b- a)/N, на каждой из которых строится трапеция. Приближен­ное значение интеграла определяется суммой площадей трапеций, постро­енных на интервале [a,b]

где x_i =a+i* h .