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

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

Войти
Регистрация
Восстановить пароль
 
BAHO
3 / 3 / 1
Регистрация: 11.10.2012
Сообщений: 78
#1

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

11.10.2012, 20:42. Просмотров 809. Ответов 6
Метки нет (Все метки)

Помогите решить задачку в си++ методом рекурсии. методом рекурсии приходится решать по прихоти преподавателя((
Проложить полотно железной дороги по кратчайшему, с эконо¬мической точки зрения, пути между пунктами А и Б. На географи¬ческой карте строится некоторая прямоугольная область, где в ле¬вом нижнем углу помещен пункт А, а в правом верхнем углу — пункт Б. Прямоугольная область по горизонтали и по вертикали разделяется на произвольное количество отрезков, и по границам отрезков строится сетка. Для каждой стороны элементарного пря¬моугольника определяется стоимость прокладки пути (рис. 5.1).
Для упрощения решения задачи положим, что путь может про¬кладываться только по границам элементарных прямоугольных областей (т. е. под углом 90°), заранее известна стоимость строи¬тельства по каждому элементарному отрезку, и путь от пункта Б к пункту А прокладывается в направлении справа налево и сверху вниз без петель. Таким образом, каждый возможный путь от пунк¬та А до пункта Б будет представлять собой ломаную линию. Надо проложить такой путь от А к Б, чтобы суммарные затраты на его строительство были минимальны.
Миниатюры
Задача решаемая методом рекурсии  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2012, 20:42     Задача решаемая методом рекурсии
Посмотрите здесь:

Транспортная задача методом северо западного угла C++
C++ задача методом крамера (как проверить вход данные с++)
Задача на сортировку массива методом вставки на С++ C++
C++ Задача (сортировка методом пузырька)
Методом рекурсии вывести число слево на право. Не использую массивов циклов строк C++
Задача методом Гаусса C++
Решение уравнения методом бисекции с использованием рекурсии C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DebieCooper
 Аватар для DebieCooper
34 / 34 / 1
Регистрация: 12.10.2011
Сообщений: 286
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
Сообщений: 286
11.10.2012, 21:00     Задача решаемая методом рекурсии #4
Я сам не знаю, что тут делать надо) Сказал, что первое в голову пришло. Просто я ухожу сейчас)
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.10.2012, 23:24     Задача решаемая методом рекурсии #5
По хорошему эту задачу надо решать каким-нибудь алгоритмом Дейкстры. Если же рекурсия обязательна, то можно извратиться и перебрать все возможные пути в графе с помощью поиска в глубину и выбрать из них минимальный. Но это будет чертовски неэффективно.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 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++ Задача коммивояжера методом динамического программирования
C++ Вычислить сумму N элементов методом восходящей и нисходящей рекурсии
Транспортная задача (методом потенциалов) C++
Транспортная задача (методом потенциалов) C++
C++ Задача коммивояжера методом локального поиска

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

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

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