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

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

Войти
Регистрация
Восстановить пароль
 
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
#1

графы. поиск в глубину - C++

04.07.2013, 14:23. Просмотров 1135. Ответов 11
Метки нет (Все метки)

Здраствуйте. Вот такая задача
N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i, j), 1≤ i < j ≤ N (шестеpня с номеpом i находится в зацеплении с шестеpней j). Можно ли повеpнуть шестеpню с номеpом 1?
Если да, то найти количество шестеpен, пpишедших в движение.
Если нет, то тpебуется убpать минимальное число шестеpен так, чтобы в оставшейся системе пpи вpащении шестеpни 1 во вpащение пpишло бы максимальное число шестеpен. Указать номеpа убpанных шестеpен ( если такой набоp не один, то любой из них ) и количество шестеpен, пpишедших в движение.


помогите решить, хотя бы частично с поиском в глубину и соответственно проверкой вращения шестеренок(каждая шестеренка заставляет крутиться следующую в противоположную сторону, то есть при наличии нечетных циклов система встанет)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2013, 14:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос графы. поиск в глубину (C++):

Поиск в глубину. Графы. С++ - C++
Задана ,допустим, такая матрица смежности 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 Node.h #pragma once

графы,поиск в глубину - C++
очень нужна помощь!нужно в неориентированном графе найти компоненты связности поиском в глубину. Есть готовый алгоритм поиска,из...

поиск в глубину - C++
Дали задание реализовать поиск в глубину.Пробую релизовать по e-maxx http://e-maxx.ru/algo/dfsно не получается. vector&lt;char&gt; used; int...

Поиск в глубину - C++
Помогите с заданием пожалуйста. Число 1 можно записать как сумму n чисел вида 1 / i, где i - натуральное число. Например, для n = 3 имеем...

Поиск в глубину - C++
&quot;В рождественскую ночь Санта-Клаус спускается по каминной трубе и раскладывает детям подарки. Кровати в комнате стоят очень плотно. Чтобы...

Поиск в глубину - C++
Здравствуйте. Как реализовать поиск кратчайшего пути в невзвешенном графе через поиск в глубину? Пробовал сделать так const...

11
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
04.07.2013, 15:46 #2
на алголисте посмотрите алгоритмы.
0
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 16:11  [ТС] #3
Kukurudza, там к сожалению только в чистом виде поиск в глубину, а мне нужно чтобы можно было дважды проходить по вершинам
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
04.07.2013, 19:05 #4
хорошая задачка. подумайте, когда можно ее повернуть, а когда нет. это забавно)
0
svk2140
-8 / 0 / 1
Регистрация: 04.07.2013
Сообщений: 274
04.07.2013, 19:07 #5
ух у меня щяс мозги перегреются)
0
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 19:08  [ТС] #6
salam, я понимаю, что поворот идет либо когда нет цикла, либо когда он четен, то есть не будет того что нахлестнется одно направление на другое, у меня проблема с тем как просмотреть все элементы и в цикле не зациклится

Добавлено через 1 минуту
svk2140, а у меня второй день так( хотя вроде как продвигается но все равно ничего не работае
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
04.07.2013, 19:22 #7
Цитата Сообщение от Рехеана Посмотреть сообщение
salam, я понимаю, что поворот идет либо когда нет цикла, либо когда он четен, то есть не будет того что нахлестнется одно направление на другое, у меня проблема с тем как просмотреть все элементы и в цикле не зациклится
да, я думаю, именно это условие и нужно поставить. просто напишите правильно дфс. можете искать цикл просто так. если найдется, посмотреть, четный или нет. тут просто реализация грамотная нужна.
0
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 19:26  [ТС] #8
salam, вот с ней и проблема, не могу написать так чтобы в цикл проходило и чтобы это было так как это требует преподаватель, практика в универе идет, он совсем объяснять не хочет дал книжку там не очень понятно... а вы не могли бы помочь?
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
04.07.2013, 19:27 #9
Цитата Сообщение от Рехеана Посмотреть сообщение
и чтобы это было так как это требует преподаватель
я ведь наверняка знаю, чего он требует...
0
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 19:33  [ТС] #10
Прошу прощения торможу.

вот по этой методичке там алгоритм есть, а реализовано на си шарп.
и как бы там не учитываются циклы.
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
04.07.2013, 20:00 #11
не люблю я очень эти методички... прошу прощения. давайте подумаем. цикл можно найти так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int graph[SIZE][SIZE]; // матрица смежности
int color[SIZE];            // color[i] может принимать одно из трех значений {0, 1, 2}
                                 // 0 - вершина не была посещена,
                                 // 1 - мы зашли в нее, но еще не вышли,
                                 // 2 - мы уже вышли из этой вершины.
void dfs(int v) {
   color[v] = 1;                  // мы зашли в вершину v
   for(int i=0; i < SIZE; i++)
      if(i != v && graph[v][i] == true)
         if(color[i] == 1) {      // мы нашли цикл, так как пытаемся пойти из вершины 
                                      // с цветом 1 в вершину с цветом 1, то есть 
         }                           // в вершину, из которой еще не вышли
         else if(color[i] == 0)
                  dfs(i);
   color[v] = 2;
}
дальше можете делать с этим циклом, что угодно.

Добавлено через 4 минуты
вообще говоря, сейчас вы можете только определить, есть ли он. чтобы что-то делать непосредственно с ним, необходим массив предков.

Добавлено через 2 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int graph[SIZE][SIZE]; // матрица смежности
int par[SIZE];               // массив предков 
int color[SIZE];            // color[i] может принимать одно из трех значений {0, 1, 2}
                                 // 0 - вершина не была посещена,
                                 // 1 - мы зашли в нее, но еще не вышли,
                                 // 2 - мы уже вышли из этой вершины.
void dfs(int v) {
   color[v] = 1;                  // мы зашли в вершину v
   for(int i=0; i < SIZE; i++)
      if(i != v && graph[v][i] == true)
         if(color[i] == 1) {      // мы нашли цикл, так как пытаемся пойти из вершины 
                                      // с цветом 1 в вершину с цветом 1, то есть 
         }                           // в вершину, из которой еще не вышли
         else if(color[i] == 0) {
                  par[i] = v;   // мы называем вершину v предком вершины i, 
                                   // так как обход в глубину попал в i именно из v
                  dfs(i);
         }
   color[v] = 2;
}
Добавлено через 1 минуту
надеюсь, вам это все поможет.
0
Рехеана
0 / 0 / 0
Регистрация: 24.04.2013
Сообщений: 29
04.07.2013, 20:08  [ТС] #12
salam, спасибо
0
04.07.2013, 20:08
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.07.2013, 20:08
Привет! Вот еще темы с ответами:

Поиск в глубину - C++
Объясните плз поиск в глубину с примером. Сам много реалихаций нашел, но до конца не могу разобраться, может у кого есть примерчик хороший....

Рекурсивный поиск в глубину - C++
Нужно найти путь по простому лабиринту от точки к точке, используя в программе рекурсивный поиск в глубину. Фотографию примера лабиринта...

Итеративный поиск в глубину - C++
Здравствуйте! Вопрос связан с поиском в графе. Меня интересуют идеи решения или ссылка на литературу. Пожалуйста, подскажите... ...

Рекурсивный и нерекурсивный поиск в глубину - C++
Не уверен в правильности работы даной функции. Если начинать с вершины 2, то рекурсивный и нерекурсивный поиски дадут одинаковые...


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

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

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