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

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

Войти
Регистрация
Восстановить пароль
 
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
#1

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

26.03.2012, 21:26. Просмотров 917. Ответов 9
Метки нет (Все метки)

Здравствуйте! Хочу понять рекурсию для этого хочу реализовать рекурсивный выход из лабиринта. точка (.) можно ходить, решетка (#) стена, 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;
}
в чем я ошибаюсь?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2012, 21:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос понять рекурсию (C++):

Стек на основе массива структур - эт как понять читаю литературу и не могу понять! - C++
Стек статически (на основе массива структур). Пример структура &quot;Товар&quot; которая включает в себя: № по каталогу(ключ), Название, цена, срок...

Задача на рекурсию - C++
С помощью рекурсии вычислить произведение ненулевых элементов динамического массива. Кто-то знает? Вот такой вот фрагмент есть, но он...

Задача на рекурсию - C++
Дано число. Вывести все цифры этого числа, не используя дополнительных библиотек, массивов, списков и т.д. Использовать только...

Задача на рекурсию - C++
Дано натуральное число n. Выяснить, имеется ли среди чисел n, n+1, ..., 2n близнецы, т.е. простые числа, разность между которыми равна...

Поясните за рекурсию - C++
Учу язык на одном из сайтов, столкнулся с таким примером программы с рекурсией: рекурсия в C++C++ #include &lt;iostream&gt; using...

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

9
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
26.03.2012, 21:46 #2
Цитата Сообщение от jambas92 Посмотреть сообщение
Здравствуйте!
в чем я ошибаюсь?
Существуют готовые хорошие алгоритмы поиска пути. На ум приходит А*, Волновой алгоритм и.т.д.
Сам я их подзабыл уже. Вот про них погугли и на них ориентируйся.
А твоя самодеятельность похвальна , но работать на будет, просто потому что
в такой ситуации он будет ходить взад-вперёд
*****
. . И .*
*****
И -игрок
Вызов mouse в первый раз будет советовать игроку сделать шаг вправо после первой же проверки, тем самым заводя в тупик.
Следующий вызов выведет его из тупика на 1 шаг влево в прежнее положение, из которого бесконечно будет отправлять в тупик.
1
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;
т.е. когда начинаем рекурсию отмечаем пройденную клетку а когда возвращаемся сбрасываем ее.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
26.03.2012, 22:09 #4
если a[x+1][y] == 0 то a[x][y] = 2;
Ну и где у тебя этот момент в алгоритме? нету?
И ещё, что такое boolean? Т.е. Какую роль эта переменная играет в алгоритме?
1
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;
а куда вот его ставить та?
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 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]='.';
                }
1
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]='.';
        }
типа вот так???
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 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]='.';
1
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
26.03.2012, 22:44  [ТС] #9
работает... прикольно как говорится чтобы понять рекурсию нужно понять рекурсию...
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 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]='.';
        }
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.03.2012, 22:49
Привет! Вот еще темы с ответами:

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

Задача на рекурсию - C++
Всем доброго времени суток. Прошу подсказать мне условие задачи на рекурсию(нам дали задание самим придумать себе задание и выполнить...

Не входит в рекурсию - C++
есть задача, где надо вывести правильные варианты... правильные варианты это 0000 1010 0010 1101 и т.п. Консоль выводит...

Задачка на рекурсию... - C++
в общем нужно сделать прогу чтоб выводила дерево файлов и папок указанной директории.... Сделать это надо с помощью рекурсии... ...


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

Или воспользуйтесь поиском по форуму:
10
Yandex
Объявления
26.03.2012, 22:49
Ответ Создать тему
Опции темы

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