|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
15.11.2009, 17:43 | #11 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
допустим вот такая доска с числами
m: 0 1 2 3 2 5 1 0 6 черепашка стоит в m[0][0] вот матрица максимумов tmp[i][j] = max(m[i+1][j], m[i][j+1]) + m[i][j] tmp: 3 3 0 5 7 0 0 0 0 как используя эту матрицу переместить черепашку в m[3][3] ?)) возможные ходы черепашки i+1(вниз) и j+1(вправо) Последний раз редактировалось NiCola999; 15.11.2009 в 17:47. |
15.11.2009, 18:10 | #12 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
З.Ы. Для вашего примера комп выдал матрицу, содержание которой такое: 16 14 13 16 13 11 7 6 6 Последний раз редактировалось LeBron; 15.11.2009 в 18:12. |
|
15.11.2009, 19:10 | #13 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
препод дал вот это =)
tmp[i][j] = max( a[i-1][j], a[i][j-1] + tmp[i][j]); Последний раз редактировалось NiCola999; 15.11.2009 в 19:24. |
15.11.2009, 20:34 | #14 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
вот моё решение. основано на рекурсии.
логика очень простая. разобраться сможете легко. НО. может Вашему преподавателю это и не понравится... Код:
вначале строки файл input.txt два числа: число_строк и число_столбцов потом построчно матрица. варианты файлов input.txt: Код:
Последний раз редактировалось Serge_Bliznykov; 15.11.2009 в 20:36. |
15.11.2009, 23:16 | #15 |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
да распишите кто-нибудь алгоритм решения с помощью динамического программирования, а не рекурсии, не надо код.Или хотя бы если код то на с/с++
|
16.11.2009, 00:11 | #16 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Даже не знаю, я раньше уже написал, как она решаеться... Если надо объяснить "с ноля", то попытаюсь... не знаю, получиться ли, объясняю я так же, как пишу код. В общем, нам надо найти максимальную цену пути к правому нижнему углу. Цена пути с правого нижнего угла к правому нижнему углу равна весу клетки, которая в этом углу (ведь на матрице 1 на 1 не получиться набрать больше). Дальше для каждой клетки находим максимальную сумму, которую можно набрать, начиная с этой клетки. Логика такая: в сумму будет входить вес этой клетки и вес пути до последней клетки с этой клетки (уже без учета самого веса этой клетки). С текущей клетки в сторону последней клетки можно выйти 2мя способами - сделав ход вправо или сделав ход вниз. Смотрим, какой из этих путей более "дорогой" (для какой из 2 клеток мы перед этим получили болшее значение цены пути) и для получения значения пути с данной клетки суммируем значение пути с той, более дорогой, клетки, и значение клетки (именно самой клетки, то значение, которое получили вначале с входного файла), которую мы рассматриваем. Так обходим всю матрицу снизу вверх справа налево (иначе у нас в процессе обхода будет получаться, что для определения значения пути данной клетки нужно оценить значения путей для клеток, для которых мы это значение еще не вычислили), пока не попадем в начальную клетку. В результате получим цену пути. А для вывода самого пути будем действовать почти так же, как действовали при заполнении, только в другую сторону - выйдем с начальной клетки и каждый раз будем переходить в ту клетку с двох доступных для хода, где больше значение пути.
|
16.11.2009, 00:14 | #17 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
BTW, а что такое, в вашем понимании, "динамическое программирование" ? |
|
16.11.2009, 00:34 | #18 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
From Stilet:Господа, ссоры и кабаки до цугундера доведут. Закрою за флуд. Последний раз редактировалось Stilet; 16.11.2009 в 09:25. |
|
16.11.2009, 06:34 | #19 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
LeBron, вопрос про динамическое программирование обращён НЕ К ВАМ! поэтому не стоило на него отвечать. тем более, посылать меня в поиск. Или в Гугле так и забить - ДП с точки зрения NiCola999 ?!
From Stilet:Господа, ссоры и кабаки до цугундера доведут. Закрою за флуд. Последний раз редактировалось Stilet; 16.11.2009 в 09:25. |
16.11.2009, 09:25 | #20 | |
Не
Участник клуба
Регистрация: 29.10.2009
Сообщений: 1,456
|
разбиение большой задачи на мелкие и их решение. Задача разбивается на подзадачи. В моем случае это заполнение матрицы максимумами очков препод дал такую формулу
1)B[i][j] = max( A[i-1][j], B[i][j-1] + A[i][j]); или может так 2)B[i][j] = max( A[i-1][j], B[i][j-1] ) + A[i][j]; в тетради просто написана) думаю 2ое Затем используя эту матрицу ищется путь, как не знаю Цитата:
используя эту формулу B[i][j] = max( A[i-1][j], B[i][j-1] ) + A[i][j]; для матрицы A: 0 1 2 3 2 5 1 0 6 получил такую матрицу B: 0 0 0 0 3 8 0 2 11 я правильно тебя понял LeBron ? ) начинаем цикл с нижнего угла, значит используем правило хода наоборот( вверх,влево), смотрим если сверху от клетки B[2][2] стоит большее число,чем слева, передвигаем вверх (i-1) , иначе (j-1). получилось вот что... Код:
pos( 1 ; 2 ) 8 pos( 1 ; 1 ) 3 Scores: 22 идет вроде правильно, останавливается на 3ке т.к там дальше нули идут и условие не выполняется. Вот не пойму как сделать чтобы она правильно пошла в таком случае и не зашла за границы матрицы p.s я хоть на правильном пути ?) Последний раз редактировалось NiCola999; 16.11.2009 в 11:16. |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм Флойда. Поиск Кратчайшего пути. | 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 |