Wprowadzenie do

algorytmów

zbiór zadań

część II

DLA KAŻDEGO ALGORYTMU NAPISZ PROGRAM (NP. W JĘZYKU C++) IMPLEMENTUJĄCY TEN ALGORYTM.

5. Algorytmy rekurencyjne

Zad. 5.1.

Napisz rekurencyjny algorytm obliczania silni danej liczby naturalnej n.

Wskazówka:

Korzystamy z definicji silni:



1

dl

a n  0

n!  n( n )1! dl

a n



1

Zad. 5.2.

Napisz rekurencyjny algorytm mnożenia dwóch liczb naturalnych m i n (gdzie m, n  0 ).

Wskazówka:

Korzystamy z definicji mnożenia:

 m

dl

a n

 1

m  n   m m[ n(  )1] dl a n



1

Zad. 5.3.

Napisz rekurencyjny algorytm obliczania wartości wyrażenia n 2 , gdzie n jest liczbą naturalną.

Wskazówka:

Korzystamy z następującej definicji:



1

dl

a n  0



2

n

 n 

2  22  dl

a n parzystych







2





 n 

div  





 2  

2  2

dl

a n nieparzystych













gdzie div jest częścią całkowitą z dzielenia.

Zad. 5.4.

Zaproponuj rekurencyjny algorytm odwracania kolejności elementów w tablicy.

Zad. 5.5.

Zaproponuj rekurencyjny algorytm sprawdzania czy w danej tablicy występuje określony element.

Zad. 5.6.

Zaproponuj rekurencyjny algorytm obliczania elementów ciągu Fibonacciego:



0

dl

a n  0



fib ( n)  

1

dl

a n  1

 fib( n )1  fib( n

dl

)

2

a n  1

Co można powiedzieć o efektywności rekurencyjnego rozwiązania powyższego problemu?

Zad. 5.7.

Dany jest następujący ciąg:

n 1

S( n)   !

0 i

i

Napisz rekurencyjną definicję ciągu S( n) . Zaproponuj rekurencyjny algorytm obliczania n-tego wyrazu ciągu S( n) .

Zad. 5.8.

Dany jest ciąg Q( n) zdefiniowany rekurencyjnie:



1

dl

a n  0



Q( n)  

n



dl

a n  0

 Q( n  )

1

Napisz rekurencyjny algorytm obliczania n-tego wyrazu ciągu Q( n) . Narysuj drzewo wywołań funkcji rekurencyjnej Q( n) dla n  4 .

Zad. 5.9.

Napisz rekurencyjną definicję potęgi n a , gdzie n  N . Zaproponuj rekurencyjny algorytm obliczania wartości wyrażenia n

a dla dowolnego n.

Zad. 5.10.

Dane są ciągi zdefiniowane rekurencyjnie:



1

d

la n  0



a)

(

A )

n  

2



d

l

a n  0

 (

A n  )

1



0

dl

a n  0

b) B( )

n  2 B( 1

n- ) 

dl

1

a n  0



1

dl

a n  0

c) C( n)   C( n )1 n dl a n  0



1

d

l

a n  0



d) D( )

n   D(n 1 )



d

l

a n  0



n



0

dl

a n  0



e) E( n)  

1

dl

a n  1

 E( n  )1  2 E( n  2)

dl

a n  1



1

dl

a n  0



f) F( )

n  

2

dl

a n  1

 n F( n  )1 F( n )2

dl

a n  1

Napisz rekurencyjne algorytmy obliczania n-tych wyrazów tych ciągów.

Zad. 5.11.

Podaj rekurencyjny opis następujących ciągów:

a) ciągu arytmetycznego o pierwszym wyrazie równym 1 i różnicy równej 2, b) ciągu geometrycznego o pierwszym wyrazie równym 5 i ilorazie równym 2.

Napisz rekurencyjne algorytmy obliczania n-tych wyrazów tych ciągów.

