лабиринт

@Solka · Регистрация: 02.10.2010

Студворк — интернет-сервис помощи студентам

Коридорами лабиринта разрешается двигаться только в направлениях, указанных стрелками. Человек вошел в комнату A и, выбирая случайным образом коридоры, пытается выйти через комнату D. Определите все возможные маршруты, при которых не более чем за семь переходов человек достигнет цели. Вычислите количество соответствующих маршрутов длиной три перехода, пять, семь, (2 * n 1) переходов.
мне б идейку...

@Mayonez · 04.01.2011, 19:28

граф....

valeriikozlov · 04.01.2011, 19:57

Solka, На миниатюре из точки B в точку С два перехода. Эти переходы различной длинны? Или что-то другое обозначают?

@Solka · 04.01.2011, 20:30 **[ТС]**

я думаю, что здесь не имеет значения какой длины, их можна было б разместить по другому...Ето просто 2 различные дороги, по которым можна двигаться.
например, для количества соответствующих маршрутов длиной три перехода можна идти так
A-B1-C-D или A-B2-C-D

@ViviSex&I · 04.01.2011, 20:39

Вот через матрицу смежности:
http://www.intuit.ru/departmen... html#sect3

@Solka · 04.01.2011, 20:50 **[ТС]**

незнаю, но мне кажется, что через матрицу смежности можно лишь задать вид графа, но как посчитать при этом количество маршрутов, у меня пока не укладывается

@ViviSex&I · 04.01.2011, 20:58

Сообщение от Solka

незнаю, но мне кажется, что через матрицу смежности можно лишь задать вид графа, но как посчитать при этом количество маршрутов, у меня пока не укладывается

Матрица смежности - пути длиной 1. Возведя матрицу смежности в степень (n) получаем маршруты длиной (n). По-моему в ссылке что я дал это было.

valeriikozlov · 04.01.2011, 21:16

Для графа с циклами (в том числе и для приведенного на рисунке) кол-во маршрутов бесконечно. Но не бесконечно число маршрутов определенной длины (по кол-ву переходов).
Если задавать определенное кол-во переходов, то есть один вариант как посчитать кол-во маршрутов.
В общем идейку могу подкинуть.

@ViviSex&I · 04.01.2011, 21:20

кол-во маршрутов длиной меньше (n) - Сумма сумм эл-тов матрицы смежности для каждой степени до (n)

@Solka · 05.01.2011, 00:16 **[ТС]**

для этого варианта нужно матрицу смежности? До valeriikozlov...напишите пожалуйста..=))

valeriikozlov · 05.01.2011, 00:32

Сначало два вопроса:
- знакомы ли Вы с графами, матрицами смежности?
- допустим задано кол-во переходов равное 3. Считаем что при каждом переходе человек двигается, или он может при каком-то переходе остаться на месте?

@Solka · 05.01.2011, 11:22 **[ТС]**

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

valeriikozlov · 05.01.2011, 17:21

Solka, Тогда сначало опишу алгоритм, потом если будут вопросы, спрашивайте, отвечу.
Итак создаем матрицу смежности matr_sm[n][n], где n - количество вершин.
Например matr_sm[i][j]=0, это значит что из вершины i в вершину j нет перехода (ребра)
Например matr_sm[i][j]=1, это значит что из вершины i в вершину j есть один переход (ребро)
Например matr_sm[i][j]=2, это значит что из вершины i в вершину j есть два перехода (ребра)
и т.д.
Далее создаем два массива размерностью n (например mas1[n] и mas2[n]). Оба массива обнуляем, и в первом массиве по индексу начальной вершины ставим значение 1.
Далее алгоритм такой (переход первый):
1. Делаем так:

C++
1
2
3
for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
        mas2[j]+=mas1[i]*matr_sm[i][j];

2. После этого все значения из массива mas2[n] переносим в массив mas1[n] (именно переносим заменяя существующие значения в массиве mas1[n], а не добавляя их к существующим уже значениям).
3. Обнуляем массив mas2[n].
Далее переход второй, начинаем опять с п.1 по п.3.
Далее переход третий, начинаем опять с п.1 по п.3.
И т.д.
После выполнения этих действий для нужного нам количества переходов ответ находится в mas1[n] по индексу, соответствующему номеру выходной вершины.

@Solka · 05.01.2011, 20:08 **[ТС]**

valeriikozlov, вопрос: как работает цикл....

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
mas2[j]+=mas1[i]*matr_sm[i][j];

ведь матрица смежности ровна
0 1 0 0
1 0 2 0
0 1 0 1
0 0 0 0

и все работает....))

valeriikozlov · 05.01.2011, 21:07

Solka, Если честно не очень понял вопроса.
Сам задам несколько:
- Все работает как и должно?
- Нужно объяснить сам алгоритм вычисления количества маршрутов?

