lista 4 2

ALGORYTMY I STRUKTURY DANYCH - ćwiczenia

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 1 + 1/2 +1/3 + ...+l/n d)    n-tego elementu ciągu Fibonacciego: F1=0; F2=		i; f0	= Fn.x+Fn.2;
2. a) Obliczyć wartości funkcji rekurencyjnej
	0	dla	n = 0
/;(«) =	n	dla	n > 4
	/;(2 + h(2n))	dla	n <= 4

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

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.

2012-10-22

•W"**’"¹ J i «£ ^f j k/wtkó*^ ^^hT

T. Wiśniewska

1

   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.