6. Metody projektowania algorytmów

Zad. 6.1.

Stosując metodę "dziel i rządź" ułóż algorytm przeszukiwania ciągu liczb w celu znalezienia maksimum.

Zad. 6.2.

Dany jest uporządkowany ciąg liczb (od najmniejszej do największej). Stosując metodę "dziel i rządź" ułóż algorytm wyszukiwania pozycji danej liczby w tym ciągu.

Zad. 6.3.

Korzystając z techniki programowania dynamicznego wyznacz wartość wyrażenia:



1

d

l

a i  0, j  0



P( i, j)  

0

d

la i  ,

0 j  0

 P( i  ,1 j)  P( , i j  )1 dl a i  ,0 j 0



2

dla i  ,

5 j  5 .

Zad. 6.4.

Korzystając z techniki programowania dynamicznego ułóż algorytm wyznaczania współczynnika

 n 

dwumianowego   .

 m

Wskazówka:

Korzystamy z zależności:

 n   n  

1

 n 1 





  

 



 m  m   m 1

Zad. 6.5.

Korzystając z techniki programowania dynamicznego napisz algorytm obliczania elementów ciągu Fibonacciego:



0

dl

a n  0



fib ( n)  

1

dla n  1

 fib( n  )1  fib( n 2 dl

)

a n  1

Zad. 6.6.

Korzystając z techniki programowania dynamicznego napisz algorytmy obliczania n-tych wyrazów ciągów z zadania 5.10.

Zad. 6.7.

Dany jest zbiór liczbowy:

X  ,

1

{

,

3

,

2

,

5

,

4

,

6 7

}

12

,

11

,

10

,

9

,

8

,

oraz dane są następujące podzbiory tego zbioru:

X  ,

1

{

3

,

2 ,

,

5

,

4

}

6

1

X  5

{ , ,

6 ,

8 }

9

2

X  ,

1

{ 4,7 }

10

,

3

X  { ,

2 ,

5 7 8

,

}

11

,

4

X  ,

3

{ 6 9

,

}

12

,

5

X 

}

11

,

10

{

6

Stosując algorytm zachłanny wyznacz minimalny zbiór podzbiorów, których elementy pokrywają cały zbiór X.

Czy w tym przypadku znalezione minimalne pokrycie zbioru X jest rozwiązaniem dokładnym, czy też przybliżonym?

Zad. 6.8.

Wykorzystując metody zachłanne (algorytm Kruskala, algorytm Prima) znajdź minimalne drzewo rozpinające dla następującego grafu:

7. Poprawność logiczna i numeryczna algorytmów.

Zad. 7.1.

Udowodnij metodą niezmienników pętli poprawność algorytmu mnożenia liczb naturalnych m, n: m, n  N  }

0

{

x  m  n

START

czytaj (m,n)

x=0

y=m

x=x+n

y=y-1

N

T

y=0

wypisz(x)

STOP

Zad. 7.2.

Udowodnij metodą niezmienników pętli poprawność iteracyjnego algorytmu obliczania silni liczby naturalnej n.

Zad. 7.3.

Udowodnij metodą niezmienników pętli poprawność algorytmu dzielenia z resztą dwóch liczb naturalnych m, n:

m, n  N  }

0

{

m  q  n  r

q – część całkowita z dzielenia, r – reszta z dzielenia START

czytaj (m,n)

q=0

r=m

T

N

r>=n

r=r-n

wypisz(q,r)

q=q+1

STOP

Zad. 7.4.

Udowodnij metodą niezmienników pętli poprawność algorytmu wyznaczania największego wspólnego dzielnika liczb naturalnych m, n: m, n  N  }

0

