Рекурсивная Сортировка Слиянием

(для любопытных)

Задача. Напишите программу, содержащую алгоритм слияния в процедуре Sort(A, B, b1, e1, e2). Алгоритм должен копировать со слиянием два упорядоченные куска из массива А с номерами от b1 до e1 и от e1+1 до e2 соответственно в массив В с номерами элементов от b1 до e2.

Предположив, что Вы правильно выполнили предыдущую задачу, алгоритм сортировки можно определить очень просто:

1) если длина сортируемого массива 1, то ничего не делается;

2) в противном случае массив делится на две одинаковые (или почти одинаковые) части, к каждой части применяется алгоритм сортировки, после чего эти упорядоченные части сливаются в один упорядоченный кусок.

Рассмотрите процедуру сортировки слиянием. На вход процедуры сортировки поступает неупорядоченный кусок массива А с номерами элементов от b до e, на выходе – тот же кусок, но упорядоченный. Массив С – вспомогательный.

Procedure Sort2(Var A, C: Array1; b, e: integer);

Var

i, d: integer;

Begin

if b<e

then

begin

d:= (b+e) div 2;

Sort2(A, C, b, d);

Sort2(A, C, d+1, e);

Sort(A, C, b, d, e);

for i:= b to e do

A[i]:= C[i]

end;

End;

 

Занятие V-VI Тема. Самостоятельное решение задач. Задание. Выберите с учителем задачи для решения из предложенного ниже перечня. 1. В массиве X(N) каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все единицы, затем все двойки и, наконец, все нули (дополнительного массива не заводить). 2. В заданной последовательности все элементы, не равные нулю, расположить сохраняя их порядок следования, в начале последовательности, а нулевые элементы - в конце последовательности. Дополнительного массива не заводить. 3. Отсортировать массив по возрастанию, используя процедуру Swap, которая меняет местами 2 элемента. 4. Составьте алгоритм, упорядочивающий элементы массива, стоящие на нечетных местах, в возрастающем порядке, а на четных - в убывающем. 5. Из двух упорядоченных одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N, упорядоченный так же, как исходные массивы. 6. Из двух упорядоченных одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N, упорядоченный в обратную сторону. 7. Составьте алгоритм, упорядочивающий заданную последовательность чисел так, чтобы каждый элемент, стоящий на четном месте, был больше каждого из соседних. 8. Дан упорядоченный целочисленный массив. Сформировать второй массив всех таких различных значений, которые в первом массиве встречаются по два и более раза. 9. Дан упорядоченный целочисленный массив. Сформировать второй массив всех таких различных чисел, которые ни разу в первом массиве не встречаются и имеют величину больше минимального и меньше максимального из чисел первого массива. 10. Дана вещественная матрица размером 7x4. Переставляя ее строки и столбцы, добиться того, чтобы наибольший элемент (один из них) оказался в левом верхнем углу. 11*. В заданном целочисленном массиве найти элементы, сумма которых равна данному числу, в предположении, что такие числа существуют. 12. Дан массив А, состоящий из n элементов. Осуществить перестановку элементов массива на M элементов вправо. 13. В двумерном массиве поменяйте местами первую строчку, и строчку в которой находится первый нулевой элемент. 14. В двумерном массиве переставьте строки следующим образом: первую с последней, вторую с предпоследней и так далее. Если строк нечетное число, то средняя остается неизмененной. 15. Дан двумерный массив А. Расставить его столбцы в следующем порядке: а) последний, предпоследний,..., второй, первый; б) первый, последний, второй, предпоследний, третий,... 16. Дан двумерный массив. Начиная с первой строки, сдвинуть все строки на две вниз, а последние перенести на место первых двух строк. 17. Дан двумерный массив вещественных чисел размерностью [1..N,1..N]. Произвести сортировку столбцов по убыванию элементов последней строки. Вычислить сумму элементов расположенных на диагоналях полученной матрицы. Сортировку произвести методом прямого выбора. Вывести на экран исходный и полученный массивы в виде матрицы. 18. Дан двумерный массив вещественных чисел размерностью [1..N,1..N]. Произвести сортировку столбцов по возрастанию элементов первой строки. Вычислить среднее арифметическое элементов расположенных по периметру полученной матрицы. Сортировку произвести методом прямого выбора. Вывести на экран исходный и полученный массивы в виде матрицы. 19. Дан двумерный массив, содержащий 4 строки и 5 столбцов. Элементами массива являются целые числа. Упорядочить массив по возрастанию элементов 3-го столбца. 20. Дан двумерный массив, содержащий 4 строки и 5 столбцов. Элементами массива являются целые числа. Упорядочить массив по убыванию элементов 2-й строки. Приготовьте рабочие программы и листинги с задачами этой темы.

 

 

