Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
jambas92
59 / 58 / 16
Регистрация: 18.11.2010
Сообщений: 315
1

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

26.03.2012, 21:26. Просмотров 973. Ответов 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
Ответы с готовыми решениями:

Стек на основе массива структур - эт как понять читаю литературу и не могу понять!
Стек статически (на основе массива структур). Пример структура &quot;Товар&quot; которая...

Задача на рекурсию
Задание : Напишите функцию возведения в степень, которая работала бы как для...

Задача на рекурсию
Помогите решить след. задачу: Вот мой вариант, но здесь не сохраняется...

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

Задача на рекурсию
Дано натуральное число n. Выяснить, имеется ли среди чисел n, n+1, ..., 2n...

9
Kuzia domovenok
2327 / 2074 / 482
Регистрация: 25.03.2012
Сообщений: 7,397
Записей в блоге: 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
2327 / 2074 / 482
Регистрация: 25.03.2012
Сообщений: 7,397
Записей в блоге: 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
Kuzia domovenok
2327 / 2074 / 482
Регистрация: 25.03.2012
Сообщений: 7,397
Записей в блоге: 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
59 / 58 / 16
Регистрация: 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
2327 / 2074 / 482
Регистрация: 25.03.2012
Сообщений: 7,397
Записей в блоге: 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
59 / 58 / 16
Регистрация: 18.11.2010
Сообщений: 315
26.03.2012, 22:44  [ТС] 9
работает... прикольно как говорится чтобы понять рекурсию нужно понять рекурсию...
0
Kuzia domovenok
2327 / 2074 / 482
Регистрация: 25.03.2012
Сообщений: 7,397
Записей в блоге: 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
26.03.2012, 22:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.03.2012, 22:49

Программа на рекурсию
Задача о рюкзаке. В рюкзаке объёмом V содержится запас из N предметов. Для...

Задача на рекурсию
С помощью рекурсии вычислить произведение ненулевых элементов динамического...

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


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

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

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