Szanowni Państwo;

Oto propozycje zadań, temat - rekurencja:

Łatwe.

1. rekurencyjna wersja obliczania nwd(a,b)=nwd(a-b,b) dla a>=b

2. obliczanie n'tego wyrazu ciągu a[1]=1, a[n+1]=2*a[n]*a[n] +1 dla n>=0

3. obliczanie n'tego wyrazu ciągu Fibonacciego - wersja iteracyjna i rekurencyjna

+ omówienie wad wersji rekurencyjnej

4. wypisywanie tekstu od tyłu - wersja rekurencyjna

5. szybkie potęgowanie: x^0=1 oraz x^2n=(x^n)^2 , x^(2n+1)=x*x^2n

Trudne:

1. wieże Hanoi

(dla bardzo dobrych studentów - szybkie obliczanie rozkładu krążków w n'tym kroku - bardzo trudne)

2. mergesort - sortowanie przez scalanie

3. obliczyć na ile sposobów można wyrazić liczbę m w postaci sumy składników naturalnych

z których każdy nie jest większy niż n

f((1,n)=1 dla kazdego n

f(m,1)=1 dla każdego m

f(m,n)=f(m,m) dla m<n

f(m,m)=1+f(m,m-1)

f(m,n)=f(m,n-1)+f(m-n,n) dla m>n

+ omówienie wad wersji rekurencyjnej

Rozwiązanie większości tych zadań znajdują się w zbiorku 50 zadań (patrz dziekanat).

Z poważaniem,

Piotr Sapiecha