W Cat - Описание языка PascalABC.NET

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

При формировании нового дерева будем использовать рекурсивную функцию CreateNode(P). Параметр P содержит указатель на вершину исходного дерева, копия которой создается при вызове функции. Возвращаемым значением функции является указатель на созданную вершину (как обычно, если P = nil, то функция не выполняет никаких действий и возвращает nil). Для создания дочерних вершин выполняется рекурсивный вызов этой функции. Заметим, что цепочка дочерних вершин может быть пустой (если вершина P является листом), содержать один элемент (если вершина P имеет только одного непосредственного потомка) или два элемента. Перед формированием цепочки дочерних вершин удобно занести адреса дочерних вершин вершины P во вспомогательные переменные P1 и P2. При этом в случае, если вершина P имеет только одного потомка (неважно, левого или правого), адрес этого потомка заносится в переменную P1, а переменная P2 остается равной nil. Благодаря использованию переменных P1 и P2, фрагмент кода, отвечающий за формирование списка дочерних вершин, удается сделать более кратким. Приведем текст программы, решающей задачу Tree86.

usesPT4;

functionCreateNode(P: PNode): PNode;

varP1, P2: PNode;

begin

ifP = nil then

begin

result := nil;

exit;

end;

New(result);

result^.Data := P^.Data;

result^.Right := nil;

P1 := P^.Left;

P2 := P^.Right;

ifP1 = nil then

begin

P1 := P2;

P2 := nil;

end;

{ формирование списка дочерних вершин }

result^.Left := CreateNode(P1);

ifP1 <> nil then

result^.Left^.Right := CreateNode(P2);

end;

varP1: PNode;

begin

Task('Tree86');

read(P1);

write(CreateNode(P1));

end.

Примечание.Фрагмент дерева общего вида, содержащий все дочерние вершины некоторой вершины, можно рассматривать как односвязный список , элементы которого связаны между собой с помощью поля Right (у последнего элемента списка поле Right равно nil). Каждый элемент подобного списка может содержать подсписок" своих дочерних элементов; адрес начала этого подсписка хранится в поле Left данного элемента. Поэтому в алгоритмах, связанных с обработкой вершин деревьев общего вида, для перебора непосредственных потомков некоторой вершины удобно использовать цикл (как при переборе элементов списка), в то время как для обработки каждой дочерней вершины следует, как обычно, использовать рекурсию .

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

ExamBegin2°. На вход подаются три вещественных числа; числа расположены в одной строке. Вывести вначале минимальное, а затем максимальное из них. Каждое число должно выводиться на новой строке и снабжаться комментарием: «MIN=" для минимального, «MAX=" для максимального.

Напомним, что программу-заготовку для решения этого задания можно создать с помощью команды меню Модули | Создать шаблон программы", кнопки или клавиатурной комбинации Shift+Ctrl+L. Приведем текст созданной заготовки:

usesPT4Exam;

begin

Task('ExamBegin2');

end.

После запуска программы на экране появится окно задачника:

Обсудим особенности программы-заготовки и окна задачника.

В программе-заготовке вместо модуля PT4 подключается модуль PT4Exam, специально предназначенный для использования при выполнении заданий групп Exam. Данный модуль содержит реализацию единственной процедуры Task, инициализирующей задание. Никакие дополнительные процедуры, связанные с вводом-выводом, в него не включены. Это обусловлено тем, что ввод-вывод при выполнении заданий групп Exam надо выполнять, используя стандартные процедуры языка Pascal .

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

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

Примечание.Если вы уже выполняли задания, связанные с обработкой файлов, то можете заметить, что отображение данных в заданиях групп Exam в точности соответствует способу отображения содержимого текстовых файлов . Это совпадение не случайно. На самом деле во всех заданиях групп Exam все исходные данные хранятся в специальном входном текстовом файле, а все результаты должны записываться в специальный выходной текстовый файл. Однако при этом не требуется выполнять особых действий, связанных с определением имен этих файлов, связыванием файлов с файловыми переменными, открытием и закрытием файлов (все эти действия выполняются задачником автоматически). Для программы, выполняющей задание, эти файлы играют роль стандартных потоков ввода-вывода , поэтому для доступа к ним достаточно использовать обычные процедуры ввода-вывода языка Pascal.