Динамическое программирование | Задачи (11 кл. 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю)


Уроки 84 - 87
Динамическое программирование
(§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качать материалы урока







Наверх