Динамическое программирование!!! - Microsoft Office Excel

Fuckkiller · 03.05.2011, 15:58

Задача на MS Excel. Игровое поле 2<=M<=20, 2<=N<=20. В каждой ячейке стоит число. Нужно посчитать максимальную сумму чисел в ячейках, путь по полю, который нужно пройти для этого. Двигаться можно лишь вправо и вниз, и движение начинает с верхнего левого угла. Задача из серии динамического программирования (по-моему что-то про черепашку). Помогите кто может)

Serge_Bliznykov · 03.05.2011, 17:02

честное слово, на форуме эти задачи решались.
Воспользуетесь поиском...
и обязательно посмотрите внизу страницы "Похожие темы"...

(p.s. я бы нашёл Вам конкретные ссылки на темы, но сейчас совсем нет времени...)

nilem · 03.05.2011, 17:03

Правда, не очень динамически

doober · 03.05.2011, 17:40

Платон мне друг,но истина дороже.
Николай это только часть алгоритма.Надо еще составить матрицу весов путей для каждой клетки
и с ней работать

Fuckkiller · 03.05.2011, 20:42

Doober, можешь скинуть мне файл с кодом который изображен на картинке?

nilem · 03.05.2011, 20:50

Цитата:

Сообщение от doober

Надо еще составить матрицу весов путей для каждой клетки и с ней работать

Сергей, а если так? На больших матрицах получаются околомаксимальные (ну или почти максимальные) суммы.

IgorGO · 03.05.2011, 21:06

тут перебор всех возможных путей и выбор максимального (рекурсия рулит). Рекомендую для просмотра: процедура перебора путей визуализирована.

не задавайте поле больше 8х8, чтобы не ждать долго результата. Если убрать две строки с заливками в NC, то все будет работать быстрее, но совершенно не зрелищно. NC -это NextCell, а не NortonCommander, как некоторые могли подумать))

Serge_Bliznykov · 03.05.2011, 21:42

ребятки, тут совершенно незачем использовать рекурсию (и условие задачи, где задано поле размером 20 на 20 как бы намекает об этом

)

вот, рекомендую сходить сюда и далее по ссылкам в этом сообщении...

doober · 03.05.2011, 22:07

Во вложении только часть кода.
Он определяет вес пути в каждой точке.
Я думаю Fuckkiller сам доделает двойной цикл для нахождения правильного пути путем сравнения значений в соседних клетках вправо и вниз.И пойдет правильным путем
Максимум уже посчитан

IgorGO · 03.05.2011, 22:35

Вот это да!!!
Серега, у меня получилось красиво, а у тебя правильно!!!

03.05.2011, 15:58	#1
Fuckkiller Пользователь Регистрация: 03.05.2011 Сообщений: 13	Динамическое программирование!!! Задача на MS Excel. Игровое поле 2<=M<=20, 2<=N<=20. В каждой ячейке стоит число. Нужно посчитать максимальную сумму чисел в ячейках, путь по полю, который нужно пройти для этого. Двигаться можно лишь вправо и вниз, и движение начинает с верхнего левого угла. Задача из серии динамического программирования (по-моему что-то про черепашку). Помогите кто может)

03.05.2011, 17:40	#4
doober Старожил Регистрация: 02.05.2009 Сообщений: 3,907	Платон мне друг,но истина дороже. Николай это только часть алгоритма.Надо еще составить матрицу весов путей для каждой клетки и с ней работать Анализ,обработка данных Недорого

03.05.2011, 22:35	#10
IgorGO Новичок СтарожилДжуниор Регистрация: 05.02.2008 Сообщений: 9,487	Вот это да!!! Серега, у меня получилось красиво, а у тебя правильно!!! Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете

Опции темы	Поиск в этой теме
Версия для печати Отправить по электронной почте	Поиск в этой теме: Расширенный поиск

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
динамическое программирование	stefan0202	Паскаль, Turbo Pascal, PascalABC.NET	3	07.02.2011 22:05
Динамическое программирование	Daniya.ru	Общие вопросы .NET	2	19.12.2010 11:40
Динамическое программирование	joey_ramone	Паскаль, Turbo Pascal, PascalABC.NET	0	23.04.2010 13:51
Динамическое программирование.	MAKEDON	Помощь студентам	6	26.08.2009 14:10
Задача на динамическое программирование	Римма1990	Помощь студентам	2	02.04.2009 23:11

03.05.2011, 17:02	#2
Serge_Bliznykov Старожил Регистрация: 09.01.2008 Сообщений: 26,229	честное слово, на форуме эти задачи решались. Воспользуетесь поиском... и обязательно посмотрите внизу страницы "Похожие темы"... (p.s. я бы нашёл Вам конкретные ссылки на темы, но сейчас совсем нет времени...)

03.05.2011, 20:42	#5
Fuckkiller Пользователь Регистрация: 03.05.2011 Сообщений: 13	Doober, можешь скинуть мне файл с кодом который изображен на картинке?

03.05.2011, 21:42	#8
Serge_Bliznykov Старожил Регистрация: 09.01.2008 Сообщений: 26,229	ребятки, тут совершенно незачем использовать рекурсию (и условие задачи, где задано поле размером 20 на 20 как бы намекает об этом ) вот, рекомендую сходить сюда и далее по ссылкам в этом сообщении...