Эксперт

Сергей

Задать вопрос

Мы готовы помочь Вам.

Цель работы: Ознакомиться с методами динамического программирования.
Порядок выполнения работы
1. Ознакомиться с теоретическими сведениями.
2. Получить вариант задания у преподавателя.
3. Выполнить задание: написать программу на языке С++.
4. Продемонстрировать выполнение работы преподавателю.
5. Оформить отчет.
6. Защитить лабораторную работу.
Требования к оформлению отчета
Отчет по лабораторной работе должен содержать следующие разделы:
титульный лист; цель работы; задание на лабораторную работу; ход работы;
ответы на контрольные вопросы; выводы по проделанной работе.
Варианты заданий
1. Написать программу для решения задачи методами динамического программирования. Требуется подсчитать, сколько различных текстовых сообщений можно написать используя не более k нажатий на клавиатуре кнопочного телефона.
2. Написать программу для решения задачи методами динамического программирования. На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю. Входные данные: вводится одно число 0 < N < 31. Выходные данные: выведите одно число — количество маршрутов.
3. Написать программу для решения задачи методами динамического программирования. Вычислите n-й член последовательности, заданной формулами: a2n = an + 1 (n>0), a2n+2 = a2n+1 — an (n>0), a0=1, a1=1. Входные данные: вводится натуральное число n, не превосходящее 1000. Выходные данные: выведите ответ к задаче.
4. Написать программу для решения задачи методами динамического программирования. Требуется подсчитать количество последовательностей длины N , состоящих из 0 и 1, в которых никакие две единицы не стоят рядом. Входные данные: на вход программы поступает целое число N (1
N
100 ). Выходные данные: выведите количество искомых последовательностей.
5. Написать программу для решения задачи методами динамического программирования. Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки. Входные данные: в первой строке вводится одно натуральное число N ≤ 100 — количество ступенек. В следующей строке вводятся N натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх). Выходные данные: выведите одно число — наименьшую возможную стоимость прохода по лесенке.
6. Написать программу для решения задачи методами динамического программирования. В прямоугольной таблице NxM в начале игрок находится в левой
верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Входные данные: вводятся два числа N и M — размеры таблицы (1≤N≤10, 1≤M≤10). Выходные данные: выведите искомое количество способов.
7. Написать программу для решения задачи методами динамического программирования. Даны две последовательности, требуется найти длину их наибольшей общей подпоследовательности. Входные данные: в первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю. В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю. Выходные данные: требуется вывести одно число – длину наибольшей общей подпоследовательности двух данных последовательностей или 0, если такой подпоследовательности нет.
8. Написать программу для решения задачи методами динамического программирования. В государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Национальному банку решить эту задачу. Входные данные: первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, …, xN, не превосходящих 106 — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 106 —сумму, которую необходимо выдать. Выходные данные: программа должна найти представление числа S виде суммы слагаемых из множества xi, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.
9. Написать программу для решения задачи методами динамического программирования. Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более C рублей, доставка является бесплатной, при заказе на C рублей и меньше доставка стоит B рублей.
10. Вы уже выбрали товар, стоимостью A рублей. В наличии имеются еще N товаров стоимостью d1, …, dN рублей, каждый в единственном экземпляре. Их также можно включить в заказ. Как потратить меньше всего денег и получить на дом уже выбранный товар в A рублей? Входные данные: сначала вводятся числа A, B, C, N, а затем N чисел d1, …, dN. Все числа целые, 1 ≤ A ≤ 1000, 1 ≤ B ≤ 1000, 1 ≤ C ≤ 1000, 0 ≤ N ≤ 1000, 1 ≤ di ≤ 1 000 000. Выходные данные: выведите сначала суммарное количество денег, которое придется потратить. Если при этом вы планируете сделать дополнительный заказ c расчетом на бесплатную доставку, то далее выведите количество этих товаров и их номера в возрастающем порядке. Если же Вы будете оплачивать доставку сами, то далее выведите одно число –1 (минус один).
Контрольные вопросы
1. Что такое динамическое программирование?
2. Приведите основные принципы динамического программирования?
3. Какие классы задач можно решать с помощью динамического программирования? Примеры.