Форум программистов, компьютерный форум CyberForum.ru

лабиринт - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
Solka
4 / 3 / 1
Регистрация: 02.10.2010
Сообщений: 20
04.01.2011, 18:44     лабиринт #1
Коридорами лабиринта разрешается двигаться только в направлениях, указанных стрелками. Человек вошел в комнату A и, выбирая случайным образом коридоры, пытается выйти через комнату D. Определите все возможные маршруты, при которых не более чем за семь переходов человек достигнет цели. Вычислите количество соответствующих маршрутов длиной три перехода, пять, семь, (2 * n 1) переходов.
мне б идейку...
Миниатюры
лабиринт  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.01.2011, 18:44     лабиринт
Посмотрите здесь:

Лабиринт C++
C++ Лабиринт
Лабиринт C++
Лабиринт с++ C++
Лабиринт с телепортами на C++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
04.01.2011, 19:28     лабиринт #2
граф....
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.01.2011, 19:57     лабиринт #3
Solka, На миниатюре из точки B в точку С два перехода. Эти переходы различной длинны? Или что-то другое обозначают?
Solka
4 / 3 / 1
Регистрация: 02.10.2010
Сообщений: 20
04.01.2011, 20:30  [ТС]     лабиринт #4
я думаю, что здесь не имеет значения какой длины, их можна было б разместить по другому...Ето просто 2 различные дороги, по которым можна двигаться.
например, для количества соответствующих маршрутов длиной три перехода можна идти так
A-B1-C-D или A-B2-C-D
ViviSex&I
0 / 0 / 0
Регистрация: 28.12.2010
Сообщений: 9
04.01.2011, 20:39     лабиринт #5
Вот через матрицу смежности:
http://www.intuit.ru/department/algo...4/2.html#sect3
Solka
4 / 3 / 1
Регистрация: 02.10.2010
Сообщений: 20
04.01.2011, 20:50  [ТС]     лабиринт #6
незнаю, но мне кажется, что через матрицу смежности можно лишь задать вид графа, но как посчитать при этом количество маршрутов, у меня пока не укладывается
ViviSex&I
0 / 0 / 0
Регистрация: 28.12.2010
Сообщений: 9
04.01.2011, 20:58     лабиринт #7
Цитата Сообщение от Solka Посмотреть сообщение
незнаю, но мне кажется, что через матрицу смежности можно лишь задать вид графа, но как посчитать при этом количество маршрутов, у меня пока не укладывается
Матрица смежности - пути длиной 1. Возведя матрицу смежности в степень (n) получаем маршруты длиной (n). По-моему в ссылке что я дал это было.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.01.2011, 21:16     лабиринт #8
Для графа с циклами (в том числе и для приведенного на рисунке) кол-во маршрутов бесконечно. Но не бесконечно число маршрутов определенной длины (по кол-ву переходов).
Если задавать определенное кол-во переходов, то есть один вариант как посчитать кол-во маршрутов.
В общем идейку могу подкинуть.
ViviSex&I
0 / 0 / 0
Регистрация: 28.12.2010
Сообщений: 9
04.01.2011, 21:20     лабиринт #9
кол-во маршрутов длиной меньше (n) - Сумма сумм эл-тов матрицы смежности для каждой степени до (n)
Solka
4 / 3 / 1
Регистрация: 02.10.2010
Сообщений: 20
05.01.2011, 00:16  [ТС]     лабиринт #10
для этого варианта нужно матрицу смежности? До valeriikozlov...напишите пожалуйста..=))
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 00:32     лабиринт #11
Сначало два вопроса:
- знакомы ли Вы с графами, матрицами смежности?
- допустим задано кол-во переходов равное 3. Считаем что при каждом переходе человек двигается, или он может при каком-то переходе остаться на месте?
Solka
4 / 3 / 1
Регистрация: 02.10.2010
Сообщений: 20
05.01.2011, 11:22  [ТС]     лабиринт #12
я знаю как ее записывать, это не проблема
думаю, что должен двигаться при каждом переходе
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
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] по индексу, соответствующему номеру выходной вершины.
Solka
4 / 3 / 1
Регистрация: 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

и все работает....))
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 21:07     лабиринт #15
Solka, Если честно не очень понял вопроса.
Сам задам несколько:
- Все работает как и должно?
- Нужно объяснить сам алгоритм вычисления количества маршрутов?
Solka
4 / 3 / 1
Регистрация: 02.10.2010
Сообщений: 20
05.01.2011, 21:43  [ТС]     лабиринт #16
так все хорошо
я так поняла, что суть программы - это цикл который я выделила ... да; как исчисляется количество маршрутов =)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2011, 22:03     лабиринт
Еще ссылки по теме:

Лабиринт C++
C++ Игра Лабиринт
Лабиринт C++ C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
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 (и для других вершин тоже) из всех вершин.
Yandex
Объявления
05.01.2011, 22:03     лабиринт
Ответ Создать тему
Опции темы

Текущее время: 09:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru