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

рекурсивный алгоритм - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.87
Mila_mali
 Аватар для Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 02:58     рекурсивный алгоритм #1
Уважаемые программисты! Есть задача: разработать рекурсивный алгоритм на с++ для нахождения самого длинного несамопересекающегося пути коня на доске 6*6. Я рекурсию плохо понимаю. Подскажите, что именно должна делать рекурсивная функция.
 Комментарий модератора 
Не нужно в теме, посвящённой решению одной задачи размещать другую, пусть и в чём-то сходную.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7954 / 4716 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
31.08.2010, 03:18     рекурсивный алгоритм #2
Mila_mali, В общем случае рекурсивная функция эта та функция которая явно или неявно вызывает сама себя.

Для факториала например:

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
 
unsigned long long Fact(int n)
{
    return (n>1)?n*Fact(n-1):n;
}
 
int main()
{
   std::cout<<Fact(5);
   return 0;
}
Mila_mali
 Аватар для Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 03:25  [ТС]     рекурсивный алгоритм #3
Это я понимаю. Мне другое не ясно. Если в задаче с факториалом идет умножение числа n на n-1 и функция вызывается до тех пор пока n>1, то в своей задаче я не могу понять какие действия должна выполнять рекурсивная функция.
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 03:42     рекурсивный алгоритм #4
Mila_mali,
Судя по всему функция должна из некоторой позиции коня рекурсивно запускаться и искать все возможные ходы коня из этой позиции и проверять, нет ли самопересечений.
Mila_mali
 Аватар для Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 03:57  [ТС]     рекурсивный алгоритм #5
А как тогда избежать такой ситуации: если конь может сходить на "клетку1" или "клетку2" или "клетку3" и при этом путь его не будет самопересекаться. И допустим функция выбрала ход на "клетку1" из которой тоже есть несколько вариантов чтоб путь не пересекался. и так будет до тех пор, пока не останется возможных ходов и произойдет выход из рекрсивный функции. Но этот путь ведь может оказаться не самым длинным! Ведь самый длинный путь может проходить через "клетку3", а не через "клетку1" как функция выбрала в момент вызова. Как тогда рассмотреть все варианты??
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 04:00     рекурсивный алгоритм #6
Mila_mali,
А функция ничего и не выбирает. Вы должны будете вызывать функцию для всех возможных ходов из данной позиции. В свою очередь из каждой новой позиции опять доступно несколько вариантов ходов, и для каждой позиции для каждого варианта будет рекурсивно вызываться функция. Таким образом будет создаваться дерево путей.
Mila_mali
 Аватар для Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:04  [ТС]     рекурсивный алгоритм #7
Тогда при каждом вызове функции должна будет увеличиваться переменная, хранящая число ходов, и в результате вывести на экран большее из значений этой переменной?Так?
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 04:05     рекурсивный алгоритм #8
Ну я думаю, ответом должен являться путь, а не его длина.
Mila_mali
 Аватар для Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:09  [ТС]     рекурсивный алгоритм #9
Нет. В этой задаче под словом "путь" понимается количество ходов коня.
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 04:10     рекурсивный алгоритм #10
Ну значит так, как вы и написали, нужно увеличивать счётчик.
Mila_mali
 Аватар для Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:12  [ТС]     рекурсивный алгоритм #11
И все таки мне не ясно. Т.е. в функцию каждый раз при вызове будет передаваться позиция коня? так?
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 04:14     рекурсивный алгоритм #12
Да. Аргументом фукции является данная позиция коня, а сама функция должна вычислять возможные ходы из этой позиции (тоже, по сути, позиции), затем проверять пересечение, и, если для вычисленной позиции его нет, рекурсивно вызываться с этой самой позицией.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9383 / 5433 / 916
Регистрация: 25.07.2009
Сообщений: 10,428
31.08.2010, 04:20     рекурсивный алгоритм #13
Цитата Сообщение от Mila_mali Посмотреть сообщение
и в результате вывести на экран большее из значений этой переменной?Так?
Это как-то не наглядно. Я думаю - результат своей бурной деятельности программа должна выдавать в виде массива координат, по которым ходил конь. Интереснее другое - как проверять, проходил конь через клетку, или нет? На сколько я из задания понял, ходы не только не должны заканчиваться на одной и той же клетке, но и пройденные клетки не должны пересекаться? А логика должна быть примерно такая: для каждой клетки найти все доступные ходы, для клетки, на которой ход заканчивается, снова искать доступные ходы... И так, пока ходить станет некуда.
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 04:22     рекурсивный алгоритм #14
easybudda,
Я предлагал то же самое, ответ получил отрицательный)))
И алгоритм я тоже такой предполагаю, вопрос в другом, не слишком ли накладно запоминать ВСЕ возможные пути?
Mila_mali
 Аватар для Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:26  [ТС]     рекурсивный алгоритм #15
Я так подумала, вы правы на счет ответа! Пусть это будет массив координат

Добавлено через 34 секунды
Мне как раз не понятно с тем, как программа будет запоминать все возможные пути\

Добавлено через 49 секунд
если для вычисленной позиции нет пересечения с двумя другими позициями, то тогда функция будет рекурсивно вызвана с какой из этих двух позиций?
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 04:27     рекурсивный алгоритм #16
Mila_mali,
Начнём с того, что возможных ходов может быть и больше двух.
А вообще вызывается со всеми возможными позициями.
Mila_mali
 Аватар для Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:31  [ТС]     рекурсивный алгоритм #17
Я к примеру сказала про две позиции
Я уже изучила сколько ходов можно сделать из каждой клетки доски, пока пыталась решить эту задачу
У меня проблема в другом. Как бы я ни пыталась, я не могу понять принцип рекурсивных алгоритмов
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9383 / 5433 / 916
Регистрация: 25.07.2009
Сообщений: 10,428
31.08.2010, 04:34     рекурсивный алгоритм #18
Цитата Сообщение от Mila_mali Посмотреть сообщение
Мне как раз не понятно с тем, как программа будет запоминать все возможные пути
я думаю, как-то так:
C++
1
std::vector<std::pair<int, int> > way;
Первый полученный путь сохранить, как самый длинный. А дальше сравнивать размер свежеполученного массива с самым длинным. Если новый длиннее - сохранять его, как самый длинный...
C++
1
2
if ( way.size() > max_way.size() )
  max_way = way;
Mila_mali
 Аватар для Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:39  [ТС]     рекурсивный алгоритм #19
Спасибо! Это стало ясно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.08.2010, 04:40     рекурсивный алгоритм
Еще ссылки по теме:

C++ Переделать этот алгоритм из итерационного в рекурсивный
Рекурсивный алгоритм перестановок C++
C++ Рекурсивный алгоритм
C++ Рекурсивный алгоритм
C++ Реализовать рекурсивный алгоритм вычисления выражения

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 04:40     рекурсивный алгоритм #20
Mila_mali,
Принцип приблизительно такой
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func(pos)
{
    вычислить newpos1
    if (из pos в newpos1 нет самопересечений)
    {
        сохранить newpos1
        func(newpos1)
    }
    
    вычислить newpos2
    if (из pos в newpos2 нет самопересечений)
    {
        сохранить newpos2
        func(newpos2)
    }
    ...
    вычислить newposn
    if (из pos в newposn нет самопересечений)
    {
        сохранить newposn
        func(newposn)
    }
Yandex
Объявления
31.08.2010, 04:40     рекурсивный алгоритм
Ответ Создать тему
Опции темы

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