Учебные материалы к элективным курсам по информатике дляклассов, выпуск 1 (стр. 4 )

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

Типичным примером двоичного дерева является генеалогическое дерево, в котором узлом является человек, а ветви связывают его с его собственными родителями. Получается структура: человек, затем его отец и мать, родители отца и родители матери, родители родителей и так далее. Пример такого дерева приведен на рисунке.

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

Применение двоичных деревьев, не ограничивается генеалогией. К примеру, рассмотрим арифметическое выражение 2*2+11/2. Это выражение определяет, какие действия надо выполнить с операндами, а правила арифметики устанавливают порядок их выполнения. Каждой операции соответствует два операнда, а результат выполнения операции будет использован в качестве операнда в следующем вычислении или окажется окончательным – равным значению выражения. Для нашего выражения можно построить двоичное дерево аналогичное генеалогическому:

По мере вычислений происходит преобразование (сокращение) дерева.

В скобках указан порядковый номер действия.

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

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

Решение. Задачу следует разбить на две части. Сначала построим двоичное дерево, соответствующее выражению, затем произведем вычисление значения.

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

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

Программа, реализующая этот алгоритм, приведена ниже.

Программа	Комментарии
program plusminus;
type
ukaz=^uzel;	Описание типа указателя на узел дерева
uzel=record	Описание типа узла дерева
inf:string[16];	Информационное поле
ukl, ukr:ukaz	Указатели на левый и правый следующие узлы
end;
var
a:ukaz;	Статическая переменная – указатель на корень
s:string;	Входная строка
i:integer;
y:real;
procedure stroim(st:string; var u:ukaz);	Процедура построения дерева
var
i:integer;
begin
if (pos('-',st)=0)and(pos('+',st)=0) then	Если в строке нет символов операций
begin
u^.inf:=st;	Информационное поле равно параметру st
u^.ukl:=nil;	Указатель на следующий nil – узел является
u^.ukr:=nil	вершиной дерева
end
else
begin
i:=length(st);	Начиная с последнего символа
while (st[i]<>'+')and(st[i]<>'-') do	ищем знак операции
i:=i-1;
u^.inf:=st[i];	Знак операции в информационное поле
new(u^.ukl);	Новый левый узел
new(u^.ukr);	Новый правый узел
stroim(copy(st,1,i-1),u^.ukl);	Строим левую ветвь
stroim(copy(st, i+1,length(st)-i),u^.ukr)	Строим правую ветвь
end
end;
function shet(u:ukaz):real;	Функция вычисления результата
begin
if u^.ukl=nil then	Если узел является вершиной
begin
val(u^.inf, y,i);	Преобразуем строку в число
shet:=y	Результат число
end
else	Иначе
case u^.inf[1] of	Если операция
'+': shet:=shet(u^.ukl)+shet(u^.ukr);	+, то результат сумма левого и правого
'-': shet:=shet(u^.ukl)-shet(u^.ukr)	-, то результат разность левого и правого
end
end;
begin
readln(s);	Вводим строку
new(a);	Создаем корень дерева
stroim(s, a);	Строим дерева
writeln(shet(a):15:5)	Печать значения функции
end.

Файлы

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

Под файлом будем понимать специально организованную специфицированную структуру данных на внешнем устройстве.

Для управления файлами определяются специальные переменные файлового типа.

· Текстовые

<имя файловой переменной>:text;

· Типизированные

<имя файловой переменной>:file of <имя базового типа>;

· Не типизированные

<имя файловой переменной>:file;

· Отождествление файловой переменной с физическим файлом производится процедурой

assign(<имя файловой переменной>,<спецификация файла>).

· Открытие файла производится процедурами

reset(<имя файловой переменной>) для чтения

rewrite(<имя файловой переменной>) для записи.

· Чтение данных из файла производится процедурами

read(<имя файловой переменной>,<список ввода>)

readln(<имя файловой переменной>,<список ввода>) – только для чтения из текстового файла.