Деревья

 

Занятие I

Тема. Основные понятия.

Граф – это непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек.

Если на каждом ребре задать направление, то граф будет ориентированным.

 

Если, двигаясь по ребрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путем.

Замкнутый путь, состоящий из различных ребер, называется циклом.

Граф называется связным, если любые две его вершины соединены путем.

 

Связный граф без циклов называется деревом.

Связный граф без циклов называется деревом.

С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями.

Рассмотрите пример дерева, в узлах которого располагаются символы.

Для дальнейшей работы с деревьями необходимо определить ряд понятий.

• Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у.

• Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.

• Количество непосредственных потомков внутренней вершины называется ее степенью.

• Степенью дерева называется максимальная степень всех вершин.

Например,

• вершины F, D, E являются непосредственными потомками вершины В;

• вершины F, D, E являются листьями;

• вершины C, G, H – внутренние;

• степень вершины В – 3, а вершины Н – 1;

• степень дерева равна 3.

Определение. Двоичное дерево – это дерево, в котором из каждой вершины исходит не более двух ребер.

Задание. Наберите текст программы на компьютере и рассмотрите ее действие. Данная программа демонстрирует создание произвольного двоичного дерева.

Program DemidenkoS;

Uses

Crt, Graph;

Const

Arr: array [1..6] of integer=(160,80,40,20,10,5);

Arr1: array [1..6] of integer=(120,80,70,60,50,40);

Type

ss=^sp;

sp=record

elem:byte;

Next: array[1..2] of ss;

end;

Var

a, b, c, d: longint;

s: string;

grDriver: integer;

grMode: integer;

a1, b1: real;

x, Some, Max, Min: ss;

Procedure Zap(y: ss; n: integer);

Var

aa,bb:integer;

Begin

y^.elem:=random(99)+1;

bb:=random(3);

if n<1

then

bb:=2;

if n<a

then

for aa: =1 to bb do

begin

new(y^.next[aa]);

y^.next[aa]^.next[1]:=nil;

y^.next[aa]^.next[2]:=nil;

zap(y^.next[aa],n+1);

end;

End;

Procedure Strel(x1, y1: integer; k: Real);

Var

aa: Real;

Begin

aa:=arctan(k);

if k>0

then

begin

line(x1,y1,x1+round(10*cos(aa+pi/18)),y1-round(10*sin(aa+pi/18)));

line(x1,y1,x1+round(10*cos(aa-pi/18)),y1-round(10*sin(aa-pi/18)));

line(x1+round(10*cos(aa+pi/18)),y1-round(10*sin(aa+pi/18)),x1+round(10*cos(aa-pi/18)),y1-round(10*sin(aa-pi/18)));

end

else

begin

aa:=-aa;

line(x1,y1,x1-round(10*cos(aa+pi/18)),y1-round(10*sin(aa+pi/18)));

line(x1,y1,x1-round(10*cos(aa-pi/18)),y1-round(10*sin(aa-pi/18)));

line(x1-round(10*cos(aa+pi/18)),y1-round(10*sin(aa+pi/18)),x1-round(10*cos(aa-pi/18)),y1-round(10*sin(aa-pi/18)));

end

end;

Procedure Wiv(y: ss; n, x1, y1: integer);

Var

spi: ss;

Begin

SetColor(n+1);

Circle(x1,y1,10);

Str(y^.elem, s);

if length(s)=2

then

OutTextXY(x1-6, y1-2, s)

else

OutTextXY(x1-3, y1-2, s);

if n<a

then

begin

if y^.next[1]<>nil

then

begin

SetColor(n+1);

