Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.61/18: Рейтинг темы: голосов - 18, средняя оценка - 4.61
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
1

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

31.08.2010, 02:58. Просмотров 3279. Ответов 22
Метки нет (Все метки)

Уважаемые программисты! Есть задача: разработать рекурсивный алгоритм на с++ для нахождения самого длинного несамопересекающегося пути коня на доске 6*6. Я рекурсию плохо понимаю. Подскажите, что именно должна делать рекурсивная функция.
 Комментарий модератора 
Не нужно в теме, посвящённой решению одной задачи размещать другую, пусть и в чём-то сходную.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.08.2010, 02:58
Ответы с готовыми решениями:

рекурсивный алгоритм
В общем я уже намучился с этим заданием... Дело такое, алгоритм составлен, но...

Рекурсивный алгоритм
Доброго времени суток #include <iostream> #include <cmath> using namespace...

Рекурсивный алгоритм F
Привет всем! Помогите пожалуйста как решается данная функция, если F = 6. ...

Рекурсивный алгоритм
помогите пожалуйста Представить в рекурсивный алгоритм Цикл пока...

Рекурсивный алгоритм
помогите плиз представить в рекурсивный алгоритм Массив A proverka=1...

22
ForEveR
В астрале
Эксперт С++
7996 / 4755 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 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;
}
0
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 03:25  [ТС] 3
Это я понимаю. Мне другое не ясно. Если в задаче с факториалом идет умножение числа n на n-1 и функция вызывается до тех пор пока n>1, то в своей задаче я не могу понять какие действия должна выполнять рекурсивная функция.
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
31.08.2010, 03:42 4
Mila_mali,
Судя по всему функция должна из некоторой позиции коня рекурсивно запускаться и искать все возможные ходы коня из этой позиции и проверять, нет ли самопересечений.
0
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 03:57  [ТС] 5
А как тогда избежать такой ситуации: если конь может сходить на "клетку1" или "клетку2" или "клетку3" и при этом путь его не будет самопересекаться. И допустим функция выбрала ход на "клетку1" из которой тоже есть несколько вариантов чтоб путь не пересекался. и так будет до тех пор, пока не останется возможных ходов и произойдет выход из рекрсивный функции. Но этот путь ведь может оказаться не самым длинным! Ведь самый длинный путь может проходить через "клетку3", а не через "клетку1" как функция выбрала в момент вызова. Как тогда рассмотреть все варианты??
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
31.08.2010, 04:00 6
Mila_mali,
А функция ничего и не выбирает. Вы должны будете вызывать функцию для всех возможных ходов из данной позиции. В свою очередь из каждой новой позиции опять доступно несколько вариантов ходов, и для каждой позиции для каждого варианта будет рекурсивно вызываться функция. Таким образом будет создаваться дерево путей.
0
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:04  [ТС] 7
Тогда при каждом вызове функции должна будет увеличиваться переменная, хранящая число ходов, и в результате вывести на экран большее из значений этой переменной?Так?
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
31.08.2010, 04:05 8
Ну я думаю, ответом должен являться путь, а не его длина.
0
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:09  [ТС] 9
Нет. В этой задаче под словом "путь" понимается количество ходов коня.
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
31.08.2010, 04:10 10
Ну значит так, как вы и написали, нужно увеличивать счётчик.
0
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:12  [ТС] 11
И все таки мне не ясно. Т.е. в функцию каждый раз при вызове будет передаваться позиция коня? так?
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
31.08.2010, 04:14 12
Да. Аргументом фукции является данная позиция коня, а сама функция должна вычислять возможные ходы из этой позиции (тоже, по сути, позиции), затем проверять пересечение, и, если для вычисленной позиции его нет, рекурсивно вызываться с этой самой позицией.
0
easybudda
Модератор
Эксперт CЭксперт С++
10107 / 6016 / 1507
Регистрация: 25.07.2009
Сообщений: 11,404
31.08.2010, 04:20 13
Цитата Сообщение от Mila_mali Посмотреть сообщение
и в результате вывести на экран большее из значений этой переменной?Так?
Это как-то не наглядно. Я думаю - результат своей бурной деятельности программа должна выдавать в виде массива координат, по которым ходил конь. Интереснее другое - как проверять, проходил конь через клетку, или нет? На сколько я из задания понял, ходы не только не должны заканчиваться на одной и той же клетке, но и пройденные клетки не должны пересекаться? А логика должна быть примерно такая: для каждой клетки найти все доступные ходы, для клетки, на которой ход заканчивается, снова искать доступные ходы... И так, пока ходить станет некуда.
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
31.08.2010, 04:22 14
easybudda,
Я предлагал то же самое, ответ получил отрицательный)))
И алгоритм я тоже такой предполагаю, вопрос в другом, не слишком ли накладно запоминать ВСЕ возможные пути?
0
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:26  [ТС] 15
Я так подумала, вы правы на счет ответа! Пусть это будет массив координат

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

Добавлено через 49 секунд
если для вычисленной позиции нет пересечения с двумя другими позициями, то тогда функция будет рекурсивно вызвана с какой из этих двух позиций?
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
31.08.2010, 04:27 16
Mila_mali,
Начнём с того, что возможных ходов может быть и больше двух.
А вообще вызывается со всеми возможными позициями.
0
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:31  [ТС] 17
Я к примеру сказала про две позиции
Я уже изучила сколько ходов можно сделать из каждой клетки доски, пока пыталась решить эту задачу
У меня проблема в другом. Как бы я ни пыталась, я не могу понять принцип рекурсивных алгоритмов
0
easybudda
Модератор
Эксперт CЭксперт С++
10107 / 6016 / 1507
Регистрация: 25.07.2009
Сообщений: 11,404
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;
1
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:39  [ТС] 19
Спасибо! Это стало ясно.
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 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)
    }
0
31.08.2010, 04:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.08.2010, 04:40

рекурсивный алгоритм
задание было такое (я не раз обращался с ним уже): построить алгоритм...

Рекурсивный алгоритм
Даны натуральные числа &quot;N&quot; и &quot;M&quot; надо решить с помощью с++ не могу...

Рекурсия, рекурсивный алгоритм
Не работает програма, можете исправить, или обьяснить, что не правильною ...


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

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

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