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

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

Восстановить пароль Регистрация
 
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
26.03.2012, 21:26     понять рекурсию #1
Здравствуйте! Хочу понять рекурсию для этого хочу реализовать рекурсивный выход из лабиринта. точка (.) можно ходить, решетка (#) стена, g это выход.
из начало вводится 2 цифры, это размерности символьного массива, затем вводится сам массив, затем вводится 2 цифры, это координаты начала.
например
3 3
. . .
# # .
# # g
выход есть

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

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}
в чем я ошибаюсь?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2012, 21:26     понять рекурсию
Посмотрите здесь:

Постигая рекурсию. C++
Задачка на рекурсию... C++
Задача на рекурсию C++
C++ Задача на рекурсию
Задача на рекурсию C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
26.03.2012, 21:46     понять рекурсию #2
Цитата Сообщение от jambas92 Посмотреть сообщение
Здравствуйте!
в чем я ошибаюсь?
Существуют готовые хорошие алгоритмы поиска пути. На ум приходит А*, Волновой алгоритм и.т.д.
Сам я их подзабыл уже. Вот про них погугли и на них ориентируйся.
А твоя самодеятельность похвальна , но работать на будет, просто потому что
в такой ситуации он будет ходить взад-вперёд
*****
. . И .*
*****
И -игрок
Вызов mouse в первый раз будет советовать игроку сделать шаг вправо после первой же проверки, тем самым заводя в тупик.
Следующий вызов выведет его из тупика на 1 шаг влево в прежнее положение, из которого бесконечно будет отправлять в тупик.
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 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;
т.е. когда начинаем рекурсию отмечаем пройденную клетку а когда возвращаемся сбрасываем ее.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
26.03.2012, 22:09     понять рекурсию #4
если a[x+1][y] == 0 то a[x][y] = 2;
Ну и где у тебя этот момент в алгоритме? нету?
И ещё, что такое boolean? Т.е. Какую роль эта переменная играет в алгоритме?
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
26.03.2012, 22:20  [ТС]     понять рекурсию #5
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
если a[x+1][y] == 0 то a[x][y] = 2;
а куда вот его ставить та?
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
26.03.2012, 22:37     понять рекурсию #6
Цитата Сообщение от 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
26.03.2012, 22:39  [ТС]     понять рекурсию #7
C++
1
2
3
4
5
6
if (mas[x+1][y] == '.')
        {
            mas[x+1][y]='#';
            mouse(x+1, y);
            mas[x+1][y]='.';
        }
типа вот так???
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
26.03.2012, 22:42     понять рекурсию #8
Цитата Сообщение от jambas92 Посмотреть сообщение
C++
1
2
3
4
5
6
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++
1
2
3
4
5
6
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
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
26.03.2012, 22:44  [ТС]     понять рекурсию #9
работает... прикольно как говорится чтобы понять рекурсию нужно понять рекурсию...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.03.2012, 22:49     понять рекурсию
Еще ссылки по теме:

Задача на рекурсию C++
Стек на основе массива структур - эт как понять читаю литературу и не могу понять! C++
Реализовать рекурсию C++

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

Или воспользуйтесь поиском по форуму:
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
26.03.2012, 22:49     понять рекурсию #10
Цитата Сообщение от jambas92 Посмотреть сообщение
работает... прикольно как говорится чтобы понять рекурсию нужно понять рекурсию...
Ну ты понял идею программы? Перед тем как пойти, скажем в правое ответвление лабиринта мы "заделываем" за собой дорогу. И так постепенно углубляемся, либо пока не оказываемся замурованными в тупике, тогда размуровываемся; шаг назад; и пробуем другое ответвление (например левое)

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

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

C++
1
2
3
4
5
6
if (mas[x+1][y] == '.')
        {
            mas[x+1][y]='@';
            mouse(x+1, y);
            mas[x+1][y]='.';
        }
Yandex
Объявления
26.03.2012, 22:49     понять рекурсию
Ответ Создать тему
Опции темы

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