понять рекурсию

@jambas92 · Регистрация: 18.11.2010

Author24 — интернет-сервис помощи студентам

Здравствуйте! Хочу понять рекурсию

для этого хочу реализовать рекурсивный выход из лабиринта. точка (.) можно ходить, решетка (#) стена, g это выход.
из начало вводится 2 цифры, это размерности символьного массива, затем вводится сам массив, затем вводится 2 цифры, это координаты начала.
например
3 3
. . .
# # .
# # g
выход есть

вот что я по пробовал сделать...

C++

#include <iostream>
using namespace std;
 
bool boolean = false;
char mas[100][100];
 
int mouse(int x, int y)
{
    if (boolean == false)
    {
        if (mas[x][y] == 'G' || mas[x][y] == 'g')
        {
            boolean = true;
            return 0;
        }
        if (mas[x+1][y] == '.')
        {
            mouse(x+1, y);
        }
        if (mas[x][y+1] == '.')
        {
            mouse(x, y+1);
        }
        if (mas[x-1][y] == '.')
        {
            mouse(x-1, y);
        }
        if (mas[x][y-1] == '.')
        {
            mouse(x, y-1);
        }
    }
    else
    {
        boolean = true;
        return 0;
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
 
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            cin >> mas[i][j];
        }
    }
    
    int x, y;
    cin >> x >> y;
    mouse(x,y);
 
    boolean == true ? cout << "Yes\n" : cout << "No\n";
 
    return 0;
}

в чем я ошибаюсь?

@Kuzia domovenok · 26.03.2012, 21:46

Сообщение от jambas92

Здравствуйте!
в чем я ошибаюсь?

Существуют готовые хорошие алгоритмы поиска пути. На ум приходит А*, Волновой алгоритм и.т.д.
Сам я их подзабыл уже. Вот про них погугли и на них ориентируйся.
А твоя самодеятельность похвальна , но работать на будет, просто потому что
в такой ситуации он будет ходить взад-вперёд
*****
. . И .*
*****
И -игрок
Вызов mouse в первый раз будет советовать игроку сделать шаг вправо после первой же проверки, тем самым заводя в тупик.
Следующий вызов выведет его из тупика на 1 шаг влево в прежнее положение, из которого бесконечно будет отправлять в тупик.

@jambas92 · 26.03.2012, 21:51 **[ТС]**

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

на одном форуме нашел хороший ответ, но не могу его реализовать...

в общем объясню на словах, писать код времени нет:
как надо организовать функцию. на входе она получает 2 параметра: x; y.
первое действие проверяем флаг. если он false то проверяем явлются ли наши x и y концами (искомый выход) если да то флаг тру и выходим иначе делаем следующее, объясню для одной стороны для других аналогично
если a[x+1][y] == 0 то a[x][y] = 2; poisk(x+1, y); a[x][y] = 0;
т.е. когда начинаем рекурсию отмечаем пройденную клетку а когда возвращаемся сбрасываем ее.

@Kuzia domovenok · 26.03.2012, 22:09

если a[x+1][y] == 0 то a[x][y] = 2;

Ну и где у тебя этот момент в алгоритме? нету?
И ещё, что такое boolean? Т.е. Какую роль эта переменная играет в алгоритме?

@jambas92 · 26.03.2012, 22:20 **[ТС]**

Сообщение от Kuzia domovenok

если a[x+1][y] == 0 то a[x][y] = 2;

а куда вот его ставить та?

@Kuzia domovenok · 26.03.2012, 22:37

Сообщение от jambas92

а куда вот его ставить та?

Прочитай ещё раз:

в общем объясню на словах, писать код времени нет:
как надо организовать функцию. на входе она получает 2 параметра: x; y.
первое действие проверяем флаг. если он false то проверяем явлются ли наши x и y концами (искомый выход) если да то флаг тру и выходим иначе делаем следующее, объясню для одной стороны для других аналогично
если a[x+1][y] == 0 то a[x][y] = 2; poisk(x+1, y); a[x][y] = 0;
т.е. когда начинаем рекурсию отмечаем пройденную клетку а когда возвращаемся сбрасываем ее.

!!! если a[x+1][y] == 0 то a[x][y] = 2; poisk(x+1, y); a[x][y] = 0; !!!

C

if (mas[x+1][y] == '.')
                {
                        mas[x][y]='2';
                        mouse(x+1, y);
                        mas[x][y]='.';
                }
                if (mas[x][y+1] == '.')
                {      
                        mas[x][y]='2';
                        mouse(x, y+1);
                        mas[x][y]='.';
                }
                if (mas[x-1][y] == '.')
                {      
                        mas[x][y]='2';
                        mouse(x-1, y);
                        mas[x][y]='.';
                }
                if (mas[x][y-1] == '.')
                {
                        mas[x][y]='2';
                        mouse(x, y-1);
                        mas[x][y]='.';
                }

@jambas92 · 26.03.2012, 22:39 **[ТС]**

C++

