Lekcja 5
algorytmy rekurencyjne

Zadanie 90
Ciąg Fibonacciego definiujemy następujaco: f(1)=1, f(2)=1, f(k)=f(k-1)+f(k-2).
Napisz algorytm obliczający k-ty element ciągu Fibobnacciego na dwa sposoby:

iteracyjnie; zaprogramuj funkcję Fib_I(k),

używając funkcji rekurencyjnej Fib_R(k).

Sprawdź na przykładzie (np dla 7-mego elementu ciągu), która metoda jest szybsza ...

Uwaga: W jaki sposób funkcja "zwraca" wartość ? Odp:

funkcja Potega(a,b) 
  x<- 1
  for i<- 1 to b do
    x<- x*a
  Potega<- x

Zadanie 91
Zdefiniuj następujące funkcje (koniecznie używając rekurencji):

n^k; Potega(n,k); korzystając z własności:
n^k = n*n^(k-1), n^0=1, n^(-k)=1/(n^k), (k może być <0)

n!; Silnia(n); korzystając z własności:
n! = n*(n-1)!, 0!=1

symbol Newtona "n po k"; Newton(n,k); korzystając z własności:
Newton(n,k)=Newton(n-1,k-1) + Newton(n-1,k); Newton(n,n)=1, Newton(n,0)=1

Uwaga: Pamiętaj że rekurencja nie może być "nieskończona"!

Zadanie 92
Zaimplementuj procedury wypisujące wszystkie "obiekty kombinatoryczne" danego typu (np K-elementowe kombinacje zbioru N-elementowego). Przy użyciu rekurencji jest to bardzo proste zadanie !. Należy zaimplementować procedury wypisujące następujące obiekty:

K-elementowe wariacje Z powtórzeniami zbioru N-elementowego {1, ..., N}
są to wszystkie ciągi K-elementowe zbioru N-elementowego
ich liczba wynosi = N^K
K-elementowe wariacje BEZ powtórzeń zbioru N-elementowego
ich liczba wynosi = N!/(N-K)!
K-elementowe kombinacje zbioru N-elementowego
są to wszystkie podzbiory K-elementowe zbioru N-elementowego
[przypominam że {1,2} i {2,1} to ten sam zbiór !]
ich liczba wynosi = Newton(N,K)
K-elementowe kombinacje Z powtórzeniami zbioru N-elementowego
ich liczba wynosi = Newton(N+K-1,K)

Wskazówka: Jak zaprogramować WariacjeZPowtorzeniami(i) ?
Używamy tablicy Wynik[1..n] do przechowywania pojedynczej wariacji.
W procedurze WariacjeZPowtorzeniami(i), w pętli "for j<- 1 to N do" wykonujemy:
1) Wynik[i]<- j
2) uruchamiamy rekurencyjnie WariacjeZPowtorzeniami(i+1)
Zasada działania procedury jest następująca:
zakres tablicy Wynik[1..i-1] zawiera fragment wariacji utworzony przez poprzednie wywołania procedury;
procedura WariacjeZPowtorzeniami(i) bezpośrednio modyfikuje element Wynik[i];
rekurencyjne wywołanie WariacjeZPowtorzeniami(i+1) generuje wszystkie możliwe wariacje w zakresie Wynik[i+1..n];
oczywiście gdy wszystkie elementy tablicy Wynik mają przypisaną wartość to należy ją wypisać.

Lekcja 5 algorytmy rekurencyjne

Lekcja 5
algorytmy rekurencyjne