Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
Solka
4 / 3 / 1
Регистрация: 02.10.2010
Сообщений: 20
#1

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

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

Коридорами лабиринта разрешается двигаться только в направлениях, указанных стрелками. Человек вошел в комнату A и, выбирая случайным образом коридоры, пытается выйти через комнату D. Определите все возможные маршруты, при которых не более чем за семь переходов человек достигнет цели. Вычислите количество соответствующих маршрутов длиной три перехода, пять, семь, (2 * n 1) переходов.
мне б идейку...
0
Миниатюры
лабиринт  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.01.2011, 18:44
Я подобрал для вас темы с готовыми решениями и ответами на вопрос лабиринт (C++):

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

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

Лабиринт - C++
Всем привет. Подскажите, вот делаю игру (понятно какую) но проблема. Вот код #include "stdafx.h" #include <iostream> using namespace...

Лабиринт - C++
#include <iostream> #include <fstream> #include <conio.h> #include <time.h> #include <cmath> #include <stdio.h> using...

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

Лабиринт - C++
Помогите пожалуйста: Создать игру «Лабиринт». Игра состоит из 2 уровней (лабиринтов), отличающихся по сложности. Лабиринты появляются...

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

и все работает....))
0
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 21:07 #15
Solka, Если честно не очень понял вопроса.
Сам задам несколько:
- Все работает как и должно?
- Нужно объяснить сам алгоритм вычисления количества маршрутов?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2011, 21:07
Привет! Вот еще темы с ответами:

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

Лабиринт - C++
Вообщем у меня 2 проблемы: 1) Либирнт генерирует 2 раза 2) '8' ходит как хочит Поправте плз код #include &lt;iostream&gt; #include...

Двумерный лабиринт - C++
Всем здраствуйте. Пожалуйста посоветуйте что-нибудь). Так же как и автор этой темы начал учить C++. Сам по книгам, это мой первый язык...

игра лабиринт - C++
Есть код игры Смайлик движется по лабиринту с помощью нажатия клавиш, есть два смайлика врага (один движется по вертикали, второй по...


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

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

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