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

> Внимание!

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

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

> Готовая программа на С++, Все есть, помогите расшифровать...
сообщение
Сообщение #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 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 20.04.2024 4:18
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name