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

Рекурсивная функция - C++

Восстановить пароль Регистрация
 
Ryk
0 / 0 / 0
Регистрация: 19.03.2012
Сообщений: 20
Завершенные тесты: 1
19.01.2013, 15:55     Рекурсивная функция #1
Здраствуйте, пытаюсь написать лабу для нахождения пути в лабиринте, выбрал волновой алгоритм Ли.

Для начала хочу просто заполнить матрицу фронтов волн рекурсивно

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Front(int **arr, const int m, const int sx, const int sy)
{   
    if(sx==9) return;
    if(sy==10) return;
//  if(sx==0) return;
//  if(sy==-1) return;
 
    if((arr[sx+1][sy]==1000)&&(sx+1<m)&&(sy<m)){arr[sx+1][sy]=arr[sx][sy]+1;}
    Front(arr,m,sx+1,sy);
    if((arr[sx][sy+1]==1000)&&(sx<m)&&(sy+1<m)){arr[sx][sy+1]=arr[sx][sy]+1;}
    Front(arr,m,sx,sy+1);
    //if((arr[sx-1][sy]==1000)&&(sx-1>=0)&&(sy>=0)){arr[sx-1][sy]=arr[sx][sy]+1;}
    //Front(arr,m,sx-1,sy);
    //if((arr[sx][sy-1]==1000)&&(sx>=0)&&(sy-1>=0)){arr[sx][sy-1]=arr[sx][sy]+1;}
    //Front(arr,m,sx,sy-1);
}
Проблема в том, если раскоментировать, то насколько я понимаю он будет переходить на точки в которых уже был и выдавать ошибку.
Что нужно подправить?
И хочется чтобы было именно рекурсивно.
arr[sx+1][sy]==1000 это как бы проверка был я в точке или нет. Изначально массив весь забит 1000ми.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2013, 15:55     Рекурсивная функция
Посмотрите здесь:

Рекурсивная функция C++
C++ Рекурсивная функция
C++ Рекурсивная функция[]
C++ Рекурсивная функция!
C++ рекурсивная функция
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
19.01.2013, 16:51     Рекурсивная функция #2
Цитата Сообщение от Ryk Посмотреть сообщение
C++
1
2
if((arr[sx+1][sy]==1000)&&(sx+1<m)&&(sy<m)){arr[sx+1][sy]=arr[sx][sy]+1;}
    Front(arr,m,sx+1,sy);
А разве вызов Front(sx+1...) не должен быть включён в блок if перед ним?
Ryk
0 / 0 / 0
Регистрация: 19.03.2012
Сообщений: 20
Завершенные тесты: 1
19.01.2013, 17:00  [ТС]     Рекурсивная функция #3
Нет, тогда получится немного не то, что я хочу.
Т.е мне нужно из матрицы

1000 1000 1000 1000
1000 1000 1000 1000
1000 1000 0 1000
1000 1000 1000 1000

Получить

4 3 2 3
3 2 1 2
2 1 0 1
3 2 1 2

нулем отмечена точка начала.

в том, в моем коде получается только правая нижняя часть
т.е.

1000 1000 1000 1000
1000 1000 1000 1000
1000 1000 0 1
1000 1000 1 2

А если сделать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Front(int **arr, const int m, const int sx, const int sy)
{   
    if(sx==9) return;
    if(sy==10) return;
    if(sx==0) return;
    if(sy==-1) return;
 
    if((arr[sx+1][sy]==1000)&&(sx+1<m)&&(sy<m)){arr[sx+1][sy]=arr[sx][sy]+1;Front(arr,m,sx+1,sy);}
//  Front(arr,m,sx+1,sy);
 
 
    if((arr[sx][sy+1]==1000)&&(sx<m)&&(sy+1<m)){arr[sx][sy+1]=arr[sx][sy]+1;Front(arr,m,sx,sy+1);}
//  Front(arr,m,sx,sy+1);
 
    if((arr[sx-1][sy]==1000)&&(sx-1>=0)&&(sy>=0)){arr[sx-1][sy]=arr[sx][sy]+1;Front(arr,m,sx-1,sy);}
//  Front(arr,m,sx-1,sy);
 
    if((arr[sx][sy-1]==1000)&&(sx>=0)&&(sy-1>=0)){arr[sx][sy-1]=arr[sx][sy]+1;Front(arr,m,sx,sy-1);}
//  Front(arr,m,sx,sy-1);
}
То получается сооовсем не то.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
19.01.2013, 17:08     Рекурсивная функция #4
получится именно то. в твоём случае функция рекурсивно вызывается, отправляясь даже в те точки, в которых уже были (правда она их, к счастью не отмечает никак), но это всё равно может вызывать проблемы.
Ryk
0 / 0 / 0
Регистрация: 19.03.2012
Сообщений: 20
Завершенные тесты: 1
19.01.2013, 17:12  [ТС]     Рекурсивная функция #5
Вот, что получается
Кликните здесь для просмотра всего текста

