Пошаговая детализация и нисходящее проектирование
Технология нисходящего проектирования с пошаговой детализацией является неотъемлемой частью создания хорошо структурированных программ. При написании программы с использованием этой технологии вся задача рассматривается как единственное предложение (вершина), выражающее общее назначение программы. Так как вершина редко отображает достаточное количество деталей, на основании которых можно написать программу, то поэтому надо начинать процесс детализации. Вершина разделяется на ряд более мелких задач в том порядке, в котором эти задачи должны выполнятся. В результате получим первую детализацию. Далее каждая из подзадач разбивается на подзадачи, принадлежащие второму уровню детализации. Программист завершает процесс нисходящей разработки с пошаговой детализацией, когда алгоритм настолько детализирован, чтобы его можно было бы преобразовать в программу.
Вывод: пошаговая реализация это тактика разработки программы, а нисходящее проектирование это стратегия программирования.
Цели структурного программирования:
1. Обеспечить дисциплину программирования.
2. Улучшить читабельность программы.
3. Повысить эффективность программы.
4. Повысить надежность программы.
Рекурсия и итерация
Рекурсией — называется ситуация, когда программа вызывает сама себя непосредственно или косвенно (через другие функции).
Явный вызов.
Косвенный вызов. А вызывает В, В вызывает А, обе функции рекурсивны.
Обычный вызов означает, что в тот момент когда вызывается некоторая программа, следует остановка основной программы, запоминание точки вызова, затем выделяется память для подпрограммы. Все поочередно-вызываемые подпрограммы образуют структуру-стек, то же самое происходит и с данными, таким образом затраты на память связаны с глубиной стека.
Рекурсивная задача в общем случае разбивается на ряд этапов. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи — так называемую базовую задачу (или несколько таких задач). Если функция вызывается для решения базовой задачи, она просто возвращает результат. Если функция вызывается для решения более сложной задачи, то она делит эту задачу на две части: одну часть, которую функция решать умеет, и ту которую решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но по сравнению с ней проще или несколько меньше. Поскольку новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой — это называется рекурсивным вызовом или шагом рекурсии. Шаг рекурсии выполняется до тех пор, пока исходное обращение функции еще не закрыто. Шаг рекурсии может приводить к большому числу таких рекурсивных вызовов, поскольку функция продолжает деление каждой новой подзадачи на две части.
Задача: написать подпрограмму решения уравнения f(x)=0, если известно, что f(x) непрерывна на [a,b] и имеет разные знаки на концах отрезка.
Далее приводится пример программы содержащей итеративный и рекурсивный метод решения этой задачи.
program test;
{$N+} {генерация кода с помощью сорпоцессора
математических вычислений 8087 }
uses crt;
Type _Real = single;
_FR2R = function(x : _Real) : _Real;
{——————————рекурсивный метод——————————————}
Procedure Solve(a,b : _Real;f:_FR2R; eps : _Real; var root : _Real);
{a,b - концы отрезка,f-левая часть уравнения f(x)=0,eps>0-точность решения,
предпологается f -непрерывна и имеет разные знаки на концах a и b,
root - найденный корень}
var fa,fb,fr : _Real;
Begin
fa:=f(a); {вычисление значения функции на конце отрезка}
root := (a+b)/2.0; {деление отрезка пополам}
fr:= f(root); {вычисление значения функции в середине отрезка}
if fr=0.0 then exit; {если 0 то выход}
if abs(b-a)<2.0*eps then exit; {провепка точности}
if ((fa>0.0) and (fr<0.0)) or ((fa<0.0) and (fr>0.0)) then
{проверка знака на концах}
solve(a,root,f,eps,root)
else solve(root,b,f,eps,root);
end;
{—————————метод итераций—————————————————}
Procedure Solve1(a,b : _Real;f:_FR2R; eps : _Real; var root : _Real);
var eps2,fa,fb,fr : _Real;
begin
fa:=f(a); {вычисление значения функции на концах отрезка}
fb:=f(b);
eps2:=2.0*eps;
while abs(b-a)>eps2 do {прерывем если погрешность меньше заданной}
begin
root:=(a+b)/2.0;
fr:=f(root); {вычисление значения функции в середине}
if fr=0 then break; {если 0 то выход из подпрограммы}
if ((fa>0.0) and (fr<0.0)) or ((fa<0.0) and (fr>0.0)) then{проверка знака}
begin
b:=root; {переименовываем концы}
fb:=fr;
end
else
begin
a:=root;
fa:=fr;
end;
end;
root := (a+b)/2.0; {уменьшения отрезка}
end;
function f1(x:_Real):_Real;far;
begin
f1:=sqr(x)-4.0; {задание функции}
end;
function f2(x:_Real):_Real;far;
begin
f2:=cos(x)-x; {задание функции}
end;
var a,b,x,eps :_Real;
begin
clrscr;
write('a,b,eps 1-го уравнения: ');
readln(a,b,eps);
solve(a,b,f1,eps,x);
writeln('x1 = ',x);
solve1(a,b,f1,eps,x);
writeln('x2 = ',x);
write('a,b,eps 2-го уравнения: ');
readln(a,b,eps);
solve(a,b,f2,eps,x);
writeln('x3 = ',x);
solve1(a,b,f1,eps,x);
writeln('x4 = ',x);
end.
Данная программа демонстрирует два метода решения поставленной задачи. Рекусивный метод менее эффективен, так как каждый раз программа распологает все данные в стеке. Для доказательства правильности работы рекурсивной программы можно воспользоваться методом математической индукции.
Задача о Ханойских башнях: легенда гласит, что в одном из монастырей Дальнего Востока монахи пытались переместить стопку дисков с одного колышка на другой. Начальная стопка имела 64 диска, нанизанных на один колышек так, что их размеры последовательно уменьшались к вершине. Монахи пытались переместить эту стопку с этого колышка на второй при условии, что при кажлом перемещении можно брать только один диск и больший диск никогда не должен находиться над меньшим диском. Третий колышек предоставляет возможность временного размещения дисков. Считается, что когда монахи решат эту задачу наступит конец света.
Требуется чтобы программа печатала четкую последовательность перемещений
дисков с колышка на колышек.
Источник Приемник Вспомогательный
Программа, демонстрирующая решение задачи выводит последовательность в файл с именем Proces.txt.
Type _Name = char;{тип совместимый с выводом в текстовый файл}
_Unsign = byte;
Procedure HT(source,dest,tmp :_Name;n:_Unsign; var F:text);
{sourece,dest,tmp - названия источника, приемника и вспомогательного колышка, n - число дисков, F - файл, открытый для записи. Процедура печатает список ходов,файл остается открытым}
begin
if n = 1 then writeln(F,source,'->',dest) {если диск один то сразу перемещаем его на колышек приемник}
else
begin
HT(source,tmp,dest,n-1,F); {меняем местами вспосогательный и приемник колышки}
writeln(F,source,'->',dest); {выводим шаг}
HT(tmp,dest,source,n-1,F); {меняем местами вспомогательный и источник колышки}
end;
end;
var n:_Unsign;
f : text;
s,d,t : _name;
f_name : string;
begin
write('Введите названия источника: ');
readln(s);
write('Введите названия приемника: ');
readln(d);
write('Введите названия вспомогательного диска: ');
readln(t);
write('Введите количество дисков: ');
readln(n);
assign(f,’Process.txt’); {связываем файловую переменную с именем файла}
rewrite(f); {инициируем запись в файл}
HT(s,d,t,n,f); {вызов функции}
end.
Как и для предыдущей задачи для доказательства правильности работы алгоритма используем метод математической индукции. Глубина стека ≈ n, число ходов 2n-1.