Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
ЗВІТ
З лабораторної роботи №9
З дисципліни: «Програмування ч.4»
Мета:
6) Довести чи можуть існувати мінімальні шляхи в графі в якому немає від’ємних циклів
Блок-схема:
Лістинг програми 6):
case 9:
cout << "Object-oriented method" << endl;
cout << "Умова: Вивести всi найкоротшi шляхи мiж пунктами i->j" << endl;
cout << "n = ";
cin >> iN;
graf = new CGraf(iN);
graf->Seek();
system("PAUSE");
system("cls");
cout << "Procedure-oriented method" << endl;
cout << "n = ";
cin >> iN;
Graf(iN);
system("PAUSE");
break;
case 0:
/****************************************************************\
METHOD........: CGraf
DESCRIPTION...: Initializing variables
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - size of graf
RETURNS.......: None
\****************************************************************/
CGraf::CGraf(int iN)
{
m_iN = iN;
}
/****************************************************************\
METOD.........: Seek
DESCRIPTION...: Seek Negative way
ATTRIBUTES....: Public
ARGUMENTS.....: none
RETURNS.......: bool
\****************************************************************/
bool CGraf::Seek()
{
vector < vector<int> > G (m_iN, vector<int> (m_iN));
for (int i=0; i<m_iN; i++)
for (int j=0; j<m_iN; j++)
{
if (j!=i)
{
int iTemp;
cout << i+1 << " -> " <<j+1 <<" = ";
cin >> iTemp;
G[i][j] = iTemp ? iTemp : g_iINF;
}
else
{
G[i][j]=0;
}
}
vector<vector<int> > D (m_iN), D2;
D2 = G;
for (int i=0; i<m_iN; i++)
D[i].resize (m_iN+1);
for (int k=0; k<m_iN; k++)
{
for (int i=0; i<m_iN; i++)
for (int j=0; j<m_iN; j++)
D[i][j] = min (D2[i][j], D2[i][k]+D2[k][j]);
D.swap (D2);
}
D.swap (D2);
for (int i=0; i<m_iN; i++)
{
for (int j=0; j<m_iN; j++)
{
if(i!=j)
cout << "Min way " << i+1 << " -> " << j+1 << " = " << D[i][j] << endl;
}
}
return false;
}
/****************************************************************\
FUNCTION......: Graf
DESCRIPTION...: Seek Negative way
ATTRIBUTES....: Public
ARGUMENTS.....:
iN - size of graf
RETURNS.......: bool
\****************************************************************/
bool Graf (int iN)
{
vector < vector<int> > G (iN, vector<int> (iN));
for (int i=0; i<iN; i++)
for (int j=0; j<iN; j++)
{
if (j!=i)
{
int iTemp;
cout << i+1 << " -> " <<j+1 <<" = ";
cin >> iTemp;
G[i][j] = iTemp ? iTemp : g_iINF;
}
else
{
G[i][j]=0;
}
}
vector<vector<int> > D (iN), D2;
D2 = G;
for (int i=0; i<iN; i++)
D[i].resize (iN+1);
for (int k=0; k<iN; k++)
{
for (int i=0; i<iN; i++)
for (int j=0; j<iN; j++)
D[i][j] = min (D2[i][j], D2[i][k]+D2[k][j]);
D.swap (D2);
}
D.swap (D2);
for (int i=0; i<iN; i++)
{
for (int j=0; j<iN; j++)
{
if(i!=j)
cout << "Min way " << i+1 << " -> " << j+1 << " = " << D[i][j] << endl;
}
}
return false;
}
/****************************************************************\
FUNCTION......: Seek_sub
DESCRIPTION...: seek substring in the string
ATTRIBUTES....: Public
ARGUMENTS.....:
szText - text string
RETURNS.......: bool
\****************************************************************/
bool Seek_sub(string szText)
{
int iNum;
iNum = szText.find("abcd");
if (iNum==-1)
return false;
else
return true;
}
class CGraf
{
private:
int m_iN;
public:
CGraf(int iN);
bool Seek();
};
bool Graf (int iN);
bool Seek_sub(string szText);
Висновок:
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора