Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [Pascal] задача на деревья


Автор: zirogo 22.5.2006, 14:32
Напишите программу, находящую величину наибольшего элемента дерева Т.

пожалуйста, кто может напишите код!!! 

Автор: zirogo 23.5.2006, 06:36
Please помогите!!! 

Автор: b44 24.5.2006, 05:56
по виду задача не сложная!!! может быть сделаю на выходных, просто щас время нет, сессия! 

Автор: sergejzr 26.5.2006, 12:51
Модератор: http://forum.vingrad.ru/index.php?showtopic=96391 

Автор: IgorStar 26.5.2006, 22:14
Если все равно на способ обхода, то для бинарного дерева рекурсивным способом как вариант:
Код

Type TTree=^TNode;
        TNode=record
            inf:integer;
            left,right:TTree;
          end;

var T:TTree;
     max:integer;

procedure Search_Max(var T:TTree;var elem:integer);
 begin
   if T<>nil
      then 
       begin
         if T^.inf>elem 
            then elem:=T^.inf;
        Search_Max(T^.right,elem);
        Search_Max(T^.left,elem);
       end;
 end;

begin{main program}
{создание или ввод дерева}
Max:=0;
Search_Max(T,max);
{получаешь max - максимальный элемент}
end;


Вроде должна работать, если че не так спрашивай

Автор: b44 27.5.2006, 07:10
подскажите как создать дерево! если не сложно опишите код! 

Автор: IgorStar 27.5.2006, 10:13
Какое дерево, дерево поиска что ли? 
 smile  

Автор: b44 27.5.2006, 13:42
Напишите программу, находящую величину наибольшего элемента дерева Т.

дерево Т надо водить или что, что бы он находил маским элемент 

Автор: Mechanic 27.5.2006, 16:42
Тут у тя бинарное дерево. Его нужно случайным образом заполнить?
Есть вариант (опять же рекурсивный):

Код

const Total_Nodes = 100;

{creates Node with Nodes nested childs}
procedure RandomFillTree(var Node: TTree; const Nodes: integer);
var Left, Right: integer;
begin
    //calc parts (Left, Right)
    Left := Random(Nodes+1);
    Right := Nodes - Left;
    New(Node);
    Node^.inf := Round(Random);
    Node^.Left := nil; Node^.Right := nil;
    RandomFillTree(Node^.Left, Left);
    RandomFillTree(Node^.Right, Right);
end;

var T: TTree;  MaxValue: integer;
begin
    // Fill tree
    RandomFillTree(T, Total_Nodes);
    // Search_Max
    Search_Max(T, MaxValue);
end;
 

Автор: b44 28.5.2006, 07:40
var Node: TTree; в этой части вылазиет ошибка "неопределеный идентификатор" подскажите как и где исправить! 

Автор: IgorStar 28.5.2006, 08:58
Цитата

var Node: TTree; в этой части вылазиет ошибка "неопределеный идентификатор" подскажите как и где исправить!

 
Ты строку с описание var помести перед процедурой,
то есть чтобы сначало шел раздел объявления типа а затем процедура, должно заработать, и опиши тип TTree 

Автор: Mechanic 28.5.2006, 12:54
Цитата(b44 @  28.5.2006,  07:40 Найти цитируемый пост)
var Node: TTree; в этой части вылазиет ошибка "неопределеный идентификатор" подскажите как и где исправить!

Чтоб не повторяться, я не писал в коде кусок кода от 
IgorStar, хотя его использование подразумевается.  smile 

Объявление типа TTree, и процедура Search_Max есть в его посте.
Полностью не привожу код, т.к. считаю, что мозгам всегда нужна хоть какая-нить тренеровка.  smile  

Автор: b44 28.5.2006, 13:51
подскажите это так? я просто плохо знаю Pascal, я не проходил тему типы и процедуры! пожалуйста исправте!
если можете сделайте вывод чисел на экран чтобы посмотреть как она работает! заранее спасибо!

Код

Type TTree=^TNode;
        TNode=record
            inf:integer;
            left,right:TTree;
          end;

var T:TTree;
     max:integer;

procedure Search_Max(var T:TTree;var elem:integer);
 begin
   if T<>nil
      then 
       begin
         if T^.inf>elem 
            then elem:=T^.inf;
        Search_Max(T^.right,elem);
        Search_Max(T^.left,elem);
       end;
 end;

