Помощь - Поиск - Пользователи - Календарь
Полная версия: Готовая программа на С++
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
LOVE133
есть задача- отыскание контуров заданной длины , звучит примерно так

Одной из важнейших задач, связанных с контурами является задача нахождения множества всех контуров [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
volvo
Цитата
надо все переделать под паскаль

Алгоритм Уоршалла? 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
я даже не знаю, чей это алгоритм ))) потому как все из великой и могучей книги Евстигнеева"теория графов в программировании" ......а еще - откуда в паскале Private и Public? что-то я не встречала,хотя полагаться на мой опыт бессмысленно ))))
попробую в действие и попытаюсь сообразить чиво от меня хотел препод...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.