Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Пример программы с обходами деревьев




Читайте также:
  1. C2 Покажите на трех примерах наличие многопартийной политической системы в современной России.
  2. C2 Раскройте на трех примерах научный вывод о том, что социальные условия влияют на характер и форму удовлетворения первичных (биологических, витальных) потребностей.
  3. II. Основные цели и задачи Программы, срок и этапы ее реализации, целевые индикаторы и показатели
  4. II. Примеры проективных методик
  5. III. Примеры решения задач.
  6. III. Примеры решения задач.
  7. III. Примеры решения задач.
  8. IV. Примеры решения задач.
  9. IV. Примеры решения задач.
  10. IV. Примеры решения задач.

 

В качестве примера рассмотрим задачу выбора элемента максимального веса (стоимости) на И-ИЛИ дереве. Дадим сначала необходимые пояснения.

Многие объекты сложной природы удобно представлять с помощью И-ИЛИ графов и в частности И-ИЛИ деревьев. Таким способом кодируется, например, множество изделий некоторого класса технических объектов. И-ИЛИ деревом называется такое дерево, все вершины которого, не являющиеся листьями, разбиваются на два класса: И-вершины и ИЛИ-вершины. Элементами И-ИЛИ дерева считаются поддеревья специального вида. Поддерево R некоторого И-ИЛИ дерева является его элементом, если оно обладает следующими свойствами:

· R содержит корень дерева;

· если R включает некоторую И-вершину, то вместе с ней в R входят все сыновья данной вершины;

· если R включает некоторую ИЛИ-вершину, то вместе с ней в R входит ровно один сын данной вершины.

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

С помощью И-ИЛИ дерева можно представить множество изделий. В этом дереве некоторая вершина V будет И-вершиной, если любое изделие содержит все узлы, соответствующие сыновьям вершины V. Если же в изделие входит только один сын вершины V, то V будет ИЛИ-вершиной.

Например, опишем в упрощенном виде представление с помощью И-ИЛИ дерева множества велосипедов. Корень И-ИЛИ дерева имеет название "велосипед". Каждый велосипед содержит раму, руль, седло и колеса, поэтому корень дерева является И-вершиной. Рассмотрим сына корневой вершины, соответствующего раме. Пусть рамы могут быть таких типов, как "мужская", "женская", "разборная". Отдельный велосипед имеет определенный тип рамы, поэтому вершина дерева, соответствующая раме, является ИЛИ-вершиной. Если каждая разборная рама имеет одинаковые составляющие части, то вершина дерева с названием "разборная рама" будет И-вершиной.

Аналогично рассматривая другие узлы велосипеда, можно построить все И-ИЛИ дерево. Элементы данного дерева будут описывать отдельные типы велосипедов.



Рассмотрим следующую задачу. Задано И-ИЛИ дерево, соответствующее некоторому множеству изделий. В вершинах дерева в баллах от 0 до 15 даны экспертные оценки новизны узлов. Новизна изделия определяется как сумма оценок новизны всех вершин соответствующего элемента. Требуется:

· обеспечить ввод И-ИЛИ дерева с клавиатуры;

· найти элемент с максимальной новизной.

Опишем укрупненно алгоритм решения задачи.

1. Ввод И-ИЛИ дерева в порядке сверху вниз.

2. Расчет для каждой вершины в порядке обхода снизу вверх максимальной оценки новизны среди элементов поддерева, висящего на данной вершине. Выбор для каждой ИЛИ вершины сына с максимальной оценкой новизны и простановка признаков запрета для других сыновей.

3. Печать в порядке сверху вниз незапрещенных вершин дерева.

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

Program Tree;

Uses Crt;

Type

ukaz=^uzel;

uzel=record { информация о вершине дерева }



Pr: char; { вид вершины: 'a'-И, 'o'-ИЛИ, 'l'-лист }

Name: string; { название }

Nov: 0..15; { баллы новизны }

Left, Right: ukaz; { левый и правый сыновья бинарного дерева }

SumNov: integer;

{ максимальная суммарная новизна среди элементов }

{ поддерева, висящего на данной вершине }

Zapret: char { признак запрета: 'z'-есть,'r'-нет }

end;

Var

Prizn: char;

M, K: integer;

Kon, Root, Rab: ukaz;

Namer: string;

Procedure Sozd(T: ukaz); { ввод И-ИЛИ дерева }

Begin

if T<>Nil then

begin

Write('Введите название ');

ReadLn(T^.Name);

Write('Введите показатель новизны ');

ReadLn(T^.Nov);

T^.SumNov:=0;

T^.Zapret:='r'; { пока все разрешено }

Write('Вершина ', T^.Name, ' лист дерева(д/н) ? ');

ReadLn(Prizn);

if Prizn='д' then { лист }

begin

T^.Left:=Nil;

T^.Pr:='l'

end

else { не лист }

begin

Write('Это ИЛИ-вершина (д/н) ? ');

ReadLn(Prizn);

if Prizn='д' then T^.Pr:='o'

else T^.Pr:='a';

WriteLn('Переходим к левому сыну вершины ', T^.Name);

New(Kon);

T^.Left:=Kon

end;

Sozd(T^.Left);

if T=Root then

begin

T^.Right:=Nil;

Exit { правого соседа корня не может быть }

end;

Write('У вершины ', T^.Name, ’ имеются правые соседи(д/н) ? ');

Readln(Prizn);

if Prizn='н' then T^.Right:=Nil

{ 'н'-признак отсутствия соседей }

else

begin

WriteLn('Переходим к правому соседу вершины ', T^.Name);

New(Kon);

T^.Right:=Kon;

end;

Sozd(T^.Right)

end

End;

Procedure Rasch(T: ukaz); { см. п.2 алгоритма }

Begin

if T<>Nil then

Begin

Rasch(T^.Left);

Rasch(T^.Right);

if T^.Left<>Nil then { не лист }

if T^.Pr='a' then { И-вершина }



begin

Kon:=T^.Left;

While Kon<>Nil do

begin

T^.SumNov:=T^.SumNov+Kon^.SumNov;

Kon:=Kon^.Right

end

end

else { ИЛИ-вершина }

begin

Kon:=T^.Left;

M:=-1;

While Kon<>Nil do

begin

Kon^.Zapret:='z'; { сначала запрет }

if Kon^.SumNov>M then

begin

M:=Kon^.SumNov;

Rab:=Kon

end;

Kon:=Kon^.Right { следующий сын }

end;

T^.SumNov:=M;

Rab^.Zapret:='r'; { оставили лучшую вершину }

end;

T^.SumNov:=T^.SumNov+T^.nov; { учет возможной оценки отца }

end

End;

Procedure Pech(T: ukaz);

{ печать сверху вниз лучшего (незапрещенного) элемента }

Begin

if T <> Nil then

begin

if T^.Pr='a' then Namer:=' (И-вершина) '

else if T^.Pr='o' then Namer:=' (ИЛИ-вершина) '

else Namer:=' (лист дерева) ';

if T^.Zapret<>'z' then

begin

Write(T^.Name,Namer);

WriteLn(' оценка новизны - ', T^.SumNov);

end;

Pech(T^.Left);

Pech(T^.Right)

end

End;

Begin

ClrScr;

New(Root);

Sozd(Root);

WriteLn('Дерево создано !');

ReadLn; { пауза }

Rasch(Root);

WriteLn('Расчет проведен !');

ReadLn;

WriteLn('Лучший элемент !');

Pech(Root);

ReadLn

End.

 

 

Графы


Дата добавления: 2015-01-29; просмотров: 7; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.021 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты