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
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
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:
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;
{
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
) .