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ęć.