ALG$1

9.3. Programowanie dynamiczne 241

9.3. Programowanie dynamiczne 241

Rys. 9- 2.

Obliczanie warto ści cicigu liczb Fibonacciego.

I I 2    3    5    8 I3 21

0    1    2    3    4    5    6    7

Zupełnie już dla formalności podam procedurę, która realizuje omówione uprzednio obliczenia:

void fib dyn(int x, int f[])

I

ftOj-1?

£|ij=i;

for(int i=2;i<x;i++) fli]=f[i-1]+f[i-2];

I

Nieco bardziej skomplikowana sytuacja występuje w przypadku równań reku-rencyjnych posiadających więcej niż jedną zmienną. Popatrzmy na następujący wzór:

m/) =

1

o

P(i = \,j) i /*(/,./-1)

2

jeśli i = 0 oraz j > 0, jeśli i > 0 oraz j = 0. jeśli i > 0 oraz j > 0.

Mamy tu do czynienia z dwiema zmiennymi, i oraz j, interesuje nas obliczenie wartości parametru P. Powyższy wzór jest dość nieprzyjemny już na pierwszy rzut oka - można również udowodnić, że jest bardzo kosztowny, jeśli chodzi o czas obliczeń. Mamy zatem doskonały przykład dowodzący, żc jeśli nic musimy stosować rekurencji, to najlepiej byłoby tego w ogóle nie czynić... pod warunkiem posiadania alternatywnych dróg rozwiązania.

Technika programowania dynamicznego taką drogę podpowiada. Sposób obliczenia wzoru rekurencyjnego jest trywialny, jeśli wpadniemy na pomysł użycia tablicy dwuwymiarowej, której „współrzędne” pozioma i pionowa będą odpowiadać zmiennym i oraz j. Popatrzmy na rysunek 9-3 przedstawiający ogólną ideę programu obliczającego wartości P(i, j).

Z uwagi na specyfikę problemu wygodnie będzie zainicjować tablicę już na samym wstępie warunkami początkowymi (zera i jedynki w odpowiednich