Лабораторная работа ЛИТА на тему "Динамическое программирование"

Цель: формирование практических навыков применения метода динамического программирования для построения эффективных алгоритмов решения задач оптимизации.

Задачи: оценить временную эффективность решения полным перебором и решения методом динамического программирования, в зависимости от размера ввода.

Задание:

На столе находится кучка из n спичек, и два игрока по очереди берут спички из кучки. Первому игроку разрешается взять от 1 до k спичек. А затем игроки могут брать любое количество спичек, но не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Проигрывает тот, кто возьмет последнюю спичку. Требуется рассчитать количество спичек, которое первый игрок должен взять на первом ходу, чтобы выиграть при любой игре второго игрока, если, конечно, такие варианты для первого игрока есть.

Отчет содержит листинг переборного алгоритма и алгоритма с использованием динамического программирования (Java), результаты выполнения этих алгоритмов.