Форум программистов, компьютерный форум, киберфорум
Pascal ABC
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
11 / 11 / 2
Регистрация: 17.02.2014
Сообщений: 947

Определить, можно ли попасть по дорогам из первого пункта в n-й

09.02.2016, 16:20. Показов 2982. Ответов 30
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
На карте местности имеется N населенных пунктов, пронумерованных от 1 до N (N<= 10). Некоторые из пунктов соединены между собой дорогами. Информация о дорогах задается в виде последовательности пар чисел i, j (i<j), указывающих, что i-й и j-й пункты соединены дорогой, признак конца этой последовательности — пара нулей. Определить, можно ли попасть по этим дорогам из первого пункта в n-й.


Как я понял - это реализация данной программы на языке Basic.
Visual Basic
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
99
100
Private Minc(1 To 10, 1 To 10) As Integer
Private Chk(1 To 10)           As Integer
Private flg                    As Boolean
Private Path                   As String   '::: Строка пути
 
Sub Init()
 
Dim i As Integer
Dim j As Integer
 
    For i = 1 To 10
    
        Chk(i) = 0
        
        For j = 1 To 10
            Minc(i, j) = 0
        Next j
        
    Next i
 
    Minc(1, 5) = 1
    Minc(5, 1) = 1
 
    Minc(2, 5) = 1
    Minc(5, 2) = 1
 
    Minc(3, 5) = 1
    Minc(5, 3) = 1
 
    Minc(6, 5) = 1
    Minc(5, 6) = 1
 
    Minc(6, 7) = 1
    Minc(7, 6) = 1
 
    Minc(4, 5) = 1
    Minc(5, 4) = 1
 
    'Minc(4, 8) = 1
    'Minc(8, 4) = 1
 
    Minc(9, 8) = 1
    Minc(8, 9) = 1
 
    Minc(8, 10) = 1
    Minc(10, 8) = 1
 
    flg = False
 
    Path = ""
 
End Sub
 
Sub DFS(n As Integer, m As Integer)
 
Dim i As Integer
 
    If flg Then
       Exit Sub
    End If
 
    Chk(n) = 1
    
    Path = Path & ";" & CStr(n)
    
    For i = 1 To 10
    
        If (Minc(i, n) <> 0) And (Chk(i) = 0) Then
           
           If i = m Then
              flg = True
              Debug.Print Path & ";" & CStr(m) '::: Печать пути
              Exit Sub
           End If
           
           DFS i, m
           
           k% = InStrRev(Path, ";")
           
           Path = Left$(Path, (k% - 1))
                      
        End If
        
    Next i
 
End Sub
 
Sub Start()
 
    Init
 
    DFS 7, 10
 
    If flg Then
       Debug.Print "Путь найден"
    Else
       Debug.Print "Путь не существует"
    End If
 
End Sub
Как эту программу можно реализовать на паскале?
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
09.02.2016, 16:20
Ответы с готовыми решениями:

Определить, можно ли попасть по дорогам из 1-го пункта в n-ный.
Помогите составить программы. 3.1. Описать рекурсивную функцию pow(x,n) от вещественного x(x¹0) и целого n, которая вычисляет...

Определить, можно ли попасть по этим дорогам из первого пункта в n-й
Всем привет, помогите пожалуйста с программой. Или хотя бы подскажите, что с чем нужно сравнивать. Рекурсия Задача: На карте...

Определить, можно ли попасть по дорогам из первого населенного пункта в последний
Поделитесь мыслями, как можно сделать это задание. Вот и само условие задания. На местности имеется N населенных пунктов, пронумерованных...

