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

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

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

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

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

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

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

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 03:25  [ТС]     рекурсивный алгоритм #3
Это я понимаю. Мне другое не ясно. Если в задаче с факториалом идет умножение числа n на n-1 и функция вызывается до тех пор пока n>1, то в своей задаче я не могу понять какие действия должна выполнять рекурсивная функция.
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
31.08.2010, 03:42     рекурсивный алгоритм #4
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
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
31.08.2010, 04:00     рекурсивный алгоритм #6
Mila_mali,
А функция ничего и не выбирает. Вы должны будете вызывать функцию для всех возможных ходов из данной позиции. В свою очередь из каждой новой позиции опять доступно несколько вариантов ходов, и для каждой позиции для каждого варианта будет рекурсивно вызываться функция. Таким образом будет создаваться дерево путей.
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:04  [ТС]     рекурсивный алгоритм #7
Тогда при каждом вызове функции должна будет увеличиваться переменная, хранящая число ходов, и в результате вывести на экран большее из значений этой переменной?Так?
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
31.08.2010, 04:05     рекурсивный алгоритм #8
Ну я думаю, ответом должен являться путь, а не его длина.
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:09  [ТС]     рекурсивный алгоритм #9
Нет. В этой задаче под словом "путь" понимается количество ходов коня.
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
31.08.2010, 04:10     рекурсивный алгоритм #10
Ну значит так, как вы и написали, нужно увеличивать счётчик.
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:12  [ТС]     рекурсивный алгоритм #11
И все таки мне не ясно. Т.е. в функцию каждый раз при вызове будет передаваться позиция коня? так?
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
31.08.2010, 04:14     рекурсивный алгоритм #12
Да. Аргументом фукции является данная позиция коня, а сама функция должна вычислять возможные ходы из этой позиции (тоже, по сути, позиции), затем проверять пересечение, и, если для вычисленной позиции его нет, рекурсивно вызываться с этой самой позицией.
easybudda
Эксперт CЭксперт С++
9466 / 5479 / 927
Регистрация: 25.07.2009
Сообщений: 10,503
31.08.2010, 04:20     рекурсивный алгоритм #13
Цитата Сообщение от Mila_mali Посмотреть сообщение
и в результате вывести на экран большее из значений этой переменной?Так?
Это как-то не наглядно. Я думаю - результат своей бурной деятельности программа должна выдавать в виде массива координат, по которым ходил конь. Интереснее другое - как проверять, проходил конь через клетку, или нет? На сколько я из задания понял, ходы не только не должны заканчиваться на одной и той же клетке, но и пройденные клетки не должны пересекаться? А логика должна быть примерно такая: для каждой клетки найти все доступные ходы, для клетки, на которой ход заканчивается, снова искать доступные ходы... И так, пока ходить станет некуда.
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
31.08.2010, 04:22     рекурсивный алгоритм #14
easybudda,
Я предлагал то же самое, ответ получил отрицательный)))
И алгоритм я тоже такой предполагаю, вопрос в другом, не слишком ли накладно запоминать ВСЕ возможные пути?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.08.2010, 04:26     рекурсивный алгоритм
Еще ссылки по теме:

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

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

Переделать этот алгоритм из итерационного в рекурсивный - C++
Добрый день! помогите пожалуйста переделать этот алгоритм из инетационного в рекурсивный void nat_iter(int num) { int i1, i2,...

Реализовать рекурсивный алгоритм вычисления выражения - C++
Доброго времени суток форумчане. Столкнулся с проблемой реализации рекурсивного алгоритма. Задание звучит следующим образом: С клавиатуры...

Запрограммировать рекурсивный алгоритм вычисления квадрата - C++
Добрый вечер. Может кто нить помочь.. Запрограммировать рекурсивный алгоритм вычисления квадрата натурального числа, используя...


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

Или воспользуйтесь поиском по форуму:
Mila_mali
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 14
31.08.2010, 04:26  [ТС]     рекурсивный алгоритм #15
Я так подумала, вы правы на счет ответа! Пусть это будет массив координат

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

Добавлено через 49 секунд
если для вычисленной позиции нет пересечения с двумя другими позициями, то тогда функция будет рекурсивно вызвана с какой из этих двух позиций?
Yandex
Объявления
31.08.2010, 04:26     рекурсивный алгоритм
Ответ Создать тему
Опции темы

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