· Запись данных в файл производится процедурами

write(<имя файловой переменной>,<список вывода>)

writeln(<имя файловой переменной>,<список вывода>) – только для записи в текстовый файл.

· Функция eof(<имя файловой переменной>) имеет значение "истина" если достигается конец файла и "ложь" в противном случае.

· Закрытие файла производиться процедурой close(<имя файловой переменной>).

Общий порядок работы с файлами

1. Если необходимо описывается нестандартный файловый тип.

2. Описываются переменные файлового типа.

3. Выполняется отождествление файловой переменной с физическим файлом процедурой assign.

4. Файл открывается процедурами rewrite или reset для записи или для чтения данных.

5. Выполняется чтение или запись данных в файл.

6. Файл закрывается процедурой close.

Задачи

1. Используйте алгоритм построения сортированного списка для решения задачи сортировки файла с помощью трех лент.

2. Решите задачу – считалку. Параметры: входной файл содержит количество слов считалки и список имен. Результат – список участников в порядке выбывания.

3. Решите задачу о расстановке быков на корабле. Быков ставят в круг и выбрасывают за борт каждого k-того. Входные данные: количество ваших быков; количество чужих быков; количество быков, которых следует выбросить за борт, число k. Результат: номера позиций, на которые не следует ставить ваших быков.

4. Напишите программу считалка-маятник. Используйте двусвязный список.

5. Напишите программу – калькулятор для вычисления выражений с операциями умножения и деления.

6. Дополните программу калькулятор обработкой скобок, использованных при составлении арифметических выражений.

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

Дополнительные задачи

Задача 1. Даны чашечные весы и разновес, состоящий из N гирь. Вес каждой гири Mi, i=1,2,..,N. На правой чаше весов установлен груз весом P. Найти такой набор гирь, если он существует, который, при установке на левую чашу весов, уравновешивал бы весы.

Задача 2. Пусть гири из разновеса можно устанавливать на обе чаши весов. Необходимо найти наборы гирь из разновеса, которые при установке на правую (где находится груз) и на левую (пустую) чаши весов приводили бы весы в состояние равновесия.

Задача 3. Напишите программу, которая бы печатала все возможные разбиения множества из N элементов на K непересекающихся подмножеств.

Задача 4. Даны две емкости A и B литров соответственно. Имеется водопроводный кран и раковина (для выливания воды не на пол, а чтобы сухо было). Можно переливать воду из одной емкости в другую и наоборот, наполнять и опустошать каждую емкость. Необходимо найти такую последовательность, если она есть, названных действий, не превышающую N операций, в результате выполнения которой в одной из емкостей было бы отмерено ровно C литров.

Задача 5. В пивном баре работает вороватый бармен, имеющий остатки совести. Для получения "левого" дохода он разбавляет пиво. Однако совесть ему не позволяет разбавлять пиво более чем на одну четверть. В баре имеются краны с пивом и водой, раковина и две емкости (A и B миллилитров соответственно).

Написать программу, которая позволяет найти последовательность переливаний для того чтобы отмерять в одной из емкостей С миллилитров пива разбавленного не более чем на четверть, если это возможно менее чем за 10 операций. Ограничения: пиво в раковину выливать нельзя, разбавленное пиво выливать обратно в бочку тоже нельзя. Если последовательность найти не удалось, то выдавайте сообщение: "Лучше обсчитай!"

Задача 6. В математическом ночном клубе проводится лотерея входных билетов. Билет считается выигрышным, если сумма цифр его N - разрядного номера является простым числом. Простое число такое, которое делится без остатка только на 1 и на само себя. Найти номера всех выигрышных билетов.

[1] Различные способы адресации памяти будут рассмотрены ниже

[2] Для иллюстрации способов адресации памяти не будем обращаться к конкретным типам процессоров и соответствующих им ассемблерам, вместо имен регистров будем указывать номера в круглых скобках