2. Задача №2.14
2.1. Постановка задачи и ее анализ
Проверить, являются ли элементы стека, реализованного массивом, членами арифметической прогрессии. Если являются – вывести шаг прогрессии, если нет – сообщение об этом.
2.2. Описание структур данных
type elem= array [1..100] of integer; //массив элементов
var size:integer; //число элементов pt,pt1:elem;
2.3. Проектирование программы
Рассмотрим подробнее процедуру, позволяющую определить, являются ли введённые числа членами арифметической прогрессии, и если да, то рассчитать шаг прогрессии. Её суть заключается в том, что мы берём 2 первых значения и находим их разницу. Потом берём третье число и тоже вычисляем разницу, и так далее:
procedure proverka;
var a1,a2,tmp:integer;
d,n,i:integer;
begin
a1:=pop(head); //извлекаем первое значение стека
a2:=pop(head); //извлекаем второе значение стека
d:=a2-a1; // находим шаг
tmp:=pop(head);
if tmp=polin(a1,d,3) then //проверяем третье число и сравниваем разность
writeln('Введённые Вами числа являются членами арифметической прогрессии с шагом',abs(d))
else
writeln('Введённые Вами числа не являются прогрессией’);
2.4. Результаты отладки и тестирования программы.
При запуске программы пользователю предлагается ввести количество записей и, непосредственно, сами числа (рис 2.1.):
Рис. 2.1. – Ввод данных
После чего программа выдаёт результат (Рис 2.2.):
Рис 2.2. – Результат
3. Задача №3.24
3.1. Постановка задачи и ее анализ
Описать процедуру, которая удаляет все листья бинарного дерева, попадающие в заданный диапазон значений.
3.2. Описание структур данных
Структура данных – бинарное дерево:
T=integer; //скрываем зависимость от конкретного типа данных
TTree=^TNode; //указатель на узел
TNode=record //Структура узла дерева
value:T; // это поле предназначено для хранения информации
Left, Right: TTree; // указатели на левого и правого сына
3.3. Проектирование программы
Для работы с бинарным деревом я реализовала следующие процедуры и функции:
*procedure Insert (рекурсивная процедура, вызывается при создании дерева)
*procedure Remove (осуществляет удаление узлов бинарного дерева)
*function Find (осуществляет поиск заданного элемента)
*procedure Delete (осуществляет уничтожение бинарного дерева)
*procedure LeafsCount (производит подсчёт числа «листьев»)
*function GetNode (осуществляет получение значения текущего элемента)
*procedure PrintDown (осуществляет прямой порядок прохождения)
*procedure PrintLex (осуществляет симметричный порядок прохождения)
*procedure PrintUp (осуществляет концевой порядок прохождения)
Само дерево я задала массивом iV: array[1 .. size] of Integer =(1,4,8,2,7,4,3,8,9,3);, значения которого легко изменить.
Рассмотрим подробнее процедуру Remove, в реализации которой и состояла моя основная задача:
procedure Remove(var Root: TTree; X: T);
Var WasNext: tTree;
begin
if Root<>nil then //если дерево не пустое
if X<Root^.value then //если значение Х меньше корня
remove(Root^.Left, X) //идём влево и удаляем все элементы со значением Х
else
if X>Root^.value then //если значение Х больше корня
remove(Root^.Right, X) //идём вправо и удаляем все элементы со значением Х
else
if (Root^.Left = nil) and (Root^.Right = nil) then
begin //нет сыновей, удаляем узел, на который указывает Root
Dispose(Root); //освобождаем выделенную Root память
Root:=nil
end
else
if Root^.Left=nil then //если у узла нет левого поддерева
begin
WasNext:= Root^.Right; //на это место ставим вершину его правого поддерева
Dispose(Root); //освобождаем память
Root:=WasNext;
end
else
if Root^.Right=nil then //если у узла нет правого поддерева
begin
WasNext:= Root^.Left; //на это место ставим вершину его левого поддерева
Dispose(Root); //освобождаем память
Root:= WasNext;
end
else
Root^.value:= DeleteMin(Root^.Right); // у удаляемого элемента есть оба сына
end;
Eсли у правого потомка удаляемого узла нет левого потомка, удаляемый узел заменяется на своего правого потомка, а его левый потомок подключается вместо отсутствующего левого потомка к замещающему узлу (рис. 3.1):
Рис. 3.1. – удаление узла
В общем же случае на место удаляемого узла ставится самый левый лист его правого поддерева (или наоборот – самый правый лист его левого поддерева). Корень дерева удаляется по общему правилу за исключением того, что заменяющий его узел не требуется присоединять к узлу-родителю.
Во время непосредственной реализации дерева мы запрашиваем у пользователя необходимый диапазон для удаления, и, использую процедуру Remove, удаляем листья, которые попадают в этот диапазон, и выводим новое дерево.
3.4. Результаты отладки и тестирования программы.
При запуске программы на экран выводится исходное дерево. Пользователю предлагается ввести необходимый диапазон, значения, попадающие в который, и будут удаляться (рис. 3.2):
Рис. 3.2. – Отображение исходных и входных данных на экране
После ввода необходимых данных, программа выводит на экран новое дерево, уже с удалёнными элементами (рис. 3.3):
Рис. 3.3. – Отображение результата на экране