Исходная матрица:
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 0 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
Преобразованная:
80 65 64 63 50 49 36 35 22 21
79 64 63 62 49 48 35 34 21 20
78 65 0 61 50 47 36 33 22 19
77 66 1 60 51 46 37 32 23 18
76 67 2 59 52 45 38 31 24 17
75 68 3 58 53 44 39 30 25 16
74 69 4 57 54 43 40 29 26 15
73 70 5 56 55 42 41 28 27 14
72 71 6 7 8 9 10 11 12 13
73 72 7 8 9 10 11 12 13 14
Для продолжения нажмите любую клавишу . . .

Используя вот этот код
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Front(int **arr, const int m, const int sx, const int sy)
{   
    if(sx==9) return;
    if(sy==10) return;
    if(sx==0) return;
    if(sy==-1) return;
 
    if((arr[sx+1][sy]==1000)&&(sx+1<m)&&(sy<m)){arr[sx+1][sy]=arr[sx][sy]+1;Front(arr,m,sx+1,sy);}
//  Front(arr,m,sx+1,sy);
 
 
    if((arr[sx][sy+1]==1000)&&(sx<m)&&(sy+1<m)){arr[sx][sy+1]=arr[sx][sy]+1;Front(arr,m,sx,sy+1);}
//  Front(arr,m,sx,sy+1);
 
    if((arr[sx-1][sy]==1000)&&(sx-1>=0)&&(sy>=0)){arr[sx-1][sy]=arr[sx][sy]+1;Front(arr,m,sx-1,sy);}
//  Front(arr,m,sx-1,sy);
 
    if((arr[sx][sy-1]==1000)&&(sx>=0)&&(sy-1>=0)){arr[sx][sy-1]=arr[sx][sy]+1;Front(arr,m,sx,sy-1);}
//  Front(arr,m,sx,sy-1);
}

И как видно, это не то, что мне нужно. Вероятно нужно ставить условие перед вызовом рекурсии, но никак не пойму какое. по сути надо бы сравнивать был ли я в этой точке или нет, если был, то не вызывать, но я сначала посещаю точку и меняю в ней значение.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
19.01.2013, 17:20     Рекурсивная функция #6
ясно, я мог бы и предвидеть такой итог...
Всё потому что ты ищешь не кратчайший путь, а произвольный.
как насчёт такого условия?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void Front(int **arr, const int m, const int sx, const int sy)
{   
    if(sx==9) return;
    if(sy==10) return;
    if(sx==0) return;
    if(sy==-1) return;
 
    if((arr[sx+1][sy]>arr[sx][sy]+1)&&(sx+1<m)&&(sy<m)){//добавлено ещё условие в иф
             arr[sx+1][sy]=arr[sx][sy]+1;
             Front(arr,m,sx+1,sy);
    }
///...аналогично ещё 3 стороны
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.01.2013, 17:49     Рекурсивная функция
Еще ссылки по теме:

C++ Рекурсивная функция
C++ Рекурсивная функция y=3x+5
Рекурсивная функция C++

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

Или воспользуйтесь поиском по форуму:
Ryk
0 / 0 / 0
Регистрация: 19.03.2012
Сообщений: 20
Завершенные тесты: 1
19.01.2013, 17:49  [ТС]     Рекурсивная функция #7
Огромное Спасибо вам!

На всякий случай выложу код, может кому поможет.

Кликните здесь для просмотра всего текста
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
void Front(int **arr, const int m, const int sx, const int sy)
{   
    if(sx==9) return;
    if(sy==10) return;
    if(sx==0) return;
    if(sy==-1) return;
    //(arr[sx+1][sy]>arr[sx][sy]+1)
    if((arr[sx+1][sy]>arr[sx][sy]+1)&&(sx+1<m)&&(sy<m))
    {
        arr[sx+1][sy]=arr[sx][sy]+1;
        Front(arr,m,sx+1,sy);
    }
 
    if(((arr[sx][sy+1]>arr[sx][sy]+1))&&(sx<m)&&(sy+1<m))
    {
        arr[sx][sy+1]=arr[sx][sy]+1;
        Front(arr,m,sx,sy+1);
    }
    if(((arr[sx-1][sy]>arr[sx][sy]+1))&&(sx-1>=0)&&(sy>=0))
    {
        arr[sx-1][sy]=arr[sx][sy]+1;
        Front(arr,m,sx-1,sy);
    }
 
    if(((arr[sx][sy-1]>arr[sx][sy]+1))&&(sx>=0)&&(sy-1>=0))
    {
        arr[sx][sy-1]=arr[sx][sy]+1;
        Front(arr,m,sx,sy-1);
    }
    
}


Осталось добавить обработку стен, ну и поиск пути.
Yandex
Объявления
19.01.2013, 17:49     Рекурсивная функция
Ответ Создать тему
Опции темы

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