IMG044

INFORMATYKA

II rok, studia stacjonarne I stopnia rok ak. 2012/2013 semestr zimowy

Lista 4

Algorytmy rekurencyjne

1. Podać iteracyjny i rekurencyjny algorytm obliczania dla danej liczby naturalnej n:

a)    silni,

b)    wartości x".

c)    sumy ciągu 14-1/2 4-1/3 4- ...4-1/n

d)    n-tego elementu ciągu Fibonacciego: F1=0; F2=l; F_n=F_rvi4-F_l,.₂;

2. a) Obliczyć wartości funkcji rekurencyjnej

h(n)

0

•    n

h(2 + h(2n))

dla

dla

dla

n * 0 n > 4 n <= 4

dla n=0,1,..., 6.

b) Zdefiniowano następującą funkcję rekurencyjną: int A2( intn ){ if(n==l) return 1; e/se

if( (n%2)==0 ) return n*A2(n-2); e/se return n*A2(n-l);

}

Sprawdzić kiedy funkcja działa poprawnie, a kiedy niepoprawnie, poprawić jej definicję.

3. Podać algorytm rekurencyjny dla problemu:

a)    Wieże Hanoi. Oszacować jego złożoność czasową,

b)    znalezienia największego wspólnego dzielnika dwóch liczb.

4. Zdefiniować funkcję rekurencyjną, która:

a)    odwraca wartości tablicy T[i] i=0,..., n-1, czyli zamienia miejscami element pierwszy z ostatnim, drugi z przedostatnim itd.

b)    sprawdza czy podany tekst (zawierający wyłącznie litery) jest palindromem. Palindrom to tekst, który czytany od przodu i od tyłu brzmi identycznie np. kajak, kobyłamamałybok.

5. Dla danej tablicy T[i], gdzie i=0,..., n-1, stosując metodę bisekcji (połowienia przedziału) znaleźć metodą rekurencyjną:

a)    maksymalny element tablicy,

b)    pozycję elementu o podanej wartości, przy założeniu, że tablica jest posortowana.

2012-10-18

T. Wiśniewska