Міністерство освіти та науки України Національний університет «Львівська політехніка»
ЗВІТ З лабораторної роботи №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); Висновок: