IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

> Готовая программа на С++, Все есть, помогите расшифровать...
LOVE133
сообщение 22.07.2006 14:20
Сообщение #1


Гарцующая лошадка
**

Группа: Пользователи
Сообщений: 107
Пол: Женский
Реальное имя: Любовь

Репутация: -  0  +


есть задача- отыскание контуров заданной длины , звучит примерно так

Одной из важнейших задач, связанных с контурами является задача нахождения множества всех контуров [1, с.105]. Трудность ее состоит прежде всего в том, что число контуров ориентированного графа может быть экспоненциально большим относительно числа вершин. Поэтому при разработке алгоритмов внимание обращается не на полную трудоемкость алгоритма, а на относительную, т.е. на трудоемкость, приходящуюся на один контур.
Алгоритм отыскания множества вершин, принадлежащих контуру заданной длины

Алгоритм использует матрицу смежности A(G) и матрицу Ak, если длина контура равна k. Выберем некоторое i, такое, что aii(k)=1. Это означает, что вершина vi принадлежит контуру длины k.

Тогда вершина vj принадлежит тому же контуру, если выполняются следующие три условия:
ajj(k)=1;
для любого n aij(n)=1, т.е. существует путь длины n из vi в vj;
aji(k-n)=1, т.е. существует путь длины k-n из vj в vi.

Таким образом, для каждой вершины i графа мы легко можем построить множество вершин, каждый элемент которого принадлежит некоторому контуру длины k.

Нашла реализацию нужного алгоритма на С++, а так как с этим языком знакома довольно поверхностно, то не совсем могу разобраться в коде.Помогите. чем можете...Скачала кучу инфы по С++ ,но там почти все для бывалых пользователей...вот текст программы, можно просто прокомментировать, буду очень благодарна, потому ка кнадо все переделать под паскаль...
#include <iostream.h>
#define MaxNodes 4
#define Stepen 10

class Warshall
{
  private:
 unsigned Adj[MaxNodes][MaxNodes];  //Матрица смежностей.
  //Массив степеней матрицы смежностей.
 unsigned AdjN[Stepen][MaxNodes][MaxNodes];
 void Power(int);
  public:
 void Vvod();
 void Step();
 void Kontur();
};

void Warshall::Vvod()
{
  //Ввод матрицы смежностей заданного графа.
  cout <<"Вводите элементы матрицы смежностей по строкам:\n";
  for (int i=0;i<MaxNodes;i++)
 for (int j=0;j<MaxNodes;j++)
  {
 cout <<"Введите Adj["<< (i+1) << "]["<< (j+1) << "]: ";
 cin >> Adj[i][j];
  }
}

void Warshall::Step()
//Вычисление степеней матрицы смежностей.
{
  for (int l=0;l<Stepen;l++)
  {
	Power(l);
   }
}

void Warshall::Power(int n)
//Возвращает значение n-й степени матрицы A.
{
  unsigned Z[MaxNodes][MaxNodes];
  unsigned C[MaxNodes][MaxNodes];
  unsigned Val;

  for (int i=0;i<MaxNodes;i++)
 for (int j=0;j<MaxNodes;j++) C[i][j]=Adj[i][j];

  for (int m=0;m<n-1;m++)
  {
  for (int i=0;i<MaxNodes;i++)
for (int j=0;j<MaxNodes;j++)
{
Val = 0;
for (int k=0;k<MaxNodes;k++)
Val = Val || (Adj[i][k] && C[k][j]);
Z[i][j] = Val;
}
  for (i=0;i<MaxNodes;i++)
for (int j=0;j<MaxNodes;j++) C[i][j]=Z[i][j];
  }

  for (i=0;i<MaxNodes;i++)
for (int j=0;j<MaxNodes;j++)
 AdjN [n][i][j] = C[i][j];

}

void Warshall::Kontur()
//Отыскание контуров заданной длины.
{
  unsigned n;

  cout << "Вводите длину контура: ";
  cin >> n;
  for (int m=1;m<n;m++)
  {
	for (int i=0;i<MaxNodes;i++)
 if ( AdjN [m][i][i]==1 )
 //Вершина i+1 принадлежит контуру длины n.
 {
cout << "Вершина " << (i+1) <<
 " образует контуры длины " << (m+1) << " с вершинами из множества: {";
for (int j=0;j<MaxNodes;j++)
{
if ( AdjN[m][j][j]==1 )
//Вершина j принадлежит контуру длины m.
  for (int l=0;l<m;l++)
 if  ( AdjN[l][i][j]==1  && m-l>0
 && AdjN[m-l][j][i]==1 )
 {
cout << (j+1) << ' ';
goto Metka;
  }
Metka:;
}
cout << '}' << endl;
 }
  cout << endl;
  }
}

