|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
08.12.2016, 12:10 | #1 |
Регистрация: 07.12.2016
Сообщений: 3
|
Двумерное динамическое программирование
opamagite reshit zadachu prashu ochen nado
дана A[n][m] матрица из натуральных чисел (2<=n,m<=100), и при прохождении (i,j) обьекта начисляется штраф A[i][j]. Наше задание попасть из любового элемента первой строчки в n-ную строчку. При этом из конкретного элемента можно продолжить движение к 3 соседним элементам нижней строчки. Напишите программу которая выполнит данную задачу и минимизирует размер шрафа.. ashvosk на форуме Добавить отзыв для ashvosk Пожаловаться на это сообщение (C++) |
08.12.2016, 12:15 | #2 |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,707
|
|
08.12.2016, 12:18 | #3 |
Регистрация: 07.12.2016
Сообщений: 3
|
ne obezatelno reshit za meya mojna dat bodskazku
|
08.12.2016, 12:28 | #4 |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,707
|
Так задача в лоб решается просто:
1. строим прямой путь от одного элемента до нужно, например, по прямой 2. https://en.wikipedia.org/wiki/Backtracking с параметром из предыдущего шага 3. по условию задачи отсекаем или добавляем решения |
08.12.2016, 12:48 | #5 |
Вредный кошак
Участник клуба
Регистрация: 14.10.2012
Сообщений: 1,159
|
Звучит-то как, - "Двумерное программирование".
|
08.12.2016, 13:38 | #6 |
Заблокирован
Регистрация: 29.11.2016
Сообщений: 215
|
Даю бодсказку :
- это классически рекурсивная задача... - для текущей позиции в цикле (по 3-м соседям) вызываете всё ту же функцию накопления штрафа... - и суммируете значения штрафов... - при этом где-то (в статической, глобальной переменной, дополнительном параметре функции...) храните минимально найденное до сих пор значение накопленного штрафа. |
08.12.2016, 16:47 | #7 |
Заблокирован
Регистрация: 29.11.2016
Сообщений: 215
|
Интересно стало (задача).
У вас должно получиться что-то типа такого: Код:
Код:
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Двумерное динамическое программирование | ashvosk | Помощь студентам | 0 | 07.12.2016 20:42 |
Динамическое программирование | 4ubak01 | Windows Forms | 0 | 21.04.2016 21:22 |
Динамическое программирование | Hyskills | Общие вопросы по Java, Java SE, Kotlin | 0 | 24.02.2016 21:34 |
динамическое программирование | stefan0202 | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 07.02.2011 22:05 |