Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
Misha_prog
0 / 0 / 1
Регистрация: 15.04.2013
Сообщений: 184
1

Заменить рекусрию на стек

11.07.2015, 20:40. Просмотров 1269. Ответов 6
Метки нет (Все метки)

Всем привет! не получается заменить рекурсию на стек, изучаю по Т. Кормену Алгоритмы, читаю про поиск в глубину, там есть задание где нужно рекурсию заменить на стек
вот такой код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
dfs-visit(Graph g, Vertex u) {
      time ++;  //глобальная переменная
      u.d = time;
     u.color = COLOR::GRAY;
     for(auto v : G.adj[u]) {
          if (v.color == COLOR::WHITE) {
                   v.p = u;
                  dfs-visit(g, v); 
           }
     }
   u.color=  COLOR::BLACK;
   time++;
   u.f = time;
}
Всем Спасибо за внимание и за помощь!!!
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2015, 20:40
Ответы с готовыми решениями:

Стек: найти минимальный элемент и заменить на 0
Создать стек со случайными целыми числами. Найти минимальный элемент и вставить на его место 0

Создать стек, вычислить его среднее арифметическое и заменить им первый элемент.
Написать программу по созданию, добавлению, просмотру и решению поставленной задачи для...

Как используя стек, заменить все отрицательные элементы файла на их абсолютные значения
Как используя стэк, написать процедуру или функцию, которая заменяет все отрицательные элементы...

создать стек,заполнив числами 1,2,3...n.Посмотреть его содержимое,удалить стек
Всем привет!помогите,пожалуйста!!! создать стек,заполнив числами 1,2,3...n.Посмотреть его...

Заполнить очередь и стек и поменять их содержимое местами через дополнительный стек.
Необходимо разработать программу, которая должна : Заполнить очередь и стек и поменять их...

6
Shamil1
Модератор
2510 / 1715 / 379
Регистрация: 26.03.2015
Сообщений: 6,254
11.07.2015, 23:02 2
Я собираюсь использовать вот такие типы данных:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
enum Color
{
    White,
    Gray,
    Black
}
 
class Vertex
{
    public Color Color;
    public int Left;
    public int Right;
    public Vertex Predecessor;
    public List<Vertex> Adj;
}
Вот рекурсивный код (аналогичный Вашему):
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
void DfsVisit(Vertex u)
{
    u.Color = Color.Gray;
    u.Left = time++;
    foreach(Vertex v in u.Adj)
        if(v.Color == Color.White)
        {
            v.Predecessor = u;
            DfsVisit(v);
        }
    u.Color = Color.Black;
    u.Right = time++;
}
А вот что получается, если убрать рекурсию:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void DfsVisit2(Vertex u)
{
    while(u != null)
    {
        if(u.Color == Color.White)
        {
            u.Color = Color.Gray;
            u.Left = time++;
        }
        // ищем следующего (любого) необработанного ребёнка
        Vertex v = u.Adj.Where(x => x.Color == Color.White).FirstOrDefault();
        if(v != null)
        {
            v.Predecessor = u;
            u = v;
            continue; // обрабатываем ребёнка
        }
        // нет больше детей, заканчиваем обработку этой вершины
        u.Color = Color.Black;
        u.Right = time++;
        // возвращаемся к обработке родителя этой вершины
        u = u.Predecessor;
    }
}
з.ы. Свой код я не запускал, так что возможно в нём есть какие-то ошибки/опечатки.
2
Igor3D
1229 / 596 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
12.07.2015, 12:33 3
А что это за язык? Если плюсы то где возвращаемое ф-цией значение, что за минус в имени? Или уже вышел какой-то новый стандарт где "и так можно"? Что за резвая передача Graph по значению - хз. Я понял что разговор идет об "общей схеме" замены рекурсии, в детали вникать не нужно. Если так то все довольно просто.

1) Место рекурсивного вызова заменяем на операцию типа "push"
C++
1
2
3
4
5
if (v.color == COLOR::WHITE) {
//   v.p = u;
//   dfs-visit(g, v); 
  candidates.push_back(v);
}
2) саму ф-цию вставляем в цикл, напр
C++
1
2
3
4
5
while (candidates.size()) {
  Vertex v = candidates.back().v;  
  candidates.pop_back();
  dfs-visit(g, v);
}
Ну и перед этим поместить хотя бы 1 эл-т на стек (candidates)

Не по теме:

Все-таки от абстрактных примеров толку немного

1
Catstail
Модератор
25534 / 13133 / 2467
Регистрация: 12.02.2012
Сообщений: 21,499
13.07.2015, 13:12 4
Лучший ответ Сообщение было отмечено Misha_prog как решение

Решение

Поиск в глубину на стеке реализуется так:

1) поместить в стек стартовую вершину и отметить ее как посещенную
2) стек пуст - конец
3) если у вершины стека все соседи уже посещались - pop и на п.2
4) взять любую непосещенную вершину, связанную ребром с вершиной стека, отметить как посещенную, поместить в стек и на п.2
1
MichaelL
3 / 3 / 4
Регистрация: 19.02.2014
Сообщений: 12
17.07.2015, 10:19 5
Цитата Сообщение от Igor3D Посмотреть сообщение
А что это за язык?
C#. И это даже написано в шапке листинга - "Код C#"
0
Shamil1
Модератор
2510 / 1715 / 379
Регистрация: 26.03.2015
Сообщений: 6,254
17.07.2015, 15:36 6
Цитата Сообщение от MichaelL Посмотреть сообщение
C#. И это даже написано в шапке листинга - "Код C#"
Вообще-то, в шапке кода написано "Код С++". А вопросы связаны с тем, что приведённый код не является корректным С++ кодом ("где возвращаемое ф-цией значение, что за минус в имени").
1
MichaelL
3 / 3 / 4
Регистрация: 19.02.2014
Сообщений: 12
17.07.2015, 17:27 7
Цитата Сообщение от Shamil1 Посмотреть сообщение
Вообще-то, в шапке кода написано "Код С++". А вопросы связаны с тем, что приведённый код не является корректным С++ кодом ("где возвращаемое ф-цией значение, что за минус в имени").
Каюсь, не туда посмотрел.
1
17.07.2015, 17:27
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.07.2015, 17:27

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Стек. Создать случайно генерированный стек и поменять местами первый элемент с i
Как создать случайно генерированный стек (тип элементов CHAR) и поменять местами первый элемент с i...

Используя стек, описать функцию проверяющую, является ли стек пустым
Используя стек, описать функцию проверяющую, является ли стек пустым

Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами
Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами ...


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

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

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