|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
18.08.2009, 11:49 | #1 |
Пользователь
Регистрация: 26.02.2008
Сообщений: 56
|
Задача на C
Друзья, помогите, пожалуйста, с такой задачкой:
Дана шахматная доска M*N с разными монетками на каждом квадрате. Необходимо из стартовой левой нижней позиции перебраться вверх таким образом, что бы собрать наибольшую сумму монет. По диагонали ходить нельзя. Можно только вправо и вверх Прога не должна работать путем поиска самых больших ближайших чисел, так как самое большое число может находится на другом конце матрицы. Спасибо заранее.
Sorry za translit - Ne znaju, kak na Debain postavit Russkiy!
|
18.08.2009, 15:27 | #2 |
В тени
Старожил
Регистрация: 19.12.2008
Сообщений: 5,788
|
Раз двигаться можно только вправо и вверх, то, может, перебором?
А вообще можно граф построить (каждая клетка связана с той, что выше, и той, что правее) и работать уже с ним.
Вполне очевидно, чтобы что-то понять, необходимо книги читать.
Не нужно плодить бессмысленных тем. Вас Поиск избавит от многих проблем. ___________________________________ ___________________________________ _______ [=Правила форума=]_____[Поиск]_____[Литература по С++]____[Литература. Паскаль] |
18.08.2009, 16:15 | #3 |
Старожил
Регистрация: 22.05.2007
Сообщений: 9,085
|
Можно попробовать прикрутить алгоритмы поиска кратчайшего пути. волновой там или еще какой. Стоимость монетки - есть стоимость пути. Ну или, чтобы не превращать это в поиск самого длинного пути, стоимость пути = 100 - номинал монеты
|
18.08.2009, 16:50 | #4 |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
Может что-то типа
Код:
Последний раз редактировалось Somebody; 18.08.2009 в 17:04. |
18.08.2009, 17:18 | #5 |
C++ hater
СтарожилДжуниор
Регистрация: 19.07.2009
Сообщений: 3,333
|
2Somebody неа, ибо ты ведь не знаешь, какие монетки будут дальше этого пути. на текущем шаге ты сделаешь выгодное решение, но на следующем может оказаться так, что выгоднее было пойти по другому пути
ну вот пример: 10 10 10 10 10 10 10 10 10 10 90 10 10 10 10 10 10 10 10 10 10 20 10 10 10 идем из левого нижнего угла. на первом же ходу твой алгоритм даст сбой
I invented the term Object-Oriented, and I can tell you I did not have C++ in mind. (c)Alan Kay
My other car is cdr. Q: Whats the object-oriented way to become wealthy? A: Inheritance Последний раз редактировалось pproger; 18.08.2009 в 17:24. |
18.08.2009, 17:31 | #6 |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
Ой, там имелось в виду +=. В каждом элементе будет наибольшая возможная сумма по пути до него, тогда для каждой клетки надо только выбрать предыдущую. В общем, типа:
Код:
Последний раз редактировалось Somebody; 18.08.2009 в 17:34. |