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

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

09.02.2016, 16:20. Показов 3207. Ответов 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
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
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
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
17.02.2016, 19:59


Туз в кармане!
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38229 / 21161 / 4314
Регистрация: 12.02.2012
Сообщений: 34,783
Записей в блоге: 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
Модератор
Эксперт по электронике
 Аватар для ФедосеевПавел
8679 / 4516 / 1670
Регистрация: 01.02.2015
Сообщений: 13,963
Записей в блоге: 14
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
38229 / 21161 / 4314
Регистрация: 12.02.2012
Сообщений: 34,783
Записей в блоге: 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
38229 / 21161 / 4314
Регистрация: 12.02.2012
Сообщений: 34,783
Записей в блоге: 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
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru