Помощь - Поиск - Пользователи - Календарь
Полная версия: Матрица =((((
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
1kypc
Подскажите плз как решить задачу?Мыслей по решению нет =(
Матрица - статическая с переменной верхней границей (опр при вводе)

сама задача:
Сеть авиалиний , соединяющих города , задана матрицей СВЯЗАННОСТИ M(k,k) , где M[i,j]=0 если города i,j
не связаны между собой напрямую и M[i,j]=1 если связаны
Вывести все пары городов связанных между собой не напрямую, но не более чем с 1 пересадкой.

Буду рад методу решения или какой-нибудь подсказке...
Заранее благодарен
мисс_граффити
Больше похоже на задание по дискретной математике... Ну, если у вас еще ничего такого не было, можно делать так (решение в лоб).
Работаем с первой строкой. Нашли первую единичку, запомнили, в каком она столбце (пусть это столбец j).
Теперь переходим на j-тую строку: все единички соответствуют городам, в которые можно попасть из первого города с пересадкой в j-том. Выводим их.
Продолжаем работать с первой строкой, пока в ней не кончатся единички...
Потом переходим на вторую.

Проблема в том, что будут выводиться пары Москва-Киев и Киев-Москва, если есть один путь... А если несколько путей, то таких одинаковых пар будет еще больше. Это устроит?
Michael_Rybak
А почему просто тремя вложенными циклами не проверить? Первый - откуда, второй - куда, третий - через какую вершину.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.