§ 45. Динамическое программирование
- Напишите программу, которая определяет оптимальный набор бидонов в задаче 2 из параграфа. С клавиатуры или из вводится объем цистерны, количество бидонов и их размеры.
- Напишите программу, которая решает задачу 3 о куче камней заданного веса, рассмотренную в тексте параграфа.
4. У исполнителя Калькулятор две команды, которым присвоены номера:
*3. Задача о ранце. Есть N предметов, для каждого из которых известен вес р, (i = 1,..., N) и стоимость с( (£ = 1,..., JV). В ранец можно взять предметы общим весом не более №. Напишите программу, которая определяет самый дорогой набор предметов, который можно унести в ранце.
1)прибавь 1
3)умножь на 4
Напишите программу, которая вычисляет, сколько существует различных программ, преобразующих число 1 в число JV, введённое с клавиатуры. Используйте сокращённую таблицу.
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). Пират хочет пройти из юго-западного угла острова в северо-восточный, причём он может двигаться только на север или на восток. Как пирату собрать наибольшее количество монет? Напишите программу, которая находит оптимальный путь пирата и число монет, которое ему удастся собрать.