Форум программистов, компьютерный форум CyberForum.ru

Подскажите книжку по динамическому программированию. - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.85
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 15:39     Подскажите книжку по динамическому программированию. #1
Доброго времени суток!

Наткнулся на такое понятие, как динамическое программирование, горю желанием узнать больше. Пожалуйста, подскажите литературу по динамическому программированию, только для программистов, а не для математиков.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.08.2011, 15:39     Подскажите книжку по динамическому программированию.
Посмотрите здесь:

Подскажите книжку C++
Подскажите книжку C++
Вопрос по динамическому полиморфизму C++
C++ Переход от статического к динамическому массиву
C++ Нужен урок по одномерном и двумерному динамическому массиву
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 15:40     Подскажите книжку по динамическому программированию. #2
Мне тоже интересно, но боюсь, что такой не существует =(
Зато есть:
а) Книга Федора Меньшикова "Олимпиадные задачи по программированию".
б)Разборы задач по динамическому программированию(могу пачку ссылок дать)
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 15:42  [ТС]     Подскажите книжку по динамическому программированию. #3
diagon, давайте всё, что есть Хотя книжка была бы очень полезной.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 15:44     Подскажите книжку по динамическому программированию. #4
Цитата Сообщение от talis Посмотреть сообщение
Доброго времени суток!
Наткнулся на такое понятие, как динамическое программирование, горю желанием узнать больше. Пожалуйста, подскажите литературу по динамическому программированию, только для программистов, а не для математиков
Лучший способ научиться решать задачи на динамическое программирование - перерешать кучу задач и запоминать решения.

Добавлено через 2 минуты
http://reslib.com/book/Olimpiadnie_z...grammirovaniyu
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 15:45  [ТС]     Подскажите книжку по динамическому программированию. #5
Dani, понимаете, чтобы решать задачи на динамическое программирование, нужно знать хотя бы его основы
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 15:48     Подскажите книжку по динамическому программированию. #6
Основы основ основ вот - http://********/article.asp?id_sec=1&id_text=1331

Добавлено через 47 секунд
Но можно просто начать с простых задач
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 15:49     Подскажите книжку по динамическому программированию. #7
http://********/index.asp?main=tasks&...ge=0&id_type=0
Сделай сортировку по разбору, среди них как минимум две задачи из темы динамическое программирование.
http://algolist.manual.ru/olimp/rec_prb.php#z10
Тут пачка решений, код правда на паскале, но там все равно ошибки =)
http://yatsukoyin.blogspot.com/
Тут есть разбор пачки задач, среди них на динамическое программирование.
http://e-maxx.ru/algo/
Вот этот сайт рекомендую, там множество алгоритмов с подробным разбором и реализацией на с++(с векторами/очередями/стэками/etc). Среди них пара алгоритмов на динамику.
Больше что-то ничего вспомнить не могу... Если еще кто знает ссылки на подобные ресурсы - просьба дополнить.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 15:52     Подскажите книжку по динамическому программированию. #8
Самая знаменитая задача на динамику:
В двумерном массиве NxN в [1,1] расположена черепаха. Она мечтает попасть в клетку [N,N]. Всё поле заполнено числами - это количество еды в данной клетке. И вот черепашке мало того, что нужно перейти в конечную клетку, но ей ещё нужно и собрать максимальное количество еды. Причём черепашка может двигаться на одну клетку по горизонтали вправо или на одну клетку по вертикали вниз.

Пример входного файла:

4

0 23 43 55

33 23 21 3

33 12 33 1

100 0 0 200

Добавлено через 1 минуту
Если нужно решение - пиши
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 15:52     Подскажите книжку по динамическому программированию. #9
Цитата Сообщение от Dani Посмотреть сообщение
В двумерном массиве NxN в [1,1] расположена черепаха. Она мечтает попасть в клетку [N,N]. Всё поле заполнено числами - это количество еды в данной клетке. И вот черепашке мало того, что нужно перейти в конечную клетку, но ей ещё нужно и собрать максимальное количество еды. Причём черепашка может двигаться на одну клетку по горизонтали вправо или на одну клетку по вертикали вниз.
А в чем вопрос-то собственно? =)
Разбор аналогичной задачи(Маршрут называется) есть в книге Федора Меньшикова.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 15:56     Подскажите книжку по динамическому программированию. #10
Цитата Сообщение от diagon Посмотреть сообщение
А в чем вопрос-то собственно? =)
Упс... Надо найти нужно собрать максимальное кол-во еды

