Szanowni Państwo;
Oto propozycje zadań, temat - rekurencja:
Łatwe.
rekurencyjna wersja obliczania nwd(a,b)=nwd(a-b,b) dla a>=b
obliczanie n'tego wyrazu ciągu a[1]=1, a[n+1]=2*a[n]*a[n] +1 dla n>=0
obliczanie n'tego wyrazu ciągu Fibonacciego - wersja iteracyjna i rekurencyjna
+ omówienie wad wersji rekurencyjnej
wypisywanie tekstu od tyłu - wersja rekurencyjna
szybkie potęgowanie: x^0=1 oraz x^2n=(x^n)^2 , x^(2n+1)=x*x^2n
Trudne:
wieże Hanoi
(dla bardzo dobrych studentów - szybkie obliczanie rozkładu krążków w n'tym kroku - bardzo trudne)
mergesort - sortowanie przez scalanie
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