|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.08.2009, 14:18 | #1 | |
The First Person!
Форумчанин
Регистрация: 07.08.2007
Сообщений: 228
|
Динамическое программирование.
При решение задач столкнулся с таким понятием, как динамическое программирование. Вот задача на поиск всех возможных путей и нахождение наиболее быстрого. Объясните на примере этой задачи, как вообще они решаются. Язык - значения не имеет.
Цитата:
Программа обычно делает то что вы ей сказали сделать, а не то что бы вы хотели, чтобы она сделала.
|
|
22.08.2009, 14:26 | #2 |
Заблокирован
Старожил
Регистрация: 20.07.2008
Сообщений: 4,032
|
Эта задача решается с помощью ориентированных графов.
//Только почему такое странное название темы? О_О Последний раз редактировалось Levsha100; 22.08.2009 в 14:31. |
22.08.2009, 14:26 | #3 |
В тени
Старожил
Регистрация: 19.12.2008
Сообщений: 5,788
|
Вот, недавно было такое: http://programmersforum.ru/showthread.php?t=60512
Вполне очевидно, чтобы что-то понять, необходимо книги читать.
Не нужно плодить бессмысленных тем. Вас Поиск избавит от многих проблем. ___________________________________ ___________________________________ _______ [=Правила форума=]_____[Поиск]_____[Литература по С++]____[Литература. Паскаль] |
22.08.2009, 17:04 | #4 |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
|
23.08.2009, 14:21 | #5 |
The First Person!
Форумчанин
Регистрация: 07.08.2007
Сообщений: 228
|
Да, эта задача с какой-то олимпиады. А можете представить решение с комментириями? А то никак в этой теме не могу разобраться..
Программа обычно делает то что вы ей сказали сделать, а не то что бы вы хотели, чтобы она сделала.
Последний раз редактировалось MAKEDON; 23.08.2009 в 18:50. |
24.08.2009, 12:04 | #6 |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
a[0][1] = 0;
for (int x = 2; x <= m; x++) a[0][x] = numeric_limits<int>::max(); for (int y = 1; y <= n; y++) { a[y][0] = numeric_limits<int>::max(); for (int x = 1; x <= m; x++) cin >> a[y][x]; } for (int y = 1; y <= n; y++) for (int x = 1; x <= m; x++) a[y][x] += min(a[y - 1][x], a[y][x - 1]); [/code] Минимальная сумма, полученная по пути для клетки, - это число в этой клетке плюс минимум из суммы для клетки слева и клетки сверху. Почитай Википедию про динамическое программирование, запусти пошагово на примере и посмотри. |
26.08.2009, 14:10 | #7 | ||
Форумчанин
Регистрация: 16.04.2009
Сообщений: 247
|
Цитата:
Идея такая. Пусть мы сейчас вычисляем оптимальную характеристику для [i, j] клетки. Пусть нам уже известна оптимальная характеристика для клеток левее этой клетки в этой же строке(i-той) и для всех клеток в предыдущих строках(с номером < i). Тогда как мы можем попасть в клетку [i, j]? Из клеток [i - 1, j] и [i, j - 1]. Надо только учитывать что в клетки первой строки мы можем попасть только слева и в клетки первого столбца только сверху. Выбираем минимум и не забываем добавить стоимость прохождения через саму клетку. Вот исходник, правда работает с числами только от 0 до 9 в каждой клетке. Таковы были ограничения задачи, которую я решал. Но главное, чтобы логика работы была понятна, а там переделаешь как тебе надо. Например на Delphi или C++. Там правда есть ещё несколько технических моментов, обусловленных ограничениями задачи, которую я решал, и Turbo Pascal'я на котором я её тогда писал. Эта программа правда рисует в ASCII оптимальный маршрут, вместо того, чтобы выводить необходимое число, но из неё можно взять кусок основной логики. А, да, и ещё во входном файле цифры матрицы надо записывать без пробелов. Код:
Ладно, короче Самому стало интересно, так что не поленился написать то, что тебе нужно. Код:
Цитата:
----------------------------------------------------------------------------------------------------------------------------------- Из литературы могу рекомендовать: 1) Кормен, Ривест, Лейзерсон, Штайн. Алгоритмы: построение и анализ 2) Ф.Меньшиков. Олимпиадные задачи по программированию. Правда, вторая немного устарела, в том плане, что на олимпиадах сейчас задачки и покруче бывают. Последний раз редактировалось megachuhancer; 26.08.2009 в 14:52. |
||
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
динамическое программирование в Delphi | Ира08 | Помощь студентам | 0 | 03.04.2009 18:07 |
Задача на динамическое программирование | Римма1990 | Помощь студентам | 2 | 02.04.2009 23:11 |
Рекуррентные соотношения и динамическое программирование. | DOOM514 | Фриланс | 3 | 08.01.2009 16:20 |
Динамическое MainMenu | dr.Chas | Общие вопросы Delphi | 4 | 24.06.2008 20:33 |