30
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8675 / 4512 / 1670
Регистрация: 01.02.2015
Сообщений: 13,942
Записей в блоге: 13
17.02.2016, 15:07
Студворк — интернет-сервис помощи студентам
Поиск в ширину, согласно Wikipedia:
Обозначим число вершин и рёбер в графе как https://www.cyberforum.ru/cgi-bin/latex.cgi?\left|V \right| и https://www.cyberforum.ru/cgi-bin/latex.cgi?\left|E \right| соответственно.
Так как в худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков смежности, временная сложность алгоритма составляет
https://www.cyberforum.ru/cgi-bin/latex.cgi?O(\left|V \right|+\left|E \right|)
Так как в памяти хранятся все развёрнутые узлы, пространственная сложность алгоритма составляет
https://www.cyberforum.ru/cgi-bin/latex.cgi?O(\left|V \right|+\left|E \right|)
Я не все слова отсюда понял, но, IMHO, для DFS будет полный перебор возможных вариантов, в то время как для BFS посещённая вершина больше не рассматривается, даже если к ней ведут несколько ребер от ещё нерассмотренных вершин.
0
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
17.02.2016, 17:18
А в глубину
Я выиграл
1
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8675 / 4512 / 1670
Регистрация: 01.02.2015
Сообщений: 13,942
Записей в блоге: 13
17.02.2016, 19:59


Туз в кармане!
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38210 / 21143 / 4313
Регистрация: 12.02.2012
Сообщений: 34,757
Записей в блоге: 14
18.02.2016, 09:15
Цитата Сообщение от ФедосеевПавел Посмотреть сообщение
в то время как для BFS посещённая вершина больше не рассматривается, даже если к ней ведут несколько ребер от ещё нерассмотренных вершин.
- обход графа - это перебор каждой из его вершин ровно один раз. И в DFS и в BFS каждая вершина посещается только один раз.
1
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
18.02.2016, 23:37
В общем случае
0
11 / 11 / 2
Регистрация: 17.02.2014
Сообщений: 947
19.02.2016, 20:47  [ТС]
Цитата Сообщение от Ромаха Посмотреть сообщение
Если лабиринт вы представляете как граф с m рёбрами - то да
Как считаете, такой код для данной задачи будет правильно работать?
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
type myArray = array[1..64] of integer;
 
function isWay( a, b: integer; ways: myArray ): boolean;
 
var i, c, d: integer; r: boolean; // возвращает true, если есть путь, false если нет пути
 
begin
 
i := 0;
 
while (true) do begin
 
inc(i);
 
c := ways[i];
 
if (c = 0) then break;
 
inc(i);
 
d := ways[i];
 
if (d = 0) then break;
 
if ( ( (a = c) and (b = d) ) or ( (a = c) and isWay(d, b, ways) ) ) then begin r := true; break; end else r := false;
 
end;
 
isWay := r;
 
end;
 
var i, a, b: integer; ways: myArray;
 
begin
 
i := 0;
 
while (true) do begin
 
inc(i);
 
readln(ways[i]);
 
if (ways[i] = 0) then break;
 
inc(i);
 
readln(ways[i]);
 
if (ways[i] = 0) then break;
 
end;
 
readln(a, b);
 
if (isWay(a, b, ways)) then writeln('Путь есть!') else writeln('Пути нет!');
 
end.
0
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8675 / 4512 / 1670
Регистрация: 01.02.2015
Сообщений: 13,942
Записей в блоге: 13
20.02.2016, 18:50
А расскажите, что и каким образом делает этот код.
0
11 / 11 / 2
Регистрация: 17.02.2014
Сообщений: 947
29.02.2016, 10:33  [ТС]
Цитата Сообщение от Catstail Посмотреть сообщение
- обход графа - это перебор каждой из его вершин ровно один раз. И в DFS и в BFS каждая вершина посещается только один раз.
А для чего вы использовали массив Chk для отметки. Можете рассказать о смысле данного массива и что он отмечает.

Добавлено через 5 минут
Ещё бы смысл данных выражений понять:
Pascal
1
2
3
4
if length(Path)=0 then
       Path:=inttostr(n)  
    else
       Path := Path + ';' +inttostr(n);
Если длина строки нулевая , то переводим строку в число, это для чего не понял.