if (mas[x+1][y] == '.')
        {
            mas[x+1][y]='#';
            mouse(x+1, y);
            mas[x+1][y]='.';
        }

типа вот так???

@Kuzia domovenok · 26.03.2012, 22:42

Сообщение от jambas92

C++

if (mas[x+1][y] == '.')
        {
            mas[x+1][y]='#';
            mouse(x+1, y);
            mas[x+1][y]='.';
        }

типа вот так???

Да! Да! Именно!
Только я ещё подумал, может mas[x+1][y]='#' ... mas[x+1][y]='.';
сделать общим для всех четырёх ифов?
Должно бы работать!

C++

mas[x+1][y]='#';
                if (mas[x+1][y] == '.') mouse(x+1, y);
                if (mas[x][y+1] == '.')mouse(x, y+1);
                if (mas[x-1][y] == '.') mouse(x-1, y);
                if (mas[x][y-1] == '.')  mouse(x, y-1);
mas[x+1][y]='.';

@jambas92 · 26.03.2012, 22:44 **[ТС]**

работает... прикольно

как говорится чтобы понять рекурсию нужно понять рекурсию...

@Kuzia domovenok · 26.03.2012, 22:49

Сообщение от jambas92

работает... прикольно

как говорится чтобы понять рекурсию нужно понять рекурсию...

Ну ты понял идею программы? Перед тем как пойти, скажем в правое ответвление лабиринта мы "заделываем" за собой дорогу. И так постепенно углубляемся, либо пока не оказываемся замурованными в тупике, тогда размуровываемся; шаг назад; и пробуем другое ответвление (например левое)

либо пока не найдём выход.

Вообще, отмечай дорогу не символами стен "#", а какими-нибудь специальными, например "@". Тогда когда отыщешь выход, в массиве будет "прочерчен" твой маршрут - и можно будет наглядно вывести на экран.

C++

if (mas[x+1][y] == '.')
        {
            mas[x+1][y]='@';
            mouse(x+1, y);
            mas[x+1][y]='.';
        }

@Kuzia domovenok 4063 / 3317 / 924 Регистрация: 25.03.2012 Сообщений: 12,485 Записей в блоге: 1
	26.03.2012, 21:46	2
	Сообщение от jambas92 Здравствуйте! в чем я ошибаюсь? Существуют готовые хорошие алгоритмы поиска пути. На ум приходит А, Волновой алгоритм и.т.д. Сам я их подзабыл уже. Вот про них погугли и на них ориентируйся. А твоя самодеятельность похвальна , но работать на будет, просто потому что в такой ситуации он будет ходить взад-вперёд **** . . И .* ***** И -игрок Вызов mouse в первый раз будет советовать игроку сделать шаг вправо после первой же проверки, тем самым заводя в тупик. Следующий вызов выведет его из тупика на 1 шаг влево в прежнее положение, из которого бесконечно будет отправлять в тупик. 1

@jambas92 59 / 58 / 16 Регистрация: 18.11.2010 Сообщений: 315
	26.03.2012, 21:51 [ТС]	3
	волновую я знаю, и как методом правой руки тоже, и самым коротким способом определить есть из лабиринта выход или нет тоже могу, просто в тех алгоритмах нет рекурсий. Как я понял в моем алгоритме не хватает возврата назад. То есть, когда есть развилка ставим метку, и идем по первому условию, если условие не удачная то возвращаемся на метку, только как это сделать? на одном форуме нашел хороший ответ, но не могу его реализовать... в общем объясню на словах, писать код времени нет: как надо организовать функцию. на входе она получает 2 параметра: x; y. первое действие проверяем флаг. если он false то проверяем явлются ли наши x и y концами (искомый выход) если да то флаг тру и выходим иначе делаем следующее, объясню для одной стороны для других аналогично если a[x+1][y] == 0 то a[x][y] = 2; poisk(x+1, y); a[x][y] = 0; т.е. когда начинаем рекурсию отмечаем пройденную клетку а когда возвращаемся сбрасываем ее. 0

@Kuzia domovenok 4063 / 3317 / 924 Регистрация: 25.03.2012 Сообщений: 12,485 Записей в блоге: 1
	26.03.2012, 22:09	4
	если a[x+1][y] == 0 то a[x][y] = 2; Ну и где у тебя этот момент в алгоритме? нету? И ещё, что такое boolean? Т.е. Какую роль эта переменная играет в алгоритме? 1

@jambas92 59 / 58 / 16 Регистрация: 18.11.2010 Сообщений: 315
	26.03.2012, 22:20 [ТС]	5
	Сообщение от Kuzia domovenok если a[x+1][y] == 0 то a[x][y] = 2; а куда вот его ставить та? 0

@jambas92 59 / 58 / 16 Регистрация: 18.11.2010 Сообщений: 315
	26.03.2012, 22:44 [ТС]	9
	работает... прикольно как говорится чтобы понять рекурсию нужно понять рекурсию... 0

	26.03.2012, 22:49

Опции темы