void main()
{
  Warshall A;
  A.Vvod();
  A.Step();
  A.Kontur();
}

mega_chok.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 2)
volvo
сообщение 22.07.2006 15:51
Сообщение #2


Гость






Цитата
надо все переделать под паскаль

Алгоритм Уоршалла? smile.gif

По-моему, так (только погоняй это, может я где-то ошибся...):

Const
  maxNodes =  4;
  Stepen   = 10;

Type
  Warshall = Object

  Private
    Adj:
      Array[0 .. Pred(maxNodes), 0 .. Pred(maxNodes)] Of Word;
    AdjN:
      Array[0 .. Pred(Stepen), 0 .. Pred(maxNodes), 0 .. Pred(maxNodes)] Of Word;
    Procedure Power(n: Integer);

  Public
    Procedure Vvod;
    Procedure Step;
    Procedure Kontur;

  End;

Procedure Warshall.Vvod;
Var i, j: Integer;
Begin
  WriteLn('Вводите элементы матрицы смежностей по строкам:');
  For i := 0 To Pred(maxNodes) Do
    For j := 0 To Pred(maxNodes) Do Begin
      WriteLn('Введите Adj[', (i+1), '][', (j+1), ']: ');
      ReadLn(Adj[i, j]);
    End;
End;

Procedure Warshall.Step;
Var i: Integer;
Begin
  For i := 0 To Pred(Stepen) Do Power(i);
End;

Procedure Warshall.Power(n: Integer);
Var
  Z, C: Array[0 .. Pred(maxNodes), 0 .. Pred(maxNodes)] Of Word;
  Val: Word;
  i, j, k, m: Integer;
Begin

  For i := 0 To Pred(maxNodes) Do
    For j := 0 To Pred(maxNodes) Do C[i, j] := Adj[i, j];

  For m := 0 To n - 2 Do Begin
    For i := 0 To Pred(maxNodes) Do
      For j := 0 To Pred(maxNodes) Do Begin
        Val := 0;
        For k := 0 To Pred(maxNodes) Do
          Val := Val Or (Adj[i, k] And C[k, j]);
        Z[i, j] := Val;
      End;

    For i := 0 To Pred(maxNodes) Do
      For j := 0 To Pred(maxNodes) Do C[i, j] := Z[i, j];

  End;

  For i := 0 To Pred(maxNodes) Do
    For j := 0 To Pred(maxNodes) Do
      AdjN[n, i, j] := C[i, j];

End;

Procedure Warshall.Kontur;
Var
  n: Word;
  i, j, k, l, m: Integer;

Begin
  WriteLn('Вводите длину контура:');
  ReadLn(n);
  For m := 1 To Pred(n) Do Begin
    For i := 0 To Pred(maxNodes) Do

      If AdjN[m, i, i] = 1 Then Begin
        Writeln('Вершина ', (i+1), ' образует контуры длины ',
                (m+1), 'с вершинами из множества: {');
        For j := 0 To Pred(maxNodes) Do Begin
          If AdjN[m, j, j] = 1 Then
            For l := 0 To Pred(m) Do
              If (AdjN[l, i, j] = 1) and (m - l > 0) and (AdjN[m - l, j, i] = 1) Then Begin
                Writeln((j+1), ' '); Break;
              End
        End;
        WriteLn('}');
      End;
      WriteLn;
  End
End;

Var
  A: Warshall;
begin
  A.Vvod;
  A.Step;
  A.Kontur;
end.
 К началу страницы 
+ Ответить 
LOVE133
сообщение 22.07.2006 17:49
Сообщение #3


Гарцующая лошадка
**

Группа: Пользователи
Сообщений: 107
Пол: Женский
Реальное имя: Любовь

Репутация: -  0  +


я даже не знаю, чей это алгоритм ))) потому как все из великой и могучей книги Евстигнеева"теория графов в программировании" ......а еще - откуда в паскале Private и Public? что-то я не встречала,хотя полагаться на мой опыт бессмысленно ))))
попробую в действие и попытаюсь сообразить чиво от меня хотел препод...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия 10.08.2025 2:44
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"