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

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

Войти
Регистрация
Восстановить пароль
 
Ryk
0 / 0 / 0
Регистрация: 19.03.2012
Сообщений: 20
Завершенные тесты: 1
#1

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

19.01.2013, 15:55. Просмотров 344. Ответов 6
Метки нет (Все метки)

Здраствуйте, пытаюсь написать лабу для нахождения пути в лабиринте, выбрал волновой алгоритм Ли.

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

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ми.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2013, 15:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсивная функция (C++):

Рекурсивная функция! - C++
нужна помощь, как вычислить а в степени n, т.е написать программу использую две функции рекурсивную и нерекурсивный аналог. Очень нужно,...

Рекурсивная функция - C++
Как мне оформить в рекурсивную функцию? Напишите код пожалуйста, буду благодарен)) #include &lt;iostream&gt; #include &lt;conio.h&gt; using...

рекурсивная функция - C++
Описать рекурсивную функцию Digits(S) целого типа, находящую количество цифр в строке S без использования оператора цикла. С помощью этой...

Рекурсивная функция - C++
Задание: Составить программу для счисления сумы К членов строки, где К определяется ||Uk| -|Um||&lt; е и е - наперед задана точность...

Рекурсивная функция - C++
ПРивет всем! ребят помогите решать вот такую задачку: Используя команды write(x) лишь при х=0,1,…9 написать рекурсивную процедуру вывода...

Рекурсивная функция - C++
Принять с клавиатуры натуральное число N. Написать рекурсивную функцию, которая будет выводить слово YES, если число N является точной...

6
Kuzia domovenok
2042 / 1887 / 172
Регистрация: 25.03.2012
Сообщений: 6,499
Записей в блоге: 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 перед ним?
0
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);
}
То получается сооовсем не то.
0
Kuzia domovenok
2042 / 1887 / 172
Регистрация: 25.03.2012
Сообщений: 6,499
Записей в блоге: 1
19.01.2013, 17:08 #4
получится именно то. в твоём случае функция рекурсивно вызывается, отправляясь даже в те точки, в которых уже были (правда она их, к счастью не отмечает никак), но это всё равно может вызывать проблемы.
0
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);
}

И как видно, это не то, что мне нужно. Вероятно нужно ставить условие перед вызовом рекурсии, но никак не пойму какое. по сути надо бы сравнивать был ли я в этой точке или нет, если был, то не вызывать, но я сначала посещаю точку и меняю в ней значение.
0
Kuzia domovenok
2042 / 1887 / 172
Регистрация: 25.03.2012
Сообщений: 6,499
Записей в блоге: 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 стороны
}
1
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);
    }
    
}


Осталось добавить обработку стен, ну и поиск пути.
0
19.01.2013, 17:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.01.2013, 17:49
Привет! Вот еще темы с ответами:

Рекурсивная функция - C++
Помогите, нужна задача, звучит так: Напечатать в обратном порядке последовательность чисел, признаком конца которой является 0. ...

Рекурсивная функция C++ - C++
Сосчитать f(y)=3y+5, yk - входное данное.

Рекурсивная функция y=3x+5 - C++
Здравствуйте! Помогите написать прогу(или если есть готовое решение буду благодарен! Век помнить буду) на c++, которая решает данный...

рекурсивная функция - C++
написал программу вот такую как ее оформить в виде рекурсивной функции . эта программа проверяет на палиндром строку от i до j ...


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

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

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