Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.85
talis
793 / 545 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
#1

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

17.08.2011, 15:39. Просмотров 3903. Ответов 26
Метки нет (Все метки)

Доброго времени суток!

Наткнулся на такое понятие, как динамическое программирование, горю желанием узнать больше. Пожалуйста, подскажите литературу по динамическому программированию, только для программистов, а не для математиков.
http://www.cyberforum.ru/cpp-beginners/thread1452668.html
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.08.2011, 15:39
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Подскажите книжку по динамическому программированию. (C++):

Подскажите книжку
Можете подсказать хорошую книгу по c++. Мне не нужна c++ для чайников, основы...

Подскажите книжку
Привет всем..Я в C++ новичёк... но я хорошо соображаю и очень хочу научится.У...

Подскажите хороший сборник задач по программированию
Желательно под c++

Доступ к динамическому массиву
Первый раз столкнулся с такой фигней. Что происходит? #include <iostream>...

Поиск по динамическому массиву
Задан целочисленный двумерный массив a из n строк и m столбцов. Найти номер...

26
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 15:40 #2
Мне тоже интересно, но боюсь, что такой не существует =(
Зато есть:
а) Книга Федора Меньшикова "Олимпиадные задачи по программированию".
б)Разборы задач по динамическому программированию(могу пачку ссылок дать)
1
talis
793 / 545 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 15:42  [ТС] #3
diagon, давайте всё, что есть Хотя книжка была бы очень полезной.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 15:44 #4
Цитата Сообщение от talis Посмотреть сообщение
Доброго времени суток!
Наткнулся на такое понятие, как динамическое программирование, горю желанием узнать больше. Пожалуйста, подскажите литературу по динамическому программированию, только для программистов, а не для математиков
Лучший способ научиться решать задачи на динамическое программирование - перерешать кучу задач и запоминать решения.

Добавлено через 2 минуты
http://reslib.com/book/Olimpiadnie_zadachi_po_programmirovaniyu
1
talis
793 / 545 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 15:45  [ТС] #5
Dani, понимаете, чтобы решать задачи на динамическое программирование, нужно знать хотя бы его основы
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 15:48 #6
Основы основ основ вот -

Добавлено через 47 секунд
Но можно просто начать с простых задач
1
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 15:49 #7

Сделай сортировку по разбору, среди них как минимум две задачи из темы динамическое программирование.
http://algolist.manual.ru/olimp/rec_prb.php#z10
Тут пачка решений, код правда на паскале, но там все равно ошибки =)
http://yatsukoyin.blogspot.com/
Тут есть разбор пачки задач, среди них на динамическое программирование.
http://e-maxx.ru/algo/
Вот этот сайт рекомендую, там множество алгоритмов с подробным разбором и реализацией на с++(с векторами/очередями/стэками/etc). Среди них пара алгоритмов на динамику.
Больше что-то ничего вспомнить не могу... Если еще кто знает ссылки на подобные ресурсы - просьба дополнить.
1
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 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 минуту
Если нужно решение - пиши
1
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 15:52 #9
Цитата Сообщение от Dani Посмотреть сообщение
В двумерном массиве NxN в [1,1] расположена черепаха. Она мечтает попасть в клетку [N,N]. Всё поле заполнено числами - это количество еды в данной клетке. И вот черепашке мало того, что нужно перейти в конечную клетку, но ей ещё нужно и собрать максимальное количество еды. Причём черепашка может двигаться на одну клетку по горизонтали вправо или на одну клетку по вертикали вниз.
А в чем вопрос-то собственно? =)
Разбор аналогичной задачи(Маршрут называется) есть в книге Федора Меньшикова.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 15:56 #10
Цитата Сообщение от diagon Посмотреть сообщение
А в чем вопрос-то собственно? =)
Упс... Надо найти нужно собрать максимальное кол-во еды

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

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

Добавлено через 1 минуту
Цитата Сообщение от diagon Посмотреть сообщение
Сделай сортировку по разбору, среди них как минимум две задачи из темы динамическое программирование.
их там 4 минимум
1
talis
793 / 545 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 15:57  [ТС] #11
Большое спасибо за задачи, но мне разборы нужны
0
PointsEqual
ниначмуроФ
838 / 522 / 110
Регистрация: 12.10.2009
Сообщений: 1,915
17.08.2011, 15:59 #12
с разборами, примерами, графиками
http://habrahabr.ru/tag/%D0%B4%D0%B8...D%D0%B8%D0%B5/
2
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 16:03 #13
задача - разбор -
Задача - разбор -
Задача - разбор -
Задача - разбор -
1
co6ak
Кошковед
515 / 503 / 63
Регистрация: 12.04.2010
Сообщений: 1,392
17.08.2011, 17:52 #14
если это то, о чем я думаю, тогдаNeuralBase

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

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

Добавлено через 2 минуты
Например, последовательность Фиббоначи можно просчитать без рекурсии и длинных массивов. Два числа - и дело в шляпе
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 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, объяснить алгоритм?
1
talis
793 / 545 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 18:19  [ТС] #20
Вот, нашёл интересную страничку с визуализаторами алгоритмов дискретной математики. [страница] Там есть алгоритмы, например, работы с деревьями - а они точно применимы в динамическом программировании.

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

Вопрос по динамическому полиморфизму
Здравствуйте. Прочитал про статический и динамический полиморфизмы. Возник...

Добавление памяти динамическому массиву
пытаюсь доканать динамические массивы (vector не предлагать, с ним все ок)....

Переход от статического к динамическому массиву
Есть некая структура some_struct. Необходимо перейти от статического массива...

Какая книга по программированию обьясняет все с математикой и подробно излагает все темы?По программированию?
Не Бьерн Страуструп?А то не нравится мне у Лафоре тип изложения книги,довольно...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru