Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Матрица =((((

Автор: 1kypc 26.12.2006 22:21

Подскажите плз как решить задачу?Мыслей по решению нет =(
Матрица - статическая с переменной верхней границей (опр при вводе)

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

Буду рад методу решения или какой-нибудь подсказке...
Заранее благодарен

Автор: мисс_граффити 26.12.2006 22:27

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

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

Автор: Michael_Rybak 27.12.2006 20:10

А почему просто тремя вложенными циклами не проверить? Первый - откуда, второй - куда, третий - через какую вершину.