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

Задача решаемая методом рекурсии - C++

Восстановить пароль Регистрация
 
BAHO
3 / 3 / 1
Регистрация: 11.10.2012
Сообщений: 78
11.10.2012, 20:42     Задача решаемая методом рекурсии #1
Помогите решить задачку в си++ методом рекурсии. методом рекурсии приходится решать по прихоти преподавателя((
Проложить полотно железной дороги по кратчайшему, с эконо¬мической точки зрения, пути между пунктами А и Б. На географи¬ческой карте строится некоторая прямоугольная область, где в ле¬вом нижнем углу помещен пункт А, а в правом верхнем углу — пункт Б. Прямоугольная область по горизонтали и по вертикали разделяется на произвольное количество отрезков, и по границам отрезков строится сетка. Для каждой стороны элементарного пря¬моугольника определяется стоимость прокладки пути (рис. 5.1).
Для упрощения решения задачи положим, что путь может про¬кладываться только по границам элементарных прямоугольных областей (т. е. под углом 90°), заранее известна стоимость строи¬тельства по каждому элементарному отрезку, и путь от пункта Б к пункту А прокладывается в направлении справа налево и сверху вниз без петель. Таким образом, каждый возможный путь от пунк¬та А до пункта Б будет представлять собой ломаную линию. Надо проложить такой путь от А к Б, чтобы суммарные затраты на его строительство были минимальны.
Миниатюры
Задача решаемая методом рекурсии  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DebieCooper
 Аватар для DebieCooper
34 / 34 / 1
Регистрация: 12.10.2011
Сообщений: 285
11.10.2012, 20:55     Задача решаемая методом рекурсии #2
Поиск в глубину (ширину).
BAHO
3 / 3 / 1
Регистрация: 11.10.2012
Сообщений: 78
11.10.2012, 20:56  [ТС]     Задача решаемая методом рекурсии #3
а можете подробней описать что нужно сделать?
DebieCooper
 Аватар для DebieCooper
34 / 34 / 1
Регистрация: 12.10.2011
Сообщений: 285
11.10.2012, 21:00     Задача решаемая методом рекурсии #4
Я сам не знаю, что тут делать надо) Сказал, что первое в голову пришло. Просто я ухожу сейчас)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.10.2012, 23:24     Задача решаемая методом рекурсии #5
По хорошему эту задачу надо решать каким-нибудь алгоритмом Дейкстры. Если же рекурсия обязательна, то можно извратиться и перебрать все возможные пути в графе с помощью поиска в глубину и выбрать из них минимальный. Но это будет чертовски неэффективно.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.10.2012, 23:49     Задача решаемая методом рекурсии #6
Цитата Сообщение от diagon Посмотреть сообщение
По хорошему эту задачу надо решать каким-нибудь алгоритмом Дейкстры.
согласен на все 100%.

Цитата Сообщение от diagon Посмотреть сообщение
Если же рекурсия обязательна, то можно извратиться и перебрать все возможные пути в графе с помощью поиска в глубину и выбрать из них минимальный.
единственно что могу посоветовать для ускорения вычисления с помощью рекурсии: изначально всем вершинам присваиваем заведомо недостижимое значение (максимальное значение), вершине А присваиваем 0.
При рек. вызове для очередной вершины делаем так: если путь до смежной с ней вершиной уменьшился, то этой смежной вершине уменьшаем путь и вызываем для нее рек. функцию. Если путь остался таким же или больше, то не делаем ничего.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.10.2012, 20:41     Задача решаемая методом рекурсии
Еще ссылки по теме:

C++ Вычислить сумму N элементов методом восходящей и нисходящей рекурсии
Транспортная задача (методом потенциалов) C++
Транспортная задача (методом потенциалов) C++

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

Или воспользуйтесь поиском по форуму:
BAHO
3 / 3 / 1
Регистрация: 11.10.2012
Сообщений: 78
18.10.2012, 20:41  [ТС]     Задача решаемая методом рекурсии #7
люди добрые... которые сутки у меня ни чего не выходит... можете кода выложить... а то ваще чет ни чего не выходит...
Yandex
Объявления
18.10.2012, 20:41     Задача решаемая методом рекурсии
Ответ Создать тему
Опции темы

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