Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Доброго времени суток, уважаемые эксперты!

Не могли бы вы мне рассказать о "Динамическом программировании" (ДП)


И вот помочь с задачей после рассказа

Заранее спасибо!

Задача в приложении к вопросу:

Вопрос задал: Ruslan (статус: 1-ый класс) Вопрос отправлен: 18 декабря 2009, 23:44 Состояние вопроса: открыт, ответов: 1.

Ответ #1. Отвечает эксперт: Паровоз

Здравствуйте, Ruslan!

О динамическом программирование лучше всего почитать. В интернете полно информации на эту тему, например, здесь. Возьмем как пример Вашу задачу. Несложно написать рекуррентную формулу для вычисления количесства маршрутов f(k,n). Заяц может прыгнуть на последнюю ступеньку n с n-1,n-2,...,n-k. Поэтому
f(k,n)=f(k,n-1)+f(k,n-2)+...+f(k,n-k)
Эту формулу можно переписать в более простой форме
f(k,n)=2f(k,n-1)-f(k,n-k-1)
Однако, если вычислять по этой формуле рекурсивно, то несколько раз приходится вычислять уже ранее вычисленные значения и получается лишняя работа. Можно использовать кеширование: запоминание предыдущих результатов. Пусть n и k задаются константами, например,

const
  n=40;
  k=3;

var
  a:array[-k-1..n] of Int64;

procedure InitArray;
var
  i:Integer;
begin
  for i:=-k-1 to -1 do a[i]:=0;
  a[0]:=1;
  a[1]:=1;
end;

function HowMany:Int64;
var
  i:Integer;
begin
  for i:=2 to n do a[i]:=2*a[i-1]-a[i-k-1];
  Result:=a[n];
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  InitArray;
  Edit1.Text:=IntToStr(k)+' '+IntToStr(n)+' '+IntToStr(HowMuch);
end;

Ответ отправил: Паровоз (статус: 10-ый класс) Время отправки: 19 декабря 2009, 20:04

Мини-форум вопроса

Паровоз (статус: 10-ый класс), 19 декабря 2009, 20:06 [#1]: P.S. В конце, разумеется, не HowMuch, а HowMany. Кроме того, для k=300, n=300 типа Int64 не хватит.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.