- •Рекурсия. Виды. Особенности.
- •Прямая Рекурсия. Рекурсивное определение значение факториала
- •Косвенная Рекурсия. Опережающее описание.
- •Сортировка массивов. Типы сортировок.
- •Метод прямого обмена ..Пузырька
- •Метод прямого выбора:
- •Метод прямого включения
- •Алгоритмы поиска. Линейный поиск
- •Алгоритмы поиска. Поиск делением пополам
- •Статические и динамические переменные.
- •Указатели. Типы.
- •Доступ к переменной по указателю - разыменование указателя
- •Стандартные процедуры и функции управления динамической памятью
- •Динамические структуры данных: стек, очередь, список и их особенности.
- •Список. Типы списков. Операции над списками.
- •Выбор нового текущего элемента в списке.
- •Вывод всех элементов из списка.
- •Добавление нового элемента справа от текущего в списке.
- •Удаление текущего элемента из списка
- •Список.Удаление элемента справа от текущего.
- •Стек. Операции над стеком.
Рекурсия. Виды. Особенности.
это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.
Рекурсия бывает: прямой и косвенной
Прямая – процедура обращается сама к себе
Косвенная -вызов процедуры может содержаться в теле другой процедуры, к которой производится обращение
(+) выглядит изящнее и более компактный текст программы,
(-) но выполняется медленнее и может вызвать переполнение стека (при каждом входе в подпрограмму ее локальные переменные размещаются в области памяти, называемой стеком).
Прямая Рекурсия. Рекурсивное определение значение факториала
Прямая – процедура обращается сама к себе
{ factorial n! - rekurcia}
Var s:longint; n: word;
function f (n:word): longint;
begin
if (n=1) or (n=0) then f:=1
else f:=n*f(n-1);
end;
Косвенная Рекурсия. Опережающее описание.
Косвенная -вызов процедуры может содержаться в теле другой процедуры, к которой производится обращение из данной процедуры.
Procedure A(i : Byte);
begin
В(i);
end;
Procedure В(j: Byte);
begin
A(j);
end;
Так как каждый идентификатор перед употреблением должен быть описан, то такую программную конструкцию использовать нельзя. Для разрешения этого вопроса вводится опережающее описание:
Procedure В(j: Byte); Forward;
Procedure A (i: Byte);
begin
В(i);
end;
Procedure B;
Begin A(j); end;
Сортировка массивов. Типы сортировок.
Под сортировкой понимается процесс перегруппировки элементов массива, приводящий к их упорядоченному расположению относительно ключа.
Цель сортировки — облегчить последующий поиск элементов.
Метод сортировки называется устойчивым, если в процессе перегруппировки относительное расположение элементов с равными ключами не изменяется. Основное условие при сортировке массивов — это не вводить дополнительных массивов, т.е. все перестановки элементов должны выполняться «на том же месте» в исходном массиве. Сортировку массивов принято называть внутренней в отличие от сортировки файлов (списков), которую называют внешней.
Методы внутренней сортировки классифицируются по времени их работы. Хорошей мерой эффективности может быть число сравнений ключей — С и число пересылок элементов — Р. Эти числа являются функциями С(n), Р(n) от числа сортируемых элементов n. Быстрые (но сложные) алгоритмы сортировки требуют (при n→∞) порядка n log n сравнений, прямые (простые) методы — n2.
Прямые методы коротки, просто программируются; быстрые усложненные методы требуют меньшего числа операций, но эти операции обычно сами более сложны, чем операции прямых методов. Поэтому для достаточно малых n (n ≤ 50) прямые методы работают быстрее. Значительное преимущество быстрых методов (в n/log(n) раз) начинает проявляться при n ≥ ~ 100.
Метод прямого выбора;
Метод прямого обмена (пузырьковая сортировка);
Сортировка с помощью прямого (двоичного) включения;
Шейкерная сортировка (модификация пузырьковой).