- •Логические данные
- •Символьные данные
- •Хранение текста
- •Арифметические данные
- •Данные с фиксированной точкой
- •1111111101000111(2) - Инвертируем биты - 0000000010111000(2)
- •Данные с плавающей точкой
- •Простейшие приемы анализа погрешностей.
- •Методы оптимизации
- •Данные системы Turbo Pascal
- •Способы вычисления логических операций
- •Подпрограммы и их параметры
- •Способы передачи параметров
- •Структурное программирование, управляющие конструкции, пошаговая детализация.
- •Рекурсия и итерация
- •Метод итераций (повторений)
- •Метод инварианта цикла.
- •Метод инвариантной функции.
- •Метод индуктивной функции.
- •Защитное программирование
- •Абстрактные типы данных
- •Использование объектных средств
- •Динамические структуры данных
- •Языки и грамматики
- •Расширение нотации Бэкуса-Наура.
- •Интерпретатор математических формул, реализованный на основе метода Дейкстры.
- •Абстрактные структуры данных.
- •Часть 2 Последовательность.
- •Динамический вектор.
- •Множество
- •Нагруженное множество
- •Итераторы.
Рекурсия и итерация
Рекурсией —называется ситуация, когда программа вызывает сама себя непосредственно или косвенно (через другие функции).
Явный вызов.
Косвенный вызов. А вызывает В, В вызывает А, обе функции рекурсивны.
Обычный вызов означает, что в тот момент когда вызывается некоторая программа, следует остановка основной программы, запоминание точки вызова, затем выделяется память для подпрограммы. Все поочередно-вызываемые подпрограммы образуют структуру-стек, то же самое происходит и с данными, таким образом затраты на память связаны с глубиной стека.
Рекурсивная задача в общем случае разбивается на ряд этапов. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи — так называемую базовую задачу (или несколько таких задач). Если функция вызывается для решения базовой задачи, она просто возвращает результат. Если функция вызывается для решения более сложной задачи, то она делит эту задачу на две части: одну часть, которую функция решать умеет, и ту которую решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но по сравнению с ней проще или несколько меньше. Поскольку новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой — это называется рекурсивным вызовом или шагом рекурсии. Шаг рекурсии выполняется до тех пор, пока исходное обращение функции еще не закрыто. Шаг рекурсии может приводить к большому числу таких рекурсивных вызовов, поскольку функция продолжает деление каждой новой подзадачи на две части.
Задача: написать подпрограмму решения уравнения 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.