Добавлено через 1 минуту
или вот, тоже динамика:
Пицца – любимое лакомство Васи, он постоянно покупает и с удовольствием употребляет различные сорта этого великолепного блюда. Однажды, в очередной раз, разрезая круглую пиццу на несколько частей, Вася задумался: на какое максимальное количество частей можно разрезать пиццу за N прямых разрезов?

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

Добавлено через 1 минуту
Цитата Сообщение от diagon Посмотреть сообщение
Сделай сортировку по разбору, среди них как минимум две задачи из темы динамическое программирование.
их там 4 минимум
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 15:57  [ТС]     Подскажите книжку по динамическому программированию. #11
Большое спасибо за задачи, но мне разборы нужны
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
17.08.2011, 15:59     Подскажите книжку по динамическому программированию. #12
с разборами, примерами, графиками
http://habrahabr.ru/tag/%D0%B4%D0%B8...D%D0%B8%D0%B5/
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 16:03     Подскажите книжку по динамическому программированию. #13
задача - http://********/index.asp?main=task&id_task=480 разбор - http://********/index.asp?main=solution&id_task=480
Задача - http://********/index.asp?main=task&id_task=471 разбор - http://********/index.asp?main=solution&id_task=471
Задача - http://********/index.asp?main=task&id_task=183 разбор - http://********/index.asp?main=solution&id_task=183
Задача - http://********/index.asp?main=task&id_task=114 разбор - http://********/index.asp?main=solution&id_task=114
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
17.08.2011, 17:52     Подскажите книжку по динамическому программированию. #14
если это то, о чем я думаю, тогдаNeuralBase

для ознакомления. примеры там где-то тоже должны быть.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 17:54  [ТС]     Подскажите книжку по динамическому программированию. #15
co6ak, спасибо, но это не то
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 17:55     Подскажите книжку по динамическому программированию. #16
Цитата Сообщение от co6ak Посмотреть сообщение
если это то, о чем я думаю, тогдаNeuralBase

для ознакомления. примеры там где-то тоже должны быть.
о_О
Это что?
Динамическое программирование - это просто исключение рекуррентных(повторяющихся) соотношений. Т.е. используется вместо тупого перебора, который не всегда допустим, и тесно связано с комбинаторикой.
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
17.08.2011, 17:56     Подскажите книжку по динамическому программированию. #17
ну значит не то
мы люди серые, не прошаренные.
куда нам до вас...
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 18:01  [ТС]     Подскажите книжку по динамическому программированию. #18
co6ak, пока что вы не серее меня Однако советую поискать информацию и втянуться в тему. Слышали про кэширование для ускорения расчётов? Я глубоко подозреваю, что это сильно связано с динамическим программированием.

Добавлено через 2 минуты
Например, последовательность Фиббоначи можно просчитать без рекурсии и длинных массивов. Два числа - и дело в шляпе
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 18:16     Подскажите книжку по динамическому программированию. #19
Цитата Сообщение от talis Посмотреть сообщение
Например, последовательность Фиббоначи можно просчитать без рекурсии и длинных массивов. Два числа - и дело в шляпе
Да, можно - реккурентным отношением

Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <fstream>
int main()
{
    int n,num=2,a=1,b=1,t;
    std:: ifstream ifs ("input.txt");
    ifs >> n;
    while (a<n)
    {
      t=a;    
      a=a+b;
      b=t;
      num++;
    }
    std:: ofstream ofs ("output.txt");
    if (a==n) ofs << "1" << "\n" <<num;
    else ofs << "0";
    ofs.close();
    return 0;
}
Эта программа определяет, является ли заданное число числом Фибоначчи.

Добавлено через 36 секунд
Вроде бы, Фибоначчи переводится как заика (не зайка )

Добавлено через 1 минуту
talis, объяснить алгоритм?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.08.2011, 18:19     Подскажите книжку по динамическому программированию.
Еще ссылки по теме:

C++ Поиск по динамическому массиву
Доступ к динамическому массиву C++
C++ Адаптировать задачу по динамическому программированию на рекурсию

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 18:19  [ТС]     Подскажите книжку по динамическому программированию. #20
Вот, нашёл интересную страничку с визуализаторами алгоритмов дискретной математики. [страница] Там есть алгоритмы, например, работы с деревьями - а они точно применимы в динамическом программировании.

Добавлено через 53 секунды
Цитата Сообщение от Dani Посмотреть сообщение
talis, объяснить алгоритм?
Благодарствую, но я про него уже начитался Про него одного пишут понятным языком Очень сложно читать статьи, которые написаны в стиле диссертации, а не в стиле учебника.
Yandex
Объявления
17.08.2011, 18:19     Подскажите книжку по динамическому программированию.
Ответ Создать тему
Опции темы

Текущее время: 23:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru