|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
14.11.2009, 15:48 | #1 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
поиск пути
Может кто видел решение этой задачи или подскажите как решать). Есть квадратная доска с числами. В левом верхнем углу стоит черепашка. Она умеет ходить только влево и вниз. Ей надо прийти в правый нижний угол, при этом она хочет, чтобы сумма чисел на пути была максимальной.Задача на динамическое программирование.
|
14.11.2009, 18:46 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
я бы сделал через рекурсию.
пишем функцию fPathCount - которая возвращает сумму всех клеточек, по которым прошла черепашка. смотрите, на каждом шаге можно сделать всего два хода - влево или вниз, значит, вызываем рекурсивно функцию оценки fPathCount два раза - первый раз с координатой левее текущей (переданной как параметер), второй раз с координатой ниже. из полученных значений выбираем наибольшее. запоминаем в динамической памяти (или банально, в строке), какой шажок приносил максимальное значение и возвращаем эту большую сумму как результат функции. Если достигли правый нижний угол - возврат. p.s. С++ не знаю. но алгоритм могу расписать, например, на Паскале... |
14.11.2009, 19:23 | #3 | |
Форумчанин
Регистрация: 25.09.2009
Сообщений: 525
|
Цитата:
или просто при выборе куда шагать выбирать большее число из 2 доступных? тобиш если поле будет 1 2 9 2 4 3 8 1 1 1 1 1 она пойдет 1 2 9 8 1 1 (22) или все таки 1 4 3 8 1 1 (17) |
|
14.11.2009, 22:29 | #4 | ||
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
Цитата:
Цитата:
Последний раз редактировалось NiCola999; 15.11.2009 в 14:39. |
||
15.11.2009, 14:39 | #5 | ||
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
Цитата:
Цитата:
|
||
15.11.2009, 14:54 | #6 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Опять рекурсивные идеи В таких задачах рекурсия неприемлима. Правильно сказано, динамическое программирование. Такие задачи в школе показывают, что бы стал понятен принцип ДП на таблицах. Заполняем матрицу максимумов (снизу вверх), и за n*n находим ответ.
Тут писать строк 5 Но мне как всегда лень. Вот похожая задача: В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути). Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол. Входные данные Во входном файле INPUT.TXT задано два числа N и M - размеры таблицы (1<=N<=20, 1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100). Выходные данные В выходной файл OUTPUT.TXT выведите минимальную сумму, потратив которую можно попасть в правый нижний угол. И мое АС решение на Паскале: Код:
Код:
|
15.11.2009, 15:11 | #7 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
заполнение вспомогательного массива максимумами уже готово, обьясните как черепашке дойти до правого нижнего угла используя этот массив, при том что она может двгаться только вниз и влево, начальное положение в левом верхнем углу
Последний раз редактировалось NiCola999; 15.11.2009 в 15:13. |
15.11.2009, 15:21 | #8 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Вообще никак. Если вниз и влево, то она в правый угол не попадет... Если же вниз и вправо, как я подозреваю, то все не столь непонятно. Если нужно не только само значение, но и путь, то надо выходить из начальной клетки и каждый раз идти в ту клетку воспомогательной матрицы, в которой больше значение (тоесть до которой существует более дорогой путь), пока не попадем в конечную клетку. У меня тоже должен быть исходник, но он тоже на Паскале.
|
15.11.2009, 16:56 | #9 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
да, все-таки вниз и вправо она может. Да, надо вывести путь
|
15.11.2009, 17:18 | #10 | |
Пользователь
Регистрация: 07.11.2008
Сообщений: 71
|
Цитата:
Если долго мучаться, что нибудь получится!!!
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм Флойда. Поиск Кратчайшего пути. | Shady | Помощь студентам | 5 | 06.10.2014 18:29 |
Поиск пути в лабиринте - Пролог | yulia | Помощь студентам | 15 | 21.08.2010 00:14 |
Поиск пути, ...как подключить модуль? | Лубышев | Gamedev - cоздание игр: Unity, OpenGL, DirectX | 1 | 25.09.2009 15:49 |
Поиск кротчайшего пути в делфи 7 | Андрос | Общие вопросы Delphi | 53 | 25.05.2009 21:44 |