@Solka · 05.01.2011, 21:43 **[ТС]**

так все хорошо
я так поняла, что суть программы - это цикл который я выделила ... да; как исчисляется количество маршрутов =)

valeriikozlov · 05.01.2011, 22:03

Смысл здесь такой:
Если после X переходов мы можем попасть Y вариантами в вершину A. То после X+1 перехода в вершину B только из вершины A мы можем попасть Y*matr_sm[A][B] вариантами.
В вершину B может быть можно попасть и из других вершин за X+1 переход. Для этого и осуществляем цикл:

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
mas2[j]+=mas1[i]*matr_sm[i][j];

Здесь как бы накапливаются значения в mas2[][] для вершины B (и для других вершин тоже) из всех вершин.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Solka 4 / 3 / 0 Регистрация: 02.10.2010 Сообщений: 20

	лабиринт 04.01.2011, 18:44. Показов 4121. Ответов 16 Метки нет (Все метки) Коридорами лабиринта разрешается двигаться только в направлениях, указанных стрелками. Человек вошел в комнату A и, выбирая случайным образом коридоры, пытается выйти через комнату D. Определите все возможные маршруты, при которых не более чем за семь переходов человек достигнет цели. Вычислите количество соответствующих маршрутов длиной три перехода, пять, семь, (2 * n 1) переходов. мне б идейку... Миниатюры 0

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874
	04.01.2011, 19:28
	граф.... 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	04.01.2011, 19:57
	Solka, На миниатюре из точки B в точку С два перехода. Эти переходы различной длинны? Или что-то другое обозначают? 1

@Solka 4 / 3 / 0 Регистрация: 02.10.2010 Сообщений: 20
	04.01.2011, 20:30 [ТС]
	я думаю, что здесь не имеет значения какой длины, их можна было б разместить по другому...Ето просто 2 различные дороги, по которым можна двигаться. например, для количества соответствующих маршрутов длиной три перехода можна идти так A-B1-C-D или A-B2-C-D 0

@ViviSex&I 0 / 0 / 0 Регистрация: 28.12.2010 Сообщений: 9
	04.01.2011, 20:39
	Вот через матрицу смежности: http://www.intuit.ru/departmen... html#sect3 0

@Solka 4 / 3 / 0 Регистрация: 02.10.2010 Сообщений: 20
	04.01.2011, 20:50 [ТС]
	незнаю, но мне кажется, что через матрицу смежности можно лишь задать вид графа, но как посчитать при этом количество маршрутов, у меня пока не укладывается 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	04.01.2011, 21:16
	Для графа с циклами (в том числе и для приведенного на рисунке) кол-во маршрутов бесконечно. Но не бесконечно число маршрутов определенной длины (по кол-ву переходов). Если задавать определенное кол-во переходов, то есть один вариант как посчитать кол-во маршрутов. В общем идейку могу подкинуть. 0

@ViviSex&I 0 / 0 / 0 Регистрация: 28.12.2010 Сообщений: 9
	04.01.2011, 21:20
	кол-во маршрутов длиной меньше (n) - Сумма сумм эл-тов матрицы смежности для каждой степени до (n) 0

@Solka 4 / 3 / 0 Регистрация: 02.10.2010 Сообщений: 20
	05.01.2011, 00:16 [ТС]
	для этого варианта нужно матрицу смежности? До valeriikozlov...напишите пожалуйста..=)) 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	05.01.2011, 00:32
	Сначало два вопроса: - знакомы ли Вы с графами, матрицами смежности? - допустим задано кол-во переходов равное 3. Считаем что при каждом переходе человек двигается, или он может при каком-то переходе остаться на месте? 0

@Solka 4 / 3 / 0 Регистрация: 02.10.2010 Сообщений: 20
	05.01.2011, 11:22 [ТС]
	я знаю как ее записывать, это не проблема думаю, что должен двигаться при каждом переходе 0

@Solka 4 / 3 / 0 Регистрация: 02.10.2010 Сообщений: 20
	05.01.2011, 20:08 [ТС]
	valeriikozlov, вопрос: как работает цикл.... for(int i=0; i<n; i++) for(int j=0; j<n; j++) mas2[j]+=mas1[i]*matr_sm[i][j]; ведь матрица смежности ровна 0 1 0 0 1 0 2 0 0 1 0 1 0 0 0 0 и все работает....)) 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	05.01.2011, 21:07
	Solka, Если честно не очень понял вопроса. Сам задам несколько: - Все работает как и должно? - Нужно объяснить сам алгоритм вычисления количества маршрутов? 0

@Solka 4 / 3 / 0 Регистрация: 02.10.2010 Сообщений: 20
	05.01.2011, 21:43 [ТС]
	так все хорошо я так поняла, что суть программы - это цикл который я выделила ... да; как исчисляется количество маршрутов =) 0