Podaj rekurencyjny algorytm wyznaczający:
(a) \(\displaystyle{ k^{n}}\), gdzie \(\displaystyle{ k}\) i \(\displaystyle{ n}\) są pewnymi dodatnimi liczbami naturalnymi,
(b) sumę elementów ciągu \(\displaystyle{ n}\) liczb naturalnych, zapisanego w tablicy \(\displaystyle{ A[1..n]}\).
Narysuj drzewo wywołań rekurencyjnych rozważanego algorytmu. Wytypuj operację dominujacą
w owym algorytmie i przedstaw równanie rekurencyjne opisujące liczbę jej wykonań. Zaproponuj
rozwiązanie równania.
Podaj algorytm rekurencyjny.
-
- Użytkownik
- Posty: 450
- Rejestracja: 3 kwie 2007, o 18:38
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska
- Podziękował: 12 razy
- Pomógł: 68 razy
Podaj algorytm rekurencyjny.
Dedemonn, przedstawiłem tylko ideę, a nie pełne równanie rekurencyjne, które opisuje algorytm.
W pełni będzie tak:
\(\displaystyle{ \begin{cases}k^{n} = k^{n-1} * k \quad n>1\\k^{n} = k \quad n= 1\end{cases}}\)
W pełni będzie tak:
\(\displaystyle{ \begin{cases}k^{n} = k^{n-1} * k \quad n>1\\k^{n} = k \quad n= 1\end{cases}}\)