Добавлено через 19 минут
А Можно ли вообще строку пути убрать из программы // знак вопроса не работает
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38210 / 21143 / 4313
Регистрация: 12.02.2012
Сообщений: 34,757
Записей в блоге: 14
29.02.2016, 11:31
Цитата Сообщение от jestero Посмотреть сообщение
А для чего вы использовали массив Chk для отметки
- для отметки номеров уже посещенных вершин
Цитата Сообщение от jestero Посмотреть сообщение
Ещё бы смысл данных выражений понять:
- в переменной Path находится список вершин, составляющих путь. Если Path пуста - просто кладем туда вершину, если нет - отделяем новую вершину точной с запятой.
Цитата Сообщение от jestero Посмотреть сообщение
А Можно ли вообще строку пути убрать из программы
-зачем?
1
11 / 11 / 2
Регистрация: 17.02.2014
Сообщений: 947
01.03.2016, 12:24  [ТС]
Спасибо. С этим разобрался.
А вот эта функция не подскажете для чего?
Pascal
1
2
3
4
5
6
7
8
9
10
Function posRev(s : string; f : char) : integer;
Var i : integer;
Begin
    for i:=length(s) downto 1 Do
        if s[i]=f then begin
           posRev:=i;
           exit;
        end;
    posRev:=0;
End;
Если i-й элемент строки равен символу f, то функция возвращает номер этого элемента. Вы потом используете эту функцию:
Pascal
1
k:= posRev(Path, ';');
То есть она в данном случае ищет в строке точку с запятой и что с ней дальше делает?
И вот с последним моментом разобраться бы:
if (k >0) then Path:= copy(Path,1,(k-1)); Если предыдущая функция вернула значение больше нуля, то из строки начиная с первого символа копируется k-1 символов и полученное значение присваивается в строку. Можно немного поподробнее о фактическом смысле данного действия?
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38210 / 21143 / 4313
Регистрация: 12.02.2012
Сообщений: 34,757
Записей в блоге: 14
01.03.2016, 13:42
PosRev ищет первое вхождение символа f в строке s от конца. Т.е. ищется последняя ; и строка пути укорачивается отбрасыванием последней вершины.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
01.03.2016, 13:42

Определить, можно ли попасть по дорогам из 1-го пункта в n-ый
помогите. вообще не знаю как сделать 3. Имеется n населенных пунктов, пронумерованных от 1 до n (n=10). Некоторые пары пунктов соединены...

Определить, можно ли попасть по дорогам из l-того пункта в m-ый
Имеется n населенных пунктов, пронумерованных от 1 до n (n=10). Некоторые пары пунктов соединены дорогами. Определить, можно ли попасть...

Используя рекурсию, определить, можно ли по дорогам попасть из 1-го пункта в N-ый
Имеется 10 населенных пунктов. Дана последовательность пар чисел пар чисел I и J (I&lt;J), указывающих, что I –ый J-ый пункты соединены...

Определить, можно ли попасть по этим дорогам из l-того пункта в m-ый
1. Имеется n населенных пунктов, пронумерованных от 1 до n (n=10). Некоторые пары пунктов соединены дорогами. Определить, можно ли...

Используя рекурсию, определить, можно ли по этим дорогам попасть из 1-го пункта в N-ый
Помогите пожалуйста написать код. Вот задание: Имеется 10 населенных пунктов. Дана последовательность пар чисел пар чисел I и J...


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

Или воспользуйтесь поиском по форуму:
31
Ответ Создать тему
Новые блоги и статьи
Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему
Hrethgir 27.07.2026
То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .
тв 16 бой ии
anaschu 27.07.2026
Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк
anaschu 27.07.2026
НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .
Очистка реквизитов и табличных частей документа при копировании (вариант 2)
Maks 26.07.2026
Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .
Доктрина интенционального знания - Доктрина для портала "Срез".
Hrethgir 25.07.2026
Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых
anaschu 25.07.2026
Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил
anaschu 25.07.2026
две стороны одной монеты
Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад).
Hrethgir 24.07.2026
В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru