1 / 1 / 1
Регистрация: 22.10.2011
Сообщений: 54
1

Граф. Система односторонних дорог. Найти путь от A до B не проходящий через определенные вершины.

21.04.2012, 21:34. Показов 4906. Ответов 6
Метки нет (Все метки)

Задача:
"Задана система односторонних дорог. Найти путь, соединяющий города A и B и не проходящий через заданное множество городов".

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

Pascal
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
uses crt;
type matr=array[1..100,1..100] of integer;
     gor=array[1..100] of integer;
var s,mmm:matr;
    goroda:gor;
 
i,j,n,m,k,i1,j1,t,v:integer;
 
procedure matr_smezh;
begin
randomize;
for i:=1 to n do
begin
     for j:=1 to n do
     begin
     s[i,j]:=random(2);
     end;
end;
for i:=1 to n do
begin
for j:=1 to n do
begin
s[i,i]:=0;
s[j,i]:=s[i,j];
end;
end;
end;
 
procedure vuvod(s:matr; n:integer);
begin
for i:=1 to n do
begin
     for j:=1 to n do
     begin
     write(s[i,j],'   ');
     end;
writeln;
end;
end;
 
procedure notname;
begin
for i:=1 to n do
if (i=goroda[i]) then break else
begin
for j:=1 to n do
if  (j=goroda[j]) then break else
begin
for t:=1 to i1 do
for v:=1 to j1 do
mmm[t,v]:=s[i,j];
end;
end;
end;
 
begin
clrscr;
writeln ('Ââåäèòå êîëè÷åñòâî âåðøèí ãðàôà');
readln(n);
writeln('Ââåäèòå êîëè÷åñòâî íåïðîõîäèìûõ âåðøèí');
readln(m);
i1:=n-m; j1:=i1;
writeln('Ââåäèòå âåðøèíû');
for i:=1 to m do
readln( goroda[i]);
matr_smezh;
writeln('ìàòðèöà ñìåæíîñòè');
vuvod(s,n);
writeln;
for i:=1 to m do
write(goroda[i],' ');
notname;
writeln;
vuvod(mmm,i1);
readln;
end.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.04.2012, 21:34
Ответы с готовыми решениями:

Граф: найти минимальный путь из вершины А в вершину В, проходящий через вершину С
Ребят помогите кто чем может. Задача типа: Найти мин.путь из вершины А в вершину В проходящий через...

Найти путь, соединяющий вершины a и b и не проходящий через заданное подмножество вершин V
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry:...

Задана система односторонних дорог
Найти путь, соединяющий города A и B и не проходящий через заданное множество городов. ...

перевод с pascal, система односторонних дорог
Задана система односторонних дорог. Найти путь, соединяющий города A и B и не проходящий через...

6
Эксперт С++
4725 / 2546 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.04.2012, 12:40 2
elvipka, Вы выбрали не самый простой путь решения.
Я Вам могу описать более простой вариант, но для этого ответьте на несколько вопросов:
Нужно вывести любой путь, один из самых коротких или всевозможные пути?
0
1 / 1 / 1
Регистрация: 22.10.2011
Сообщений: 54
22.04.2012, 14:17  [ТС] 3
Цитата Сообщение от valeriikozlov Посмотреть сообщение
elvipka, Вы выбрали не самый простой путь решения.
Я Вам могу описать более простой вариант, но для этого ответьте на несколько вопросов:
Нужно вывести любой путь, один из самых коротких или всевозможные пути?
а задачке не сказано, но думаю что кратчайший.
надеюсь на вашу помощь)
спасибо)
0
Эксперт С++
4725 / 2546 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.04.2012, 14:42 4
Цитата Сообщение от elvipka Посмотреть сообщение
а задачке не сказано, но думаю что кратчайший.
тогда описываю вариант решения:
Вам нужна только матрица смежности s[1..100,1..100] и один массив типа integer a[1..100] .
Все элементы a[] сначало равны 0. Затем города, через которые нельзя проходить: делаем a[с такими номерами]:=-1;
Вводим значения A и B. Тут нужна очередь, и в очередь заносим элемент A. (И обязательно в массиве a[] помечаем город A числом A)
Затем так:
проводим поиск по матрице смежности всех городов в которые можно попасть из элемента, который находится в начале очереди. Если a[такого номер города]=0, то такой номер помечаем значением в a[] номером элемента, который находится в начале очереди, и заносим его тоже в очередь.
По окончании такого прохода по очереди, можно пройтись в обратную сторону (для этого нужен будет еще один массив [1..100]).
Если не сумеете написать код, пишите, помогу.
0
1 / 1 / 1
Регистрация: 22.10.2011
Сообщений: 54
22.04.2012, 20:43  [ТС] 5
что то совсем не могу понять.
очередь - как шарики в трубе, с одной стороны добавил с другой убрал.
очередь как новый массив использовать?
0
Эксперт С++
4725 / 2546 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
22.04.2012, 21:24 6
elvipka, сейчас что-нибудь напишу

Добавлено через 22 минуты
проверяйте:
Pascal
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
88
89
90
91
92
93
94
95
96
97
98
uses crt;
type matr=array[1..100,1..100] of integer;
     gor=array[1..100] of integer;
var s:matr;
Q,goroda:gor;
 
i,n,m,t,i_st,i_end,A,B:integer;
 
procedure matr_smezh;
var i,j:integer;
begin
randomize;
for i:=1 to n do
begin
     for j:=1 to n do
     begin
     s[i,j]:=random(2);
     end;
end;
for i:=1 to n do
begin
s[i,i]:=0;
for j:=1 to n do
begin
s[j,i]:=s[i,j];
end;
end;
end;
 
procedure vuvod();
var i,j:integer;
begin
for i:=1 to n do
begin
     for j:=1 to n do
     begin
     write(s[i,j],'   ');
     end;
writeln;
end;
end;
 
procedure poisk;
var i:integer;
begin
goroda[A]:=200;
Q[1]:=A; i_st:=1; i_end:=2;
while i_st<i_end do begin
for i:=1 to n do
if (goroda[i]=0) and (s[Q[i_st],i]=1) then begin
Q[i_end]:=i; inc(i_end); goroda[i]:=Q[i_st];
end;
inc(i_st);
end;
end;
 
procedure vuvod_res();
var i:integer;
begin
if goroda[B]=0 then writeln('Пути нет')
else
begin
Q[1]:=B; i_end:=2; t:=goroda[B];
while t<>A do begin
Q[i_end]:=t; inc(i_end); t:=goroda[t];
end;
Q[i_end]:=A;
for i:=i_end downto 1 do write(Q[i],' ');
end;
end; 
 
begin
clrscr;
writeln ('Введите количество вершин графа');
readln(n);
writeln('Введите количество непроходимых вершин');
readln(m);
writeln('Введите вершины');
for i:=1 to m do begin
readln(t); goroda[t]:=-1;
end;
matr_smezh;
writeln('матрица смежности');
vuvod();
writeln;
for i:=1 to n do 
if goroda[i]=-1 then write(i,' ');
writeln;
writeln ('Введите номер вершины А');
read(A);
writeln ('Введите номер вершины B');
read(B);
poisk;
writeln;
vuvod_res();
writeln;
readln;
end.
а про очередь Вы правильно написали.
1
1 / 1 / 1
Регистрация: 22.10.2011
Сообщений: 54
22.04.2012, 21:33  [ТС] 7
Цитата Сообщение от valeriikozlov Посмотреть сообщение
elvipka, сейчас что-нибудь напишу

Добавлено через 22 минуты
проверяйте:
Pascal
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
88
89
90
91
92
93
94
95
96
97
98
uses crt;
type matr=array[1..100,1..100] of integer;
     gor=array[1..100] of integer;
var s:matr;
Q,goroda:gor;
 
i,n,m,t,i_st,i_end,A,B:integer;
 
procedure matr_smezh;
var i,j:integer;
begin
randomize;
for i:=1 to n do
begin
     for j:=1 to n do
     begin
     s[i,j]:=random(2);
     end;
end;
for i:=1 to n do
begin
s[i,i]:=0;
for j:=1 to n do
begin
s[j,i]:=s[i,j];
end;
end;
end;
 
procedure vuvod();
var i,j:integer;
begin
for i:=1 to n do
begin
     for j:=1 to n do
     begin
     write(s[i,j],'   ');
     end;
writeln;
end;
end;
 
procedure poisk;
var i:integer;
begin
goroda[A]:=200;
Q[1]:=A; i_st:=1; i_end:=2;
while i_st<i_end do begin
for i:=1 to n do
if (goroda[i]=0) and (s[Q[i_st],i]=1) then begin
Q[i_end]:=i; inc(i_end); goroda[i]:=Q[i_st];
end;
inc(i_st);
end;
end;
 
procedure vuvod_res();
var i:integer;
begin
if goroda[B]=0 then writeln('Пути нет')
else
begin
Q[1]:=B; i_end:=2; t:=goroda[B];
while t<>A do begin
Q[i_end]:=t; inc(i_end); t:=goroda[t];
end;
Q[i_end]:=A;
for i:=i_end downto 1 do write(Q[i],' ');
end;
end; 
 
begin
clrscr;
writeln ('Введите количество вершин графа');
readln(n);
writeln('Введите количество непроходимых вершин');
readln(m);
writeln('Введите вершины');
for i:=1 to m do begin
readln(t); goroda[t]:=-1;
end;
matr_smezh;
writeln('матрица смежности');
vuvod();
writeln;
for i:=1 to n do 
if goroda[i]=-1 then write(i,' ');
writeln;
writeln ('Введите номер вершины А');
read(A);
writeln ('Введите номер вершины B');
read(B);
poisk;
writeln;
vuvod_res();
writeln;
readln;
end.
а про очередь Вы правильно написали.
спасибо вам!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.04.2012, 21:33
Помогаю со студенческими работами здесь

Не могу понять задачу (система односторонних дорог)
Тема такая, препод задал задачку на языке &quot;C&quot;, решить ее, как вы поняли, я не могу:) Задача...

Найти путь, соединяющий города A и B, и не проходящий через заданное множество городов
&quot;Задана система односторонних дорог. Найти путь, соединяющий города A и B и не проходящий через...

Найти путь, соединяющей города А и В и не проходящий через заданное множество городов
Задана система односторонних дорог. Найти путь, соединяющей города А и В и не проходящий через...

Найти путь максимальной длины, и проходящий через заданное множество вершин
5)Дано бинарное дерево. Найти путь максимальной длины, и проходящий через заданное множество...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru