|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.12.2010, 11:24 | #1 |
Пользователь
Регистрация: 24.11.2010
Сообщений: 17
|
Динамическое программирование
Задание 1. В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол. Входные данные Во входном файле INPUT.TXT задано два числа N и M – размеры таблицы (1 ≤ N ≤ 20, 1 ≤ M ≤ 20). Затем идет N строк по M чисел в каждой – размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100). Выходные данные В выходной файл OUTPUT.TXT выведите минимальную сумму, потратив которую можно попасть в правый нижний угол. Пример INPUT.TXT OUTPUT.TXT 3 4 1 1 1 1 5 2 2 100 9 4 2 1 8 |
19.12.2010, 11:27 | #2 |
Пользователь
Регистрация: 24.11.2010
Сообщений: 17
|
Помогите пожалуйста дорешать задачку!Ошибка в Min
Код:
________ Код нужно оформлять по правилам: тегом [CODE]..[/СODE] (это кнопочка с решёточкой #) Не забывайте об этом! Модератор. Последний раз редактировалось Serge_Bliznykov; 19.12.2010 в 11:30. |
19.12.2010, 11:40 | #3 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
А Вы не задумывались, почему задача на "динамическое программирование" ?
Выбранный Вами алгоритм решения НЕВЕРЕН. выбрав минимальное число на ТЕКУЩЕМ шаге нельзя получить минимальное значение ВСЕГО пути.. почитайте: http://www.programmersforum.ru/showp...24&postcount=6 http://www.programmersforum.ru/showthread.php?t=70592 http://www.programmersforum.ru/showthread.php?t=65954 http://programmersforum.ru/showthread.php?t=60512 http://www.programmersforum.ru/showthread.php?t=60880 если вкратце - берём новый массив, потом идя с правого нижнего угла вверх и влево заполняем его минимальной суммой, которую можно получить двигаясь от этой ячейки к конечной. Когда дошли до левого верхнего угла - то уже путь можно прокладывать по этой таблице минимумов (там в задаче для черепашки ищутся максимумы, Вам нужны минимумы - но это по сути ничего не меняет)! Последний раз редактировалось Serge_Bliznykov; 19.12.2010 в 11:43. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Delphi.Динамическое программирование | Егор527 | Помощь студентам | 5 | 03.06.2010 14:05 |
Динамическое программирование | joey_ramone | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 23.04.2010 13:51 |
Динамическое программирование. | MAKEDON | Помощь студентам | 6 | 26.08.2009 14:10 |
динамическое программирование в Delphi | Ира08 | Помощь студентам | 0 | 03.04.2009 18:07 |
Задача на динамическое программирование | Римма1990 | Помощь студентам | 2 | 02.04.2009 23:11 |