T(n,0) = n dla n >= 0
T(0,m) = m dla m >= 0
T(n,m)= T(n – 1, m)+2T(n, m – 1) dla n>0 i m>0
Rekurencyjnie jest łatwo, ale jak zrobić to nierekurencyjnie w C?
Z góry dziękuję za pomoc.
T(n,0) = n dla n >= 0
T(0,m) = m dla m >= 0
T(n,m)= T(n – 1, m)+2T(n, m – 1) dla n>0 i m>0
Rekurencyjnie jest łatwo, ale jak zrobić to nierekurencyjnie w C?
Z góry dziękuję za pomoc.
Dla wywołań rekurencyjnych zastosuj pentlę while z odpowiednim warunkiem wyjścia.
Nierekurencyjnie jest równie prosto, zrób sobie tablice o wymiarach n x m, pierwszy wiersz to same n, pierwsza kolumna to same m, a potem pętelka po pętelce (pseudkod):
for(int i =1 i<n; ++i)
{
for(int j =1 j<m; ++j)
{
tablica[i][j] = tablica[i-1][j] + 2*tablica[i][j-1];
}
}
jak już zrozumiesz rozwiązanie na dwóch wymiarach, to możesz je łatwo sprowadzić do rozwiazania które przechowuje tylko ostatni wiersz:
for(int i =1 i<n; ++i)
{
for(int j =1 j<m; ++j)
{
tablica[j] = tablica[j] + 2*tablica[j-1];
}
}