Среда, 08.01.2025
Pascal 4 All
[ · Новые сообщения · Участники · Правила форума · Поиск · RSS ]

 

  • Страница 1 из 1
  • 1
Модератор форума: Seqular, Pavel  

Деревья
BzDoNДата: Воскресенье, 19.12.2010, 23:40 | Сообщение # 1
Новичок
Группа: Пользователи
Сообщений: 8
Репутация: 1
Замечания: 0%
Статус: Offline
Задано сильно ветвящееся дерево. При его вводе могли быть сделаны ошибки. Провести проверку на отсутствие циклов, то есть повторяющихся вершин. При обнаружении цикла выдать на экран последовательность вершин, составляющих цикл. (Pascal)

Снизу прикреплена теория по данной теме.

Прикрепления: 4988103.rar (131.4 Kb)


Сообщение отредактировал BzDoN - Воскресенье, 19.12.2010, 23:50
 
SeqularДата: Среда, 22.12.2010, 22:45 | Сообщение # 2
Хранитель
Группа: Администраторы
Сообщений: 859
Репутация: 35
Статус: Offline
Code

Program TreeAnalize;
Uses CRT;
Const MaxSize = 20;
Var a: Array[1..MaxSize, 1..MaxSize] of Byte;
     i,j: Byte;
     n: Byte;

Procedure WriteMatrix;
Begin
Write('How many vertex?: '); Readln(n);
Writeln('e.g. "[1 -> 3]: 1" if ver.3 & ver.1 - linked');
Writeln('e.g. "[2 -> 5]: 0" if ver.2 & ver.5 - no linked');
Writeln;
For i := 1 to n-1 do
     Begin
     For j := i + 1 to n do
         Begin
         Write('[',i,' -> ',j,']: ');
         Readln(a[i,j]);
         a[j,i] := a[i,j];
         End;
     End;
End;

Procedure PrintMatrix;
Begin
Writeln;
For i := 1 to n do
     Begin
     For j := 1 to n do
         Write(a[i,j]:4);
     Writeln;
     End;
End;

Function AnalizeMatrix: Boolean;
Var col: boolean;
     k: Byte;
     result: Boolean;
Begin
result := True;
For i := 2 to n do
     Begin
     Col := false;
     For j := 1 to i do
         Begin
         if (a[i,j] = 1) then
            Begin
            if (Col = false) then Col := True
                             else Begin
                    result := false;
                    Write('Loop in: ',j,' -> ', i);
                    For k := j-1 downto 1 do
                    if (a[i,k] = 1) then
                    Begin
                    Writeln(' -> ',k);
                    Break
                    End;
                    End;
            End;
         End;
     End;
AnalizeMatrix := result;
End;

Begin
ClrScr;
WriteMatrix;
PrintMatrix;
ReadKey;
if (AnalizeMatrix) then Writeln('Clear!!!')
                    else Writeln('Loop found!');
ReadKey;
End.

Задаёте матрицу смежности как в той задаче с проверкой простой. Чтобы не запутаться - нарисуйте дерево сначала на бумажке )
Прогу потестил на 3-х графах! Простые петли определяет неплохо!


Поддерживаю также проект сообщество молодых сисадминов
 
SeqularДата: Среда, 22.12.2010, 23:12 | Сообщение # 3
Хранитель
Группа: Администраторы
Сообщений: 859
Репутация: 35
Статус: Offline
Тесты:
1) Имеем дерево:
Пишем
(Почему я ввожу именно это - надеюсь, вопросов не возникает?)
Выводит:
и Clear! т.е. зацикливаний нет
Прикрепления: 0731654.gif (2.5 Kb) · 6832821.gif (7.1 Kb) · 2966067.gif (1.7 Kb)


Поддерживаю также проект сообщество молодых сисадминов
 
SeqularДата: Среда, 22.12.2010, 23:25 | Сообщение # 4
Хранитель
Группа: Администраторы
Сообщений: 859
Репутация: 35
Статус: Offline
Второй пример:
Все ясно без слов:
Граф:
Ввожу данные




Выдает:
Quote
Loop in: 3 -> 6 -> 2
Loop in: 7 -> 10 -> 5
Loop in: 9 -> 12 -> 8
Loop found!
Прикрепления: 6641298.gif (3.9 Kb) · 5613490.gif (4.3 Kb) · 9623086.gif (4.3 Kb) · 2427545.gif (2.7 Kb) · 4763005.gif (3.0 Kb)


Поддерживаю также проект сообщество молодых сисадминов
 
FadeonДата: Вторник, 28.12.2010, 01:01 | Сообщение # 5
Новичок
Группа: Пользователи
Сообщений: 5
Репутация: 0
Замечания: 0%
Статус: Offline
Имеется дерево, корень которого соответствует основателю рода. Сыновья каждой вершины задают сыновей и дочерей соответствующего человека. Указывается имя некоторого человека. Требуется выдать имена его детей, внуков, сестер и братьев, одного из родителей, дедушки или бабушки.
Прикрепления: 2438571.rar (131.3 Kb)


Сообщение отредактировал Fadeon - Вторник, 28.12.2010, 01:02
 
SeqularДата: Вторник, 28.12.2010, 08:59 | Сообщение # 6
Хранитель
Группа: Администраторы
Сообщений: 859
Репутация: 35
Статус: Offline
Fadeon, Если эта задача не имеет отношения к текущей - создавайте новую тему

Поддерживаю также проект сообщество молодых сисадминов
 
  • Страница 1 из 1
  • 1
Поиск:

Copyright MyCorp © 2025
Используются технологии uCoz
javascript:;" rel="nofollow" onclick="loginPopupForm(); return false;