Тема: Задача на динамическое программирование

Задача: Даны n последовательных столбиков. Кузнечик находится на первом столбе, умеет прыгать на 1,2,...,k столбиков. Найти количество вариантов, которым он может допрыгать до n-го столба.

Program 112;

var N,i,j,K:integer;

a:array[1..20] of longint;

begin

write('N= '); read(N);

write('K= '); read(K);

a[1]:=1;

for i:=2 to N do

for j:=i-1 downto i-k do begin

if j=0 then break;

inc(a[i],a[j]);

end;

writeln('Ответ: ', a[N]);

end.

Программа работает при 1<=K,N<=20

В каждом элементе a[i] - хранится значение количества вариантов, которым можно достичь столбик с номером i. А расчитывается это значение так: суммируются значения для предыдущих k столбиков.

Динамическое программирование

Задача: Черепашка

На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной.
Определить эту сумму.

Решение

Формат входных данных:

Первая строка - N размер доски.Далее следует N строк, каждая из которых содержит N целых чисел, представляющих доску.

Формат выходных данных:

Одно число - максимальная сумма.

Пусть нам известен «максимальный» путь для всех клеток, кроме правой нижней (функция F (X, Y)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение:

Function F (x, y: integer):longint;

Begin

If B [x, y] = -1 then

If F(x-1, y) > F(x, y-1)

Then B [x, y]: = F(x-1, y) + A[x, y]

Else B [x, y]: = F(x, y-1) + A[x, y];

F: = B [x, y]

End;

Теперь необходимо подумать о граничных условиях. Логически правильнее было бы посчитать нашу функцию для левой и верхней границы. Это делается легко, так как для этих клеток существует только один маршрут (непосредственно вдоль границы). Но еще проще ввести в рассмотрение фиктивные нулевые строку и столбец и присвоить им нулевые значения. Действительно, эти клетки, в принципе, недостижимы, поэтому максимальная сумма равна нулю.

Итеративное заполнение массива также довольно просто. После введения граничных условий (любых из рассматриваемых выше) дальнейшее заполнение осуществляется двойным циклом:

For i: =1 to N do

For j: =1 to N do

If B [i-1, j] >B[i,j-1]

Then B[i, j]: = B [i-1, j] + A[i, j]

Else B[i, j]: = B[i,j-1] + A[i, j];

Тема: М етод перебора вариантов, отсечение перебора

Задача «Вырубка деревьев»

Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет N деревьев, расстояния между соседними деревьями одинаковы.

После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.

Входные данные

Входной файл INPUT.TXT содержит два целых числа M и N (0 <= M <= N <= 1000).

Выходные данные

В выходном файле OUTPUT.TXT должно содержаться одно число - искомое количество способов.

Комментарии

Требуется написать программу, которая по заданным числам N и M определит, сколько существует способов вырубки некоторых из N деревьев так, чтобы после вырубки осталось M деревьев и соседние деревья находились на равном расстоянии друг от друга.

Примечания

Зафиксируем расстояние между деревьями после вырубки. Если оно равно d, то возможно n – d(m – 1) – m + 1 способов вырубить деревья. Суммируя по всем d, получаем ответ.

Если у нас есть 0 деревьев и 0 деревьев должно остаться после вырубки, то существует один вариант вырубки - это надо учитывать при решении задачи.