14. Абстрактный тип данных «стек». Реализация стека с помощью указателей. Привести пример.

Спец. тип списка(LIFO), в котором все операции выполняются на одном конце, называемом вершиной.Значение указателя стека – ссылка на вершину. Каждыфй эл-т содержит ссылку на следующий.

Описание:type

pt=^elem;

elem=record

data:integer;

next:pt;

end;

procedure writestack(var u:pt;dig:integer);

var

x:pt;

begin

new(x);

x^.data:=dig;

x^.next:=u;

u:=x;

end;

u-ссылка на стек;dig-записыв. значение.

procedure readstack(var u:pt; var dig:integer);

var

x:pt;

begin

dig:=u^.data;

x:=u;

u:=u^.next;

dispose(x);

end;

В результате процедуры переменной будет присвоено значение первого элемента и изменена ссылка на вершину стека.

15. Особенности итерационного вычислительного процесса. Структура (шаги) итерационного процесса

Итер. вычисл. процесс - циклический процесс, который продолжается до тех пор, пока разность между уточняем. на каждом шаге значениями не окажется <=задан. величине. Итер. процесс применяется при численных методах.

Особенности:1)неизвестно заранее кол-во повторений.

2)Результаты текущего шага используются при выполнении следующего.

Этапы:1)задание нач. значений.

2)подг. этап.

3)Реализация вычислений

4)подготовка след. итерации.

5)вычисление погрешности

6)условие окончания итераций. возврат к 3)

16. Особенности и определение рекурсивного вычислительного процесса. Привести пример использования рекурсии и стека.

Объект назыв. рекурсивным, если он содержит сам себя или определён с помощью самого себя. Мощь рекурсии в том, что она позволяет определить бесконечное мн-во объектов конечным высказыванием.Лучше использовать рекурсию, когда задача или обрабатываемая структ. определена рекурсивно или для неё сложно использовать итерации.

Если P содержит обращение к себе – прямая рекурсия. Если Р обращается к Q, которая обращается к Р – косвенная рекурсия.

При каждом обращении создаётся новое мн-во лок. переем., имеющих те же имена, что и при предыд. обращ., но отличающихся значениями. Рекурсия может приводить к бесконечн. вычислениям. Необходимо, чтобы условие входа в рекурсию в опред. момент переставало выполняться.

program recurs;

Var

N:integer;

F:longint;

function fakt(N:integer):longint;

begin

if N=1 then fakt:=1

else fakt:=N*fakt(N-1);

end;

begin

Readln(N);

Writeln(Fakt(N));

end;

Отложенные вызовы заносятся в стек.

17.Постфиксная, префиксная, инфиксная записи представления выражений и их особенности

3 формы записи:

1)А+В-инфиксная.

2)+АВ-префиксная(польская)

3)АВ+-постфиксная(обр. польская)

Метод польской записи создан при исследовании трансляции Яном Лукасевичем..Для преобразования в префиксн. используются приоритеты.Высший учитыв. первым. После вычислений результат-один операнд.Вычисления – слева направо, кроме возведения в степень.

Сцщность польской записи – в отсутствии скобок и порядке знаков, который соответствует порядку действий слева направо. Любое выражение можно вычислить за один проход.Для преобразований использ. стек. Ранг результата должен равняться 1.

1)В стек помещается символ пустого стека.

2)Приоритет входного символа сравнивается с пиоритетом верхнего эл-та стека.

3)Если приоритет входного >, то символ заносится в стек, иначе верхний выталкивается из стека. Сравнение происходит снова.

При каждом добавлении в префиксн. запись модифицир. ранг.

+,- 1

*,/ 2

a..z 3

Дно стека 0

При преобразовании инфиксного в польское порядок переменных не меняется,порядок операторов меняется отн-но приоритета.