Line(x1,y1+10,x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10);

SetColor(n+2);

Line(x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1-arr[n],y1+arr1[n]-10);

Strel(x1-arr[n],y1+arr1[n]-10,(arr1[n]-20)/arr[n]);

Wiv(y^.next[1],n+1,x1-arr[n],y1+arr1[n]);

end;

if y^.next[2] <> nil

then

begin

SetColor(n+1);

Line(x1,y1+10,x1+arr[n],y1+arr1[n]-10);

SetColor(n+2);

Line(x1+(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1+arr[n],y1+arr1[n]-10);

Strel(x1+arr[n],y1+arr1[n]-10,-(arr1[n]-20)/arr[n]);

Wiv(y^.next[2],n+1,x1+arr[n],y1+arr1[n]);

end;

end;

end;

Begin

ClrScr;

Randomize;

Repeat

new(x);

a:=6;

x^.next[1]:=Nil;

x^.next[2]:=Nil;

Zap(x,0);

Max:=x;

Min:=x;

writeln;

grDriver:= Detect;

InitGraph(grDriver, grMode,'c:\tp7\bgi\');

SetFillStyle(solidfill,15);

SetColor(15);

Wiv(x,1,320,50);

Delay(5000);

until KeyPressed;

End.

Задание. Поэкспериментируйте над предложенной программой, внося свои изменения. Результат покажите учителю.

 

Занятие II

Тема. Представление деревьев. Основные операции над деревом.

Дерево – это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.

Очевидно, что для описания требуются ссылки. Опишем, как переменные с фиксированной структурой – сами вершины, тогда степень дерева будет определять число ссылочных компонент, указывающих на вершины поддеревьев. В бинарном дереве их два: левое и правое.

Type

TreeLink = ^Tree;

Tree = Record

Data: <тип данных>;

Left, Right: TreeLink;

End;

Корень дерева опишем в разделе описания переменных:

Var

kd: TreeLink;

К основным операциям над деревьями относятся:

• занесение элемента в дерево;

• обход дерева;

• удаление элемента из дерева.

Рассмотрим вставку и обход дерева на примере следующей задачи.

Задача. Создать и вывести на экран дерево, элементы которого вводятся с клавиатуры и имеют целый тип. Причем для каждой вершины дерева во всех левых вершинах должны находиться числа меньшие, а в правой большие, чем числа, хранящиеся в этой вершине. Такое дерево называется деревом поиска.

Опишем процедуру вставки в дерево новой вершины. При вставке в дерево вершина вставляется либо как поддерево уже существующей вершины или как единственная вершина дерева. Поэтому и левая и правая связи новой вершины должны быть Nil. Когда дерево пусто, значение передаваемое в виде параметра ссылки равно Nil. В этом случае нужно изменить ее так, чтобы она указывала на новую вершину, которая была вставлена как корневая. При вставке второго элемента переданный из основной программы параметр t уже не будет равен Nil, и надо принимать решение о том, в какое поддерево необходимо вставить новую вершину.

Procedure InsTree(n: integer; Var t: TreeLink);

Begin

if t=nil

then

begin

new(t);

with t^ do

begin

Left:= nil;

Right:= nil;

Data:= n;

end;

end;

else

if n<=t^.data

then

InsTree(n, t^.Left)

else

InsTree(n, t^.Right)

End;

Опишем процедуру вывода значений элементов двоичного дерева на экран. Для этого необходимо выполнить полный обход дерева. При обходе дерева его отдельные вершины посещаются в отдельном порядке. Вывод двоичного дерева можно производить рекурсивно, выполняя для каждой вершины три действия:

• вывод числа, хранящегося в узле;

• обход левого поддерева;

• обход правого поддерева.

Порядок выполнения этих действий определяет способ обхода дерева. Способы вывода:

• прямой вывод (сверху вниз);

• обратный вывод (слева направо);

• концевой вывод (снизу вверх).

Процедура обратного вывода дерева имеет следующий вид:

Procedure PrintTree(t: TreeLink);

Begin

if t<>Nil

then

begin

PrintTree(t^.Left);

Write(t^.Data:3);

PrintTree(t^.Right);

end;

End;

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

Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная nd типа TreeLink – значение указателя на корень дерева; переменная Digit типа integer для хранения очередного введенного числа.

Begin

writeln('Вводите вершины дерева. Окончание ввода – 0');

kd:= nil;

read(Digit);

while Digit <> 0 do

begin

InsTree(Digit, kd);

writeln(' Введите очередное число ');

read(Digit);

end;

PrintTree(kd);

End.

Задание. Напишите программу создания и вывода на экран двоичного дерева, используя свою процедуру вывода. Протестируйте программу и представьте учителю файл и листинг для оценки.

 

Занятие III

Тема. Самостоятельное решение задач.

Выберите с учителем одну из предложенных задач.

1. Создайте программой числовое двоичное дерево. Опишите рекурсивную логическую функцию, проверяющую наличие заданного числа в сформированном дереве. В программе используйте подпрограммы.

2. Создайте программой числовое двоичное дерево. Опишите рекурсивную числовую функцию, подсчитывающую сумму элементов дерева. В программе используйте подпрограммы.

3. Создайте программой числовое двоичное дерево. Опишите функцию, которая находит наибольший элемент непустого дерева. В программе используйте подпрограммы.

4. Напишите программу, содержащую процедуру, которая каждый отрицательный элемент дерева заменяет на положительный, а положительный превращает в ноль.

5. Напишите программу, содержащую процедуру, которая каждый элемент дерева возводит в квадрат.

6. Создайте программой символьное двоичное дерево. Опишите функцию, возвращающую строку, сформированную на базе этих символов. В программе используйте подпрограммы.

7. Создайте программой символьное двоичное дерево. Опишите логическую функцию, проверяющую, есть ли в непустом дереве хотя бы два одинаковых символа. В программе используйте подпрограммы.

8. Создайте строковое двоичное дерево. Опишите функцию, возвращающую строку, сформированную на базе символов, встречающихся в каждой строке дерева. В программе используйте подпрограммы.

9. Создайте двоичное дерево записей. Проверьте выбранное поле записей на равенство. В программе используйте подпрограммы.

10. Создайте программой два числовых двоичных дерева. Опишите рекурсивно и нерекурсивно логическую функцию, входными параметрами которой являются два дерева, проверяющую на равенство эти деревья. В программе используйте подпрограммы.

 

Занятие IV

Тема. Идеально сбалансированное дерево.

В дереве поиска можно найти место каждого элемента, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значений встречающихся данных.

Использование деревьев поиска значительно сокращает время решения задачи.

Правильно организованным деревом считается идеально сбалансированное дерево, то есть для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.

Сформируем идеально сбалансированное дерево, элементами которого являются N чисел, вводимых с клавиатуры.

Поскольку требуется построить идеально сбалансированное дерево, то его узлы в процессе построения должны распределяться равномерно. Сформируем правило равномерного распределения узлов при известном их числе:

• Взять один узел в качестве корня.

• Построить левое поддерево с числом узлов n1=N div 2 тем же способом.

• Построить правое поддерево с числом узлов n2=N-n1-1 тем же способом.

Program BalansTree;

Uses

Crt;

Type

Pt = ^Node;

Node = record

Data: integer;

Left, Right: Pt;

end;

Var

n: integer;

kd: Pt;

f: text;

Function Tree(n: integer): Pt;

Var

NewNode: Pt;

x, n1, n2: integer;

Begin

if n=0

then

Tree:= Nil

else

begin

n1:= n Div 2;

n2:= n–n1–1;

read(f,x);

new(NewNode);

with NewNode^ do

begin

Data:= x;

Left:= Tree(n1);

Right:= Tree(n1);

end;

Tree:= NewNode;

end;

End;

Procedure PrintTree(t: Pt; h: integer);

Var

i: integer;

Begin

if t<>nil

then

with t^ do

begin

PrintTree(Left, h+1);

for i:= 1 to h do

write(' ');

writeln(Data:6);

PrintTree(Right, h+1);

end;

End;

Begin

ClrScr;

assign(f, 'c:\f.pas');

reset(f);

write('n=');

readln(n);

kd:= Tree(n);

PrintTree(kd, 0);

readln;

End.

Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип построения идеально сбалансированного дерева.