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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.87
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
#1

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

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

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

Рекурсивный алгоритм F - C++
Привет всем! Помогите пожалуйста как решается данная функция, если F = 6. Вот код программы: #include <iostream> int F(int n)...

рекурсивный алгоритм - C++
задание было такое (я не раз обращался с ним уже): построить алгоритм вычисления значения аргумента exp(x) с точностью до "эпсилон" с...

рекурсивный алгоритм - C++
В общем я уже намучился с этим заданием... Дело такое, алгоритм составлен, но не совсем такой, какой нужен #include <iostream> #include...

Рекурсивный алгоритм - C++
Даны натуральные числа "N" и "M" надо решить с помощью с++ не могу переставить с этим кодом с++ #include <stdio.h> #include...

Рекурсивный алгоритм - C++
помогите плиз представить в рекурсивный алгоритм Массив A proverka=1 Цикл для i:=1 до 10 делать: Ввод A Конец цикл ...

Рекурсивный алгоритм - C++
Доброго времени суток #include <iostream> #include <cmath> using namespace std; float rec(int x,int n) { if (n != 0) { ...

22
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,544
Завершенные тесты: 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
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
31.08.2010, 04:14 #12
Да. Аргументом фукции является данная позиция коня, а сама функция должна вычислять возможные ходы из этой позиции (тоже, по сути, позиции), затем проверять пересечение, и, если для вычисленной позиции его нет, рекурсивно вызываться с этой самой позицией.
0
easybudda
Модератор
Эксперт CЭксперт С++
9695 / 5645 / 963
Регистрация: 25.07.2009
Сообщений: 10,848
31.08.2010, 04:20 #13
Цитата Сообщение от Mila_mali Посмотреть сообщение
и в результате вывести на экран большее из значений этой переменной?Так?
Это как-то не наглядно. Я думаю - результат своей бурной деятельности программа должна выдавать в виде массива координат, по которым ходил конь. Интереснее другое - как проверять, проходил конь через клетку, или нет? На сколько я из задания понял, ходы не только не должны заканчиваться на одной и той же клетке, но и пройденные клетки не должны пересекаться? А логика должна быть примерно такая: для каждой клетки найти все доступные ходы, для клетки, на которой ход заканчивается, снова искать доступные ходы... И так, пока ходить станет некуда.
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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
31.08.2010, 04:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.08.2010, 04:26
Привет! Вот еще темы с ответами:

Рекурсивный алгоритм - C++
помогите пожалуйста Представить в рекурсивный алгоритм Цикл пока ((proverka=1) и (k&gt;1) ) Если A &gt; A То Начало ...

Рекурсивный алгоритм Дейкстры - C++
Добрый день, необходима помощь в алгоритме trains - матрица, сохраняющая длины ребер stations - количество графов start - граф, с...

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

нужно построить рекурсивный алгоритм - C++
в общем нужен алгоритм вычисления значение функции exp(x) действительного аргумента x с точностью ε с использованием рекурсии. Нужен как...


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

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

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