Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/16: Рейтинг темы: голосов - 16, средняя оценка - 4.75
4 / 3 / 0
Регистрация: 02.10.2010
Сообщений: 20
1

лабиринт

04.01.2011, 18:44. Показов 3084. Ответов 16
Метки нет (Все метки)

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

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Миниатюры
лабиринт  
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.01.2011, 18:44
Ответы с готовыми решениями:

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

Лабиринт с++
Есть код. только мне не понятен алгоритм который работает в bool PathExists(Labyrinth& lab, int...

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

Лабиринт
#include <iostream> #include <fstream> #include <conio.h> #include <time.h> #include <cmath>...

16
390 / 282 / 53
Регистрация: 26.12.2009
Сообщений: 875
04.01.2011, 19:28 2
граф....
0
Эксперт С++
4717 / 2538 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
04.01.2011, 19:57 3
Solka, На миниатюре из точки B в точку С два перехода. Эти переходы различной длинны? Или что-то другое обозначают?
1
4 / 3 / 0
Регистрация: 02.10.2010
Сообщений: 20
04.01.2011, 20:30  [ТС] 4
я думаю, что здесь не имеет значения какой длины, их можна было б разместить по другому...Ето просто 2 различные дороги, по которым можна двигаться.
например, для количества соответствующих маршрутов длиной три перехода можна идти так
A-B1-C-D или A-B2-C-D
0
0 / 0 / 0
Регистрация: 28.12.2010
Сообщений: 9
04.01.2011, 20:39 5
Вот через матрицу смежности:
http://www.intuit.ru/departmen... html#sect3
0
4 / 3 / 0
Регистрация: 02.10.2010
Сообщений: 20
04.01.2011, 20:50  [ТС] 6
незнаю, но мне кажется, что через матрицу смежности можно лишь задать вид графа, но как посчитать при этом количество маршрутов, у меня пока не укладывается
0
0 / 0 / 0
Регистрация: 28.12.2010
Сообщений: 9
04.01.2011, 20:58 7
Цитата Сообщение от Solka Посмотреть сообщение
незнаю, но мне кажется, что через матрицу смежности можно лишь задать вид графа, но как посчитать при этом количество маршрутов, у меня пока не укладывается
Матрица смежности - пути длиной 1. Возведя матрицу смежности в степень (n) получаем маршруты длиной (n). По-моему в ссылке что я дал это было.
0
Эксперт С++
4717 / 2538 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
04.01.2011, 21:16 8
Для графа с циклами (в том числе и для приведенного на рисунке) кол-во маршрутов бесконечно. Но не бесконечно число маршрутов определенной длины (по кол-ву переходов).
Если задавать определенное кол-во переходов, то есть один вариант как посчитать кол-во маршрутов.
В общем идейку могу подкинуть.
0
0 / 0 / 0
Регистрация: 28.12.2010
Сообщений: 9
04.01.2011, 21:20 9
кол-во маршрутов длиной меньше (n) - Сумма сумм эл-тов матрицы смежности для каждой степени до (n)
0
4 / 3 / 0
Регистрация: 02.10.2010
Сообщений: 20
05.01.2011, 00:16  [ТС] 10
для этого варианта нужно матрицу смежности? До valeriikozlov...напишите пожалуйста..=))
0
Эксперт С++
4717 / 2538 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
05.01.2011, 00:32 11
Сначало два вопроса:
- знакомы ли Вы с графами, матрицами смежности?
- допустим задано кол-во переходов равное 3. Считаем что при каждом переходе человек двигается, или он может при каком-то переходе остаться на месте?
0
4 / 3 / 0
Регистрация: 02.10.2010
Сообщений: 20
05.01.2011, 11:22  [ТС] 12
я знаю как ее записывать, это не проблема
думаю, что должен двигаться при каждом переходе
0
Эксперт С++
4717 / 2538 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
05.01.2011, 17:21 13
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] по индексу, соответствующему номеру выходной вершины.
1
4 / 3 / 0
Регистрация: 02.10.2010
Сообщений: 20
05.01.2011, 20:08  [ТС] 14
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
Эксперт С++
4717 / 2538 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
05.01.2011, 21:07 15
Solka, Если честно не очень понял вопроса.
Сам задам несколько:
- Все работает как и должно?
- Нужно объяснить сам алгоритм вычисления количества маршрутов?
0
4 / 3 / 0
Регистрация: 02.10.2010
Сообщений: 20
05.01.2011, 21:43  [ТС] 16
так все хорошо
я так поняла, что суть программы - это цикл который я выделила ... да; как исчисляется количество маршрутов =)
0
Эксперт С++
4717 / 2538 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
05.01.2011, 22:03 17
Смысл здесь такой:
Если после 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 (и для других вершин тоже) из всех вершин.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.01.2011, 22:03

лабиринт
дан лабиринт размером NxN. форма лабиринта записана в тектовом файле. стена обозначается М. даны...

Лабиринт
Помогите пожалуйста: Создать игру «Лабиринт». Игра состоит из 2 уровней (лабиринтов),...

Лабиринт
Всем привет. Подскажите, вот делаю игру (понятно какую) но проблема. Вот код #include &quot;stdafx.h&quot;...

Лабиринт
Народ помогите! есть задание: Лабиринт представляет собой квадрат, состоящий из NxN сегментов....


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

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

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