Читать реферат по всему другому: "Динамическое программирование, алгоритмы на графах" Страница 2

(Назад) (Cкачать работу)

программирование “сверху вниз” (все предыдущие задачи решались “снизу вверх”). Для этого задачу будем решать все же рекурсивно, используя формулу (*), но ответы к уже решенным подзадачам будем запоминать в таблице. Первоначально таблица пуста (вернее заполним элементы, значение которых по формуле () равно 0 или 1, а остальные значения, например, числом -1). Когда в процессе вычислений подзадача встречается первый раз, ее решение заносится в таблицу. В дальнейшем решение этой подзадачи берется из таблицы. Таким образом мы получили прием улучшения рекурсивных алгоритмов, а “лишние” подзадачи теперь решаться не будут.

Приведем программу для решения этой задачи. var i,j,k,n:byte;

sum:longint;

table:array[1..120,1..120] of longint;

function t(n,k:byte):longint;

var i,s:byte;

begin

if table[n,k]