Урок 50
Динамическое программирование
(§45. Динамическое программирование)
Содержание урока
Что такое динамическое программирование?
Задачи
Задачи
1. Напишите программу, которая определяет оптимальный набор бидонов в задаче 2 из параграфа. С клавиатуры или из файла вводится объём цистерны, количество типов бидонов и их размеры.
2. Напишите программу, которая решает задачу 3 о куче камней заданного веса, рассмотренную в тексте параграфа.
*3. Задача о ранце. Есть N предметов, для каждого из которых известен вес pi (i = 1,..., N) и стоимость сi (i = 1,..., N). В ранец можно взять предметы общим весом не более W. Напишите программу, которая определяет самый дорогой набор предметов, который можно унести в ранце.
4. У исполнителя Калькулятор две команды, которым присвоены номера:
1)прибавь 1
3) умножь на 4
Напишите программу, которая вычисляет, сколько существует различных программ, преобразующих число 1 в число N, введённое с клавиатуры. Используйте сокращённую таблицу.
5. У исполнителя Калькулятор три команды, которым присвоены номера:
1) прибавь 1
2) умножь на 3
3) умножь на 4
Напишите программу, которая вычисляет, сколько существует различных программ, преобразующих число 1 в число N, введённое с клавиатуры.
6. У исполнителя Калькулятор две команды, которым присвоены номера:
1) прибавь 1
2) увеличь каждый разряд числа на 1
Сколько есть программ, которые число 24 преобразуют в число 46?
7. У исполнителя Калькулятор две команды, которым присвоены номера:
1) прибавь 1
2) увеличь каждый разряд числа на 1
Сколько существует программ, которые число 26 преобразуют в число 49?
*8. Прямоугольный остров разделён на квадраты так, что его размеры — N х М квадратов. В каждом квадрате зарыто некоторое число золотых монет, эти данные хранятся в матрице (двумерном массиве) Z, где Z[i, j] — число монет в квадрате с координатами (i, j). Пират хочет пройти из юго-западного угла острова в северо-восточный, причём он может двигаться только на север или на восток. Как пирату собрать наибольшее количество монет? Напишите программу, которая находит оптимальный путь пирата и число монет, которое ему удастся собрать.
Следующая страница 
§45. Динамическое программирование
Cкачать материалы урока
