1. Динамическое программирование

Метод динамического программирования часто помогает эффективно решить задачу, переборный алгоритм для которой потребовал бы экспоненциального времени. Идея этого метода состоит в сведении исходной задачи к решению некоторых ее подзадач «меньшего размера» и использовании табличной техники для сохранения уже найденных ответов. Решение подзадач при этом происходит в порядке возрастания их размеров — от меньших к большим. Преимущество динамического программирования заключается в том, что раз уж какая-то подзадача решена, ее ответ где-то хранится и никогда не вычисляется заново [Шень 95, п. 8.1; Ахо 79, п. 2.8].

В том случае, когда исходная задача определяется одним параметром N, имеющим смысл «размера задачи», идея динамического программирования сродни идее метода математической индукции. А именно, предположим, что мы уже знаем ответ Fk на задачу размера k для всех k, меньших N, и хотим вычислить ответ для k, равного N. Если нам удастся выразить этот ответ через уже известные, то тем самым получен алгоритм решения задачи для произвольного N: отталкиваясь от нескольких начальных значений F0, F1, …, Fs, вычисляем в цикле числа Fs+1, Fs+2 и т.д. до искомого значения FN.

Решение многих задачах, представленных в этой главе, требует реализации арифметики многократной точности, называемой иначе длинной арифметикой. Алгоритмы и структуры данных, необходимые для этого, описаны в [Кнут 78, п. 4.3]. Модуль, реализующий операции с длинными числами, может быть получен на http://antosha.com/onzi/modules.html.

Как проверить свое решение?

ЗадачаПрограмма  Тесты  
1.1. Последовательности из 0 и 1 Скачать программу! Скачать тесты!
1.2. Восстановление скобок Скачать программу! Скачать тесты!
1.3. Уравнение с пропущенными цифрами Скачать программу! Скачать тесты!
1.4. Ход конем Скачать программу! Скачать тесты!
1.5. Дырокол Скачать программу! Скачать тесты!
1.6. Сжатие текста Скачать программу! Скачать тесты!
1.7. Пустоты в кубе Скачать программу! Скачать тесты!
1.8. Шаблоны с ? и * Скачать программу! Скачать тесты!
1.9. Ну и имечко! Даже и не ждите Скачать тесты!
1.10. Жадный калькулятор Скачать программу! Скачать тесты!
1.11. Взлом сети Скачать программу! Скачать тесты!
1.12. Параллельные вычисления Скачать программу! Скачать тесты!
1.13. Длинный путь в графе Скачать программу! Скачать тесты!
1.14. Навстречу друг другу Скачать программу! Скачать тесты!

Вернуться на главную страницу


Valid CSS! Valid XHTML 1.0!
Webmaster: Антон Лапунов
Используются технологии uCoz