Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal ABC
Войти
Регистрация
Восстановить пароль
 
tommy0
0 / 0 / 0
Регистрация: 01.04.2017
Сообщений: 23
1

Вывести все пары городов связанных между собой не напрямую, но не более чем с одной пересадкой

23.04.2017, 21:07. Просмотров 278. Ответов 6
Метки нет (Все метки)

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

переделал код с C++ на паскале, но он не работает подскажите пожалуйста что не так.

это код на C++:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
 
const int k=6;
 
int main()
{
    int arr[k][k]=
    {{0,0,1,0,0,1},
     {0,0,1,1,0,0},
     {1,1,0,0,0,0},
     {0,1,0,0,1,0},
     {0,0,0,1,0,0},
     {1,0,0,0,0,0}};
     for (int i=0;i<k;i++)
         for (int j=0;j<k-1;j++)
             if (arr[i][j]==1)
                for (int j1=j+1;j1<k;j1++)
                    if (arr[i][j1]==1 && arr[j][j1]==0)
                        std::cout<<j+1<<' '<<j1+1<<'\n';             
}
Это переделанный:

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
program Project1;
 
{$APPTYPE CONSOLE}
 
{$R *.res}
 
uses
  System.SysUtils;
 
const
 n1=10;
 
 
type tarr = array [1..n1,1..n1] of integer;
 
 
procedure out_arr(n: integer; var x: Tarr);
var
  i,j: integer;
begin
  for i := 1 to n  do
  begin
   writeln;
 
  for j := 1 to n do
 
    write(x[i,j]:5);
  end;
end;
 
procedure rand (n:integer;var mas:tarr);
var i,j:integer;
 begin
 randomize;
for i := 1 to n do
 
 
for j := 1 to n do
  mas[i,j]:=random(2);
  out_arr(n,mas);
  writeln;
end;
 
procedure samoleti (n:integer; var x:tarr);
 
var i,j,j1:integer;
 
 
 begin
 i:=0;
 j1:=j+1;
 while i<n do
 begin
 
 while j<n-1 do
 
 if (x[i,j]=1) then
 
  while j1<n do
 
 if (x[i,j1]=1) and (x[i,j1]=0) then
 
 
   writeln(J+1,j1+1) ;
   i:=i+1;
  j:=J+1;
  j1:=J1+1;
 end;
 
 
 
 end;
 
 
var x:tarr;n:integer;
 
begin
 writeln('введите кол-во строк и столбцов');
 readln(n);
 rand(n,x);
 samoleti(n,x);
 out_arr(n,x);
 
 readln;
 
 
end.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2017, 21:07
Ответы с готовыми решениями:

Н городов связаны между собой Мдорогами. Каждая дорога связывает только два города. Известны длины всех дорог. Найдите пути между любыми двумя (вводя
N городов связаны между собой mдорогами. Каждая дорога связывает только два...

Найти все числа из массива B, встречающиеся более чем в одной строке матрицы A
Помогите решить задачку в Pascal, заранее спасибо! Найти все числа из...

Напечатать все пары городов, связанных между собой не напрямую, но не более чем с одной пересадкой
Помогите пожалуйста в C++ Сеть авиалиний, соединяющая города, задана...

Напечатайте список городов, которые напрямую сообщаются более чем с тремя городами
Уважаемы формучане,объясните пожалуйста кое-что. Вот задача: Пусть...

Вывести на экран все пары городов с расстоянием менее 100 км между ними
Помогите пожалуйста с решение задачи на массивы. неужто сложно напечатать...

6
Puporev
Модератор
55429 / 42552 / 29405
Регистрация: 18.05.2008
Сообщений: 100,668
24.04.2017, 09:53 2
Цитата Сообщение от tommy0 Посмотреть сообщение
это код на C++:
Разве это весь код?
0
tommy0
0 / 0 / 0
Регистрация: 01.04.2017
Сообщений: 23
24.04.2017, 14:16  [ТС] 3
Вроде как да
0
ФедосеевПавел
Модератор
3856 / 2177 / 894
Регистрация: 01.02.2015
Сообщений: 7,248
25.04.2017, 07:35 4
tommy0, полагаю, что требуется применить алгоритм Флойда (Флойда-Уоршелла), причём расстояния между городами принять равными 1 (алгоритм Флойда для взвешенных матриц).
Потом из матрицы расстояний вывести те пары, у которых расстояние равно ровно 2.

Скорее всего алгоритм не в чистом виде, а с лёгкой модификацией - проверять отсутствие пути между городами по значению 0.

Собственно - всё.
0
tommy0
0 / 0 / 0
Регистрация: 01.04.2017
Сообщений: 23
25.04.2017, 21:46  [ТС] 5
ФедосеевПавел, а без алгоритма Флойда никак? Просто я не понимаю как сделать через него.
0
ФедосеевПавел
Модератор
3856 / 2177 / 894
Регистрация: 01.02.2015
Сообщений: 7,248
25.04.2017, 22:48 6
Это моя реализация, но она не полностью корректна.
Найти кратчайший путь между двумя заданными городами

У вас будет примерно так же, но что-то нужно доработать в условиях проверки, т.к. в вашем случае нет Infinity (бесконечного расстояния).

После завершения алгоритма будет матрица расстояний. В которой будет указано количество перелётов. Просматривая эту таблицу нужно будет выбрать те пары, у которых расстояние равно 2.

У меня сейчас нет времени на отладку. Поэтому оставлю это вам. Главное, чтобы вы поняли идею.

Но можно и так, как в вашей программе - поиском в глубину, с ограничением на погружение. Но потребуется обрабатывать дублирующиеся пары. Так, что лучше указанным мною алгоритмом.
0
tommy0
0 / 0 / 0
Регистрация: 01.04.2017
Сообщений: 23
26.04.2017, 17:30  [ТС] 7
ФедосеевПавел,спасибо
0
26.04.2017, 17:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.04.2017, 17:30

Человек везет пару связанных между собой санок. Найти ускорение саней и силу натяжения веревки между санями.
Человек везет пару связанных между собой санок, прикладывая к веревке силу 50 Н...

Сравнить массивы между собой и вывести массив, в котором больше разеых элементов, чем в других
Доброго времени суток форумчане, помогите пожалуйста написать программу, есть 5...

Достать все товары, которые принадлежат более чем одной категории
Я это сделал, вывел так: название продукта и название категории, через запятую,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru