Funkcje rekurencyjne

Symbol Newtona

Zastanów się, dlaczego ten program tak długo działa, jak będą przebiegały obliczenia np. dla newton(10,5)? Sprawdź, co to jest programowanie dynamiczne.

Generowanie permutacji

Sortowanie Merge Sort

1. Jeśli n=1, to wektor jest posortowany, koniec;
2. Dla n>1 podziel wektor na dwa "mniej więcej" równe wektory w1 i w2;
3. Posortuj wektory w1 i w2 algorytmem MergeSort;
4. Scal wektory w1 i w2 do wektora posortowanego, wykorzystując, że są one posortowane.

Program sortujący wektor liczb całkowitych: MergeSort.

Krzywa Koch'a

Definiujemy rekurencyjnie następujący sposób ciąg krzywych K(k):

1. Jeśli k=0, to K(0) jest odcinkiem;
2. Dla k>0 K(k) powstaje przez odpowiednie połączenie czterech kopii krzywych K(k-1) (patrz ilustracja - poszczególne kopie krzywych stopnia o jeden mniejszego wyróżniono różnymi kolorami).

Trójkąt Sierpińskiego

1. TS(0) to wypełniony trójkąt;
2. Dla k>0 zbiór TS(k) powstaje poprzez sklejenie 3 mniejszych kopii TS(k-1) (patrz rysunek).

Przykładowe zadania

Napisz funkcję rekurencyjną dla znajdowania liczb Fibonacciego.

Napisz funkcję rekurencyjną obliczającą największy wspólny dzielnik dwóch liczb.

Napisz funkcję rekurencyjną znajdującą wszystkie możliwe sumy składników naturalnych dające w wyniku zadaną liczbę n. Np: dla n=3 są to 3, 2+1, 1+1+1.

Napisz funkcję rekurencyjną dla znajdowania liczb Fibonacciego, która zapamiętuje już obliczone wartości (programowanie dynamiczne)

Napisz funkcję rekurencyjną, która znajduje położenie k hetmanów na szachownicy k*k w taki sposób aby żadne dwa nie stały w tej samej linii, kolumnie i przekątnej (nie szachowały się).

Napisz program, który oblicza kolejne punkty krzywej K[n], dla ustalonego n.

Wróć