ALG$0

240 Rozdział 9. Zaawansowane techniki programowania

„programu wanie dynamiczne "

•    mając dane rozwiązanie problemu elementarnego, wylicz na jego podstawie

•    problem wyższego rzędu i kontynuuj obliczenia, aż do otrzymania rozwiązania rzędu N.

Nowa technika ma pewien posmak optymalności: raz znalezione rozwiązanie pewnego pod-problemu zostaje zarejestrowane w tablicy i w miarę potrzeb jest później wykorzystywane. Nie był to bynajmniej przypadek metody „dziel-i-rządź”, która pozwalała na wielokrotne wyliczanie tych samych wartości.

Nowo poznaną metodę zilustrujemy dwoma przykładami o różnym stopniu skomplikowania, zaczynając od... doskonale nam zimnego problemu obliczania elementów ciągu Fibonacciego (patrz §2.4.1). Przypomnimy (po raz kolejny) definicję tego ciągu:

M 0) = l

fih( n) = f(n — 1) + fib(n) gdzie n>2

Rozwiązanie rekurencyjne testowaliśmy już kilkakrotnie, spróbujmy teraz zaadoptować rekurencyjną procedurę obliczania tego ciągu do podanych powyżej zasad konstrukcji programu wykorzystujących programowanie dynamiczne:

koncepcja - wzór rekurencyjny już mamy, pozostaje tylko zadeklarować tablicę fibfn] do składowania obliczanych wartości;

inicjacja - początkowymi wartościami w tablicy fib będą oczywiście warunki początkowe:Jih/0J=l ifih[J]=l\

progresja algorytmu - ten punkt zależy ściśle od wzoru rekurencyjnego, który implementujemy przy pomocy tablicy. W naszym przypadku wartość\\fib[ij w tablicy (dla i < 2) jest suma dwóch poprzednio obliczonych wartości: fibfi-lj i fib[i-2], Obie te wartości zostały zapamiętane w tablicy, zupełnie jak w programie rekurencyjnym, który zapamiętuje je... na stosie wywołań rekurencyjnych.

Zauważmy jednak, że tej analogii nie można posunąć zbyt daleko, bowiem nasze postępowanie ma charakter sekwencji instrukcji elementarnych bez dodatkowych wywołań proceduralnych, tak jak to czyni każdy program re-kurencyjny.

Powyższe uwagi są zilustrowane na rysunku 9-2.