Informatyka - Podstawy Programowania w Języku C++
prow. Sławomir Czarnecki
Zadania na laboratorium nr. 8
1. Zdefiniuj dwie wersje funkcji „silnia”
!
n
dla dowolnego
0
n ≥
. Pierwszą wersja
rekurencyjną:
unsigned
long
long
silnia(
unsigned
long
long
n)
i drugą wersję iteracyjną
unsigned
long
long
SILNIA(
unsigned
long
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
long
nwd(
unsigned
long
long
m,
unsigned
long
long
n)
i drugą wersję iteracyjną
unsigned
long
long
NWD(
unsigned
long
long
m,
unsigned
long
long
n)
w oparciu o algorytm I z Lab 3:
• 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
long
binomial(
unsigned
long
long
n,
unsigned
long
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
long
BINOMIAL(
unsigned
long
long
n,
unsigned
long
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.