const Total_Nodes = 100;
procedure RandomFillTree(var Node: TTree; const Nodes: integer);
var Left, Right: integer;
begin

    Left := Random(Nodes+1);
    Right := Nodes - Left;
    New(Node);
    Node^.inf := Round(Random);
    Node^.Left := nil; Node^.Right := nil;
    RandomFillTree(Node^.Left, Left);
    RandomFillTree(Node^.Right, Right);
end;

begin
Max:=0;
Search_Max(T,max);
end.
 

Автор: Mechanic 28.5.2006, 14:34
Цитата(zirogo @  22.5.2006,  14:32 Найти цитируемый пост)
пожалуйста, кто может напишите код!!!


Цитата(b44 @  24.5.2006,  05:56 Найти цитируемый пост)
по виду задача не сложная!!! может быть сделаю на выходных, просто щас время нет, сессия!


Цитата(b44 @  28.5.2006,  13:51 Найти цитируемый пост)
подскажите это так? я просто плохо знаю Pascal, я не проходил тему типы и процедуры!


Ничего не понимаю. Пожалуйста, объясните, кто тут кому помогает писать код!?  smile 

Код

Program BinaryTree;

//Сперва идут декларации типов, констант, переменных и процедур / функций
Type TTree=^TNode;
        TNode=record
            inf:integer;
            left,right:TTree;
          end;

const Total_Nodes = 100;

var T:TTree;
     max:integer;

procedure ....;
begin
  ...
end;

procedure ....;
begin
  ...
end;

//потом начинается тело программы, где это всё используется
begin
    // Fill tree
    RandomFillTree(T, Total_Nodes);
    // Search_Max
    Max:=0;
    Search_Max(T,max);
end.
 

Автор: b44 28.5.2006, 19:56
Mechanic не теряйся просто под моим ником трое человек! У меня просто попросили регистрацию!
если делать как написал ты, вылазиет ошиибка чтото про Стэк!
в этой части перед или после begin
Код

begin

    Left := Random(Nodes+1);
    Right := Nodes - Left;
    New(Node);
    Node^.inf := Round(Random);
    Node^.Left := nil; Node^.Right := nil;
    RandomFillTree(Node^.Left, Left);
    RandomFillTree(Node^.Right, Right);
end;

 

Автор: Mechanic 28.5.2006, 20:13
Любая рекурсия давит на стек.
Уменьши количество нодов. И посмотри размер стека, можно чуть растянуть его.
Нажми в редакторе CTRL+O дважды - появится что-то типа
Цитата

{$MINSTACKSIZE $00004000}
{$MAXSTACKSIZE $00100000}

Там попробуй изменить чуть в большую сторону.

Только это из Delphi. Если найду Pascal, то спробую там скомпилить и запустить, только скажи, что за версия Pascal'я у тебя. 

Автор: Mechanic 28.5.2006, 21:11
Нашёл Pascal. Там ошибка была. Ноды создавались бесконечно. smile
Вот рабочий вариант
Код

{Borland TP 7.0 file}
{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 65500,0,655360}

Program Bin_Tree;


Type TTree=^TNode;
     TNode=record
       inf:integer;
       left,right:TTree;
     end;

{Finds maximum Inf value of entire tree}
procedure Search_Max(var T:TTree;var elem:integer);
begin
   if T<>nil
      then
       begin
         if T^.inf>elem
            then elem:=T^.inf;
        Search_Max(T^.right,elem);
        Search_Max(T^.left,elem);
       end;
end;

{Creates Node with Nodes nested childs}
procedure RandomFillTree(var Node: TTree; const Nodes: integer);
var Left, Right: integer;
begin
    {calc parts (Left, Right)}
    if Nodes = 0 then Exit;
    Left := Random(Nodes);
    Right := Nodes - Left-1;
    New(Node);
    Node^.inf := Round(Random(65535));

    {debug output "trace"}
    write('  nodes:',nodes,' Left:',Left,' Right:',Right,' Inf:',Node^.inf);

    Node^.Left := nil; Node^.Right := nil;
    RandomFillTree(Node^.Left, Left);
    RandomFillTree(Node^.Right, Right);
end;

const Total_Nodes = 100;

var T: TTree;
    Max: integer;

begin{main program}
    {Fill tree}
    RandomFillTree(T, Total_Nodes);
    {Search_Max}
    Search_Max(T, Max);
    {Out result}
    writeln;
    writeln('Max = ',Max);
end.
 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)