lista5

ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopnia rok akad. 2007/2008 semestr zimowy

Ćwiczenie 5

Algorytmy rekurencyjne

1. Algorytm Euklidesa znajdywania największego wspólnego dzielnika dwóch liczb naturalnych zapisać w wersji rekurencyjnej.

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

a)    silni

b)    wartości xⁿ

c)    n-tego elementu ciągu Fibonacciego: Fi=F₂=1; Fn=F_n.i+F_n-2;

3. Napisać funkcję rekurencyjną obliczania h(n) = Obliczyć wartości funkcji dla n=0, 1,..., 5.

0    dla

n    dla

h(2 + h(2n)) dla

n — 0 n > 4 n <- 4

4. Napisać funkcję rekurencyjną obliczania wartości funkcji Ackermanna dla m,neN A(0,n)=n+1

A(m,0)=A(m-l,l)    dla    (m>0)

A(m,n)=A(m-l,A(m,n-l))    dla    (m,n>0)

5.    Zdefiniowano następującą funkcję rekurencyjną:

intA2(intnK

if (n==l) return 1; else

if( (n%2)==0 ) return n*A2(n-2); else return n*A2(n-l);

>

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

6.    Zdefiniować funkcję rekurencyjną, która odwraca wartości tablicy T[i] i=0,..., n-1, czyli zamienia miejscami element pierwszy z ostatnim, drugi z przedostatnim itd.

a) Sprawdzić rekurencyjnie czy podany tekst (zawierający wyłącznie litery) jest paiindromem. Palindrom to tekst, który czytany od przodu i od tyłu brzmi identycznie np. kajak, kobyła mamałybok.

7.    Znaleźć maksymalną wartość w tablicy T[i], gdzie i=0, ..., n-1 metodą rekurencyjną czyli napisać funkcję, która podzieli tablicę na dwie połowy i wywoła swoje kopie na podtablicach. W przypadku, gdyby niemożliwy jest podział (tablica ma tylko jeden element) funkcja ma zwrócić wartość równą wartości tego elementu. Funkcja po wywołaniu dwóch swoich kopii porównuje wartości przez nie zwracane i zwraca tę większą.

Sprawdzić, ile razy wykonywana jest powyższa funkcja dla n=20.

8*. Napisać program, który sprawdzi, czy jest możliwe przejście wszystkich krawędzi i przekątnych ścian sześcianu w taki sposób, aby na żadnej z nich nie przebywać dwa razy. 2007-10-30