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

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

Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

Подробнее »



Вопрос # 3 549

/ вопрос открыт /

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

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


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

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

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

Приложение:
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12. 3 10 274


Ruslan Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задал: 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


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

Всего сообщений: 1; последнее сообщение — 19 декабря 2009, 20:06; участников в обсуждении: 1.
Паровоз

Паровоз (статус: 10-ый класс), 19 декабря 2009, 20:06 [#1]:

P.S. В конце, разумеется, не HowMuch, а HowMany. Кроме того, для k=300, n=300 типа Int64 не хватит.

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

Версия движка: 2.6+ (26.01.2011)
Текущее время: 30 мая 2023, 04:28
Выполнено за 0.03 сек.
Рейтинг@Mail.ru