ALG$2

242

Rozdział 9, Zaawansowane techniki programowania

miejscach), chociaż w zoptymalizowanej wersji można by tę część wbudować w pętlę główną programu. Do obliczenia wartości P(i, j) potrzebna jest znajomość dwóch sąsiednich komórek: dolnej - P(i.j-l) oraz tej znajdującej się z lewej strony - P(i-I, jj. Uwaga ta prowadzi nas do spostrzeżenia, że naturalnym sposobem obliczania wartości P(i,j) będzie posuwanie się „zygzakiem” zaznaczonym na rysunku 9-3.

Rys. 9 - J.

„ Dwuwymiarowy " wiór rekurencyjny.

t|5||5|

P(i-ld)	t
	1 P(i-j-l)

Gdy mamy te wszystkie informacje, realizacja programowa jest natychmiastowa:

const n-5;

void dynam(doubla P[n][nl) int i,j;

// inicjacja

for(i=l;i<n;i++)

P[i] [0]= 0; PIO] [i)= i;

for(j=l;j<n;j++)    II progresja

for(i=l;i<n;i++)

P[i][j]—(P[i—1][j]+P[i][j-l])/2.0;

Nietrudno jest zauważyć, że program powyższy jest dokładnym odbiciem wzoru rekurencyjnego - jedyny nasz wysiłek polega w zasadzie na tym. żeby znaleźć prawidłowy sposób wypełniania tablicy. Celowo podkreślam, że prawidłowy, bowiem w przypadku rekurencji dwu- i więcej wymiarowych (jeśli możemy sobie na takie określenie pozwolić...) możemy bardzo łatwo popełnić błąd polegający na próbie wykorzystania wartości z tablicy, które w danym etapie nie są jeszcze obliczone. Tego typu potknięcia są czasami bardzo trudne do wykrycia, więc warto przy tym szczególnie uważać.