Informatyka - Podstawy Programowania w Języku C++
prow. Sławomir Czarnecki
Zadania na laboratorium nr. 7
1. Zdefiniuj dwie wersje funkcji „silnia”
!
n
dla dowolnego
0
n ≥
. Pierwszą wersja
rekurencyjną:
unsigned
long
silnia(
unsigned
long
n)
i drugą wersję iteracyjną
unsigned
long
SILNIA(
unsigned
long
n)
Przetestuj działanie obu tych funkcji (
dla
n
nie większego od
20).
2. Zdefiniuj dwie wersje funkcji „największy wspólny dzielnik liczb naturalnych m i n”.
Pierwszą wersja rekurencyjną:
unsigned
long
nwd(
unsigned
long
m,
unsigned
long
n)
i drugą wersję iteracyjną
unsigned
long
NWD(
unsigned
long
m,
unsigned
long
n)
w oparciu o algorytm:
• Krok 1. Dopóty dopóki m n
≠ wykonaj następujące podstawienie
jeśli
m > n, to m = m – n
w przeciwnym przypadku:
n = n – m
• Krok 2. NWD(m , n) = m
Przetestuj działanie obu tych funkcji.
3. Zdefiniuj (bardzo niewydajną) rekurencyjną wersję
unsigned
long
binomial(
unsigned
long
n,
unsigned
long
k)
funkcji na współczynnik dwumianowy
(
)
!
!
!
n
n
k
k n k
=
−
dla 0
k
n
≤ ≤
korzystając z następującej prostej do udowodnienia indukcyjnie zaleŜności rekurencyjnej
1
1
0
1
1
0
lub
n
n
k
n
n
k
k
k
k
k
n
−
−
+
< <
=
−
=
=
która pozwala wyeliminować konieczność obliczania wyraŜenia typu !
n lub !
k .
Algorytm rekurencyjny oblicza aŜ 2
1
n
k
−
wyrazów w celu obliczenia wartości
n
k
.
Wykorzystując tablicę
(
) (
)
1
1
n
k
+ ×
+
=
B
B
, gdzie składowa
[ ][ ]
(
)
0,1,..., ,
0,1,...,
B i
j
i
n
j
k
=
=
będzie zawierała wartość
i
j
moŜliwe jest „skonstruowanie” znacznie wydajniejszej
iteracyjnej wersji algorytmu
unsigned
long
BINOMIAL(
unsigned
long
n,
unsigned
long
k)
Definiowanie składowych macierzy B oparte jest rekurencyjną zaleŜność
[ ][ ]
[ ][
]
[
][ ]
1
1
1
0
1
0
lub
B i
j
B i
j
j
i
B i
j
j
j
i
−
− +
−
< <
=
=
=
oraz o realizację w porządku wstępującym, rozpoczynającym się od pierwszego wiersza i
wyliczającym po kolei wartości w wierszach tablicy B. KaŜda kolejna składowa wiersza (od
lewej do prawej) jest wyliczana na podstawie wartości składowych w wierszu
poprzedzającym przy wykorzystaniu powyŜszej zaleŜności rekurencyjnej. Ostatnia obliczana
wartość, to
[ ][ ]
n
B n k
k
=
. Np. przy obliczaniu
4
2
n
k
=
=
mamy
B[0][0] = 1
(wartość B[0][0] nie jest potrzebna w dalszych obliczeniach)
B[1][0]
=
1
B[1][1]
=
1
B[2][0]
=
1
B[2][1]
=
B[1][0] + B[1][1] = 1 + 1 = 2
B[2][k=2]
=
1
B[3][0]
=
1
B[3][1]
=
B[2][0] + B[2][1] = 1 + 2 = 3
B[3][k=2]
=
B[2][1] + B[2][2] = 2 + 1 = 3
B[n=4][0]
=
1
B[n=4][1]
=
B[3][0] + B[3][1] = 1 + 3 = 4
B[n=4][k=2] =
B[3][1] + B[3][2] = 3 + 3 = 6
(
Uwaga ! moŜliwych jest jeszcze szereg wielu dodatkowych ulepszeń
). Przetestuj działanie
obu tych funkcji.
4. Zdefiniuj dwie, odpowiednio rekurencyjną i iteracyjną wersję
double
bisection(
double
( *f )(
double
),
double
a,
double
b,
double
eps)
double
BISECTION(
double
( *f )(
double
),
double
a,
double
b,
double
eps)
funkcji poszukiwania pierwiastka ciągłej funkcji jednej zmiennej rzczywistej
:
f
→
ℝ
ℝ w
przedziale domkniętym
[ ]
,
I
a b
=
⊂ ℝ
z dokładnością eps > 0, w oparciu o algorytm metody
bisekcji. Zakładamy, Ŝe wartości funkcji f na końcach przedziału I są róŜne od zera i mają
róŜne znaki.
W wersji rekurencyjnej mamy:
• Pre: x
lewy
< x
prawy
, eps > 0. Znaki f(x) w punktach x
lewy
i x
prawy
muszą być róŜne, co
wystarcza do stwierdzenia, Ŝe w przedziale [x
lewy
, x
prawy
] znajduje się co najmniej
jeden pierwiastek.
• Rozpoczynamy od wyznaczenia punktu środkowego x
srodek
= (x
lewy
+ x
prawy
) / 2.
• NaleŜy wyróŜnić dwa przypadki elementarne: x
prawy
– x
lewy
< eps lub f(x
srodek
) = 0 dla
których pierwiastek = x
srodek
.
• Nie spełnienie Ŝadnego z przypadków elementarnych prowadzi do rekurencyjnego
wywołania funkcji:
bisection(f, x
lewy
, x
srodek
, eps) jeśli f(x
lewy
) f(x
srodek
) < 0
lub
bisection(f, x
srodek
, x
prawy
, eps) jeśli f(x
lewy
) f(x
srodek
) > 0.
x
lewy
x
lewy
x
lewy
x
prawy
x
prawy
x
prawy
x
srodek
x
srodek
x
srodek
f(x
prawy
)
f(x
lewy
)
f(x
lewy
)
f(x
lewy
)
f(x
prawy
)
f(x
prawy
)
pierwiastek
pierwiastek
pierwiastek
W wersji iteracyjnej strategia polega poszukiwaniu pierwiastka od skrajnego lewego punktu
przedziału I w kierunku prawym lub od skrajnego prawego punktu przedziału I w kierunku
lewym, w zaleŜności od tego, w którym z tych punktów wartość funkcji jest ujemna. KaŜdy
kolejny przyrost (dodatni lub ujemny) jest połową wartości ostatniego przyrostu, przy czym
nie dopuszczamy do sytuacji, w której wartość funkcji w nowo sprawdzanym punkcie byłaby
dodatnia (zawsze jesteśmy po ujemnej stronie). Szczegóły będą omówione na laboratorium.
Przetestuj działanie obu tych funkcji dla funkcji
( )
3
2
8
35
150
f x
x
x
x
=
−
−
+
w przedziale
[-3 , 4], której wykres przedstawiono na poniŜszym rysunku.
5. Sortowanie tablicy a[dim] przez wstawianie (por. np. Cormen T., Leiserson C., Rivest R.,
Wprowadzenie do algorytmów, Wyd. Naukowo-Techniczne, Warszawa 1997). Algorytm jest
analogiczny do czynności porządkowania talii kart. Zaczynamy od „pustej” lewej ręki, po
czym bierzemy ze stołu kolejne karty i wstawiamy je we właściwe miejsca w posortowanej
juŜ części talii kart trzymanej w lewej ręce. Aby znaleźć właściwe miejsce dla danej karty
trzymanej w prawej ręce, porównujemy ją (od strony prawej do lewej) z posortowanymi juŜ
kartami, które mamy w lewej ręce. Przykład:
lewa ręka
stół z nieposortowanymi kartami
5
2
4
6
1
3
talia na stole do posortowania
5
2
4
6
1
3
bierzemy pierwszą kartę
5
ze stołu do lewej ręki
5
2
4
6
1
3
bierzemy drugą kartę
2
ze stołu do lewej ręki
2
5
4
6
1
3
szukamy dla karty
2
właściwego miejsca w lewej ręce
2 5
4
6
1
3
bierzemy trzecią kartę
4
ze stołu do lewej ręki
2
4
5
6
1
3
szukamy dla karty
4
właściwego miejsca w lewej ręce
2 4 5
6
1
3
bierzemy czwartą kartę
6
ze stołu do lewej ręki
2 4 5 6
1
3
bierzemy piątą kartę
1
ze stołu do lewej ręki
2 4 5
1
6
3
szukamy dla karty
1
właściwego miejsca w lewej ręce
2 4
1
5 6
3
szukamy dla karty
1
właściwego miejsca w lewej ręce
2
1
4 5 6
3
szukamy dla karty
1
właściwego miejsca w lewej ręce
1
2 4 5 6
3
szukamy dla karty
1
właściwego miejsca w lewej ręce
1 2 4 5 6
3
bierzemy szóstą kartę
3
ze stołu do lewej ręki
1 2 4 5
3
6
szukamy dla karty
3
właściwego miejsca w lewej ręce
1 2 4
3
5 6
szukamy dla karty
3
właściwego miejsca w lewej ręce
1 2
3
4 5 6
szukamy dla karty
3
właściwego miejsca w lewej ręce
Uwaga ! Elementy tablicy mogą być sortowane w miejscu, tzn. nie jest konieczne
definiowanie Ŝadnej innej dodatkowej tablicy pomocniczej i wszystkie operacje moŜna
przeprowadzać na elementach sortowanej tablicy.
6. Porównanie dwóch algorytmów sortowania: insert_sort(...) oraz quick_sort(...).
Utwórz dość duŜą tablicę v typu
double
(np. v[100000]) inicjalizując ją dowolnymi liczbami
losowymi (na przykład z przedziału [–1000.0,1000.0]).
Przeprowadź dla tablicy v test szybkości działania obu algorytmów sortowania insert_sort(...)
i quick_sort(...).
7. Zaimplementuj algorytm poszukiwania binarnego w posortowanej tablicy a[dim] jako
funkcję
int
binary_search(
double
* a,
double
x,
int
dim). Funkcja binary_search(...) ma
zwracać najmniejszy indeks
(
)
0
i
i
dim
≤ <
, dla którego
[ ]
x
a i
=
lub –1, jeśli nie istnieje
składowa wektora a równa x. Idea (dobrze znanego i bardzo prostego) algorytmu
poszukiwania binarnego przedstawiona będzie w czasie zajęć.