codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <iostream> #include <iomanip> //#include <windows.h> using namespace std; //Функция проверки, можно ли перейти в данный узел bool check(int key, int *mas, int kol) { for (int j = 0; j < kol; j++) if (mas[j] == key) //Если переход в этот узел уже был return false; return true; } int main() { // SetConsoleCP(1251); // SetConsoleOutputCP(1251); int kol; do //Ввод кол-ва узлов сети { cout << "Введите количество узлов(2-10) --> "; cin >> kol; } while (kol < 2 || kol > 10); //Создание матрицы смежности int **arr = new int *[kol]; for (int i = 0; i < kol; i++) arr[i] = new int[kol]; int rasst; for (int i = 0; i < kol; i++) { for (int j = i; j < kol; j++) { if (i == j) /*Если одинаковые точки - заполняем нулями, чтобы получилась главная диагональ нулей */ { arr[i][j] = 0; continue; } do /*Ввод расстояния между узлами для заполнения матрицы смежности */ { cout << "Введите расстояние от узла " << i << " до узла " << j << " --> "; cin >> rasst; } while (rasst < 1); arr[i][j] = arr[j][i] = rasst; } } //Вывод матрицы смежности cout << endl << "Матрица смежности: "; for (int i = 0; i < kol; i++) { cout << endl; for (int j = 0; j < kol; j++) cout << setw(5) << arr[i][j]; } int *route = new int[kol]; /* Маршрут (массив узлов сети, в которых мы побывали в порядке посещения) */ cout << endl; char ans; int start; do { for (int i = 0; i < kol; i++) //Заполняем массив -1 route[i] = -1; do //Ввод стартового узла { cout << "Введите стартовый узел --> "; cin >> start; } while (start < 0 || start > kol - 1); route[0] = start; int now = start; int path = 0; // длина уже пройденного пути cout << "\nМаршрут:" << endl; for (int i = 1; i < kol; i++) { /* i - индекс по маршруту и количество переходов, не считая возврата в стартовый узел */ int min = INT_MAX; int min_town; for (int j = 0; j < kol; j++) { if (check(j, route, kol) && arr[now][j] < min && arr[now][j] > 0) { //Нахождение минимума min = arr[now][j]; // запомнили текущий минимум min_town = j; // запомнили номер узла для тек.мин. } } /* здесь min - действительный минимум и min_town - номер узла с минимальным расстоянием от текущего */ path += min; // добавляем к общему пути route[i] = min_town; // добавляем узел в маршрут cout << setw(2) << now << " -> " << setw(2) << route[i] << " (расстояние " << min << ", путь " << path << ")" << endl; now = route[i]; } // обрабатываем возврат в стартовый узел path += arr[start][now]; cout << setw(2) << now << " -> " << setw(2) << start << " (расстояние " << arr[start][now] << ", путь " << path << ")" << endl; cout << "Общая длина пройденного пути: " << path << endl; cout << endl << "Желаете продолжить поиск путей?(+, если да) --> "; cin >> ans; } while (ans == '+'); delete[] route; //Удаление массива пройденных узлов //Удаление матрицы смежности for (int i = 0; i < kol; i++) delete[] arr[i]; delete[] arr; system("pause"); return 0;}
Private
[
?
]
Run code
Submit