{

x  NWD( m, )

n

START

czytaj (m,n)

x=m

y=n

T

N

x<>y

T

N

x>y

wypisz(x)

x=x-y

y=y-x

STOP

Zad. 7.5.

Wykorzystując metodę niezmienników pętli określ, jaką wartość będzie mieć zmienna y po wykonaniu następującego algorytmu:

START

x=10

y=0

z=200

T

N

z>100

z=z-2

wypisz(y)

y=y+2x

STOP

Zad. 7.6.

Wykorzystując metodę niezmienników pętli określ, jaką wartość będzie mieć zmienna m po wykonaniu następującego algorytmu:

START

m=1

n=2

p=0

T

N

p<10

p=p+1

wypisz(m)

m=m*n

STOP

Zad. 7.7.

Znajdź rozwiązanie układu równań:

 a x  b y  c

 1

1

1

 a x  b y  c

2

2

2

dla danych:

 przypadek I:

a  3

1

b  4 127

,

1

c 

,

15 41

1

a  1

2

b 

2

374

,

1

c  5 1

, 47

2

 przypadek II:

a  2

1

b  1

1

c  4

1

a  1

2

b 

2

2

c  3

2

a

mnożąc pierwsze równanie przez 2 i odejmując od drugiego.

a 1

Dla każdego przypadku obliczenia wykonaj dwukrotnie: najpierw na liczbach o precyzji ośmiu cyfr znaczących, a następnie na liczbach o precyzji czterech cyfr znaczących. Porównaj otrzymane wyniki. Co jest przyczyną tak dużego błędu dla danych z przypadku I? Czy wykorzystany do obliczeń algorytm jest poprawny numerycznie?

Zad. 7.8.

Dana jest funkcja f ( n) opisana wzorem rekurencyjnym:



1 dl

a n  1



f ( n)   f ( n  2) * n dl a n parzystego

 f ( n  )1* n dl

a n nieparzystego

Czy algorytm rekurencyjny obliczający wartość funkcji f ( n) dla n  2 jest stabilny (czy proces rekurencyjny jest zbieżny)?

8. Złożoność obliczeniowa algorytmów.

Zad. 8.1.

Oszacuj złożoność czasową algorytmu mnożenia dwóch macierzy kwadratowych o rozmiarze n  n .

Dla dwóch macierzy A  [ a ]

B  [ b ]

ij n n oraz

ij n n elementy macierzy C  A  B wyznaczane są ze n

wzoru: c 

a

b dla i  ,

1 ,...,

2

n , j  ,

1 ,...,

2

n .

ij

 

ik

kj

k 1

Zad. 8.2.

Dana jest tablica n-elementowa. Oszacuj pesymistyczną złożoność czasową algorytmu sortowania bąbelkowego tej tablicy:

for(int i=1; i<n; i++)

{

for(int j=n-1; j>=i; j--)

{

if(tab[j-1]>tab[j])

{

t=tab[j-1]; tab[j-1]=tab[j]; tab[j]=t;

}

}

}

Zad. 8.3.

Dana jest tablica n-elementowa. Oszacuj złożoność czasową algorytmu sortowania przez selekcję tej tablicy:

for(int i=0; i<n-1; i++)

{

min=i;

for(int j=i+1; j<n; j++)

{

if(tab[j]<tab[min]) min=j;

}

t=tab[min]; tab[min]=tab[i]; tab[i]=t;

}

Zad. 8.4.

Oszacuj złożoność czasową algorytmu znajdowania n kolejnych liczb pierwszych większych od 3.

licznik=0;

liczba=4;

while(licznik < n)

{

pierwsza=true;

if(liczba%2 != 0)

{

for(int i=3; i*i<=liczba; i=i+2)

{

if(liczba%i == 0)

{

pierwsza=false; break;

}

}

}

else

{

pierwsza=false;

}

if(pierwsza == true)

{

licznik++;

}

liczba++;

}

Zad. 8.5.

Uporządkuj w kierunku rosnącym następujące złożoności obliczeniowe algorytmów: O( n), O(log n), O( !

n